1 //1 二叉树的深度(在后序遍历的基础上进行 时间复杂度: O(n)) (即左右子树的最大深度加1)  2 public int getDepth(BiTNode node) 3 { 4     if(node == null) 5     return 0; 6  7     int count1, count2; 8     count1 = getDepth(node.lchild); 9     count2 = getDepth(node.rchild);10     return max(count1, count2) + 1;11 }

1 //2 给定结点的后继(Successor) 2 public BiNode Successor(BiNode x) 3 { 4     BiNode p = x.rchild; 5     if(p != null) 6     { 7         while(p.lchild != null) 8             p = p.lchild; 9         return p;10     }11     BiNode q = x.parent;12     while(q != null && x == q.rchild)13     {14         x = q;15         q = q.parent;16     }17     return q;18 }

1 //3 给定结点的前驱(Predecessor) 2 public BiNode Predecessor(BiNode x) 3 { 4     BiNode p = x.lchild; 5     if(p != null) 6     { 7         while(p.rchild != null) 8             p = p.rchild; 9         return p;10     }11     BiNode q = x.parent;12     while(q != null && x == q.lchild)13     {14         x = q;15         q = q.parent;16     }17     return q;18 }