在 BST 中查找中序后继而不使用任何额外空间

我正在寻找一种方法来找出 BST 中节点的中序后继者，而不使用额外的空间。

获取给定节点的中序后继节点N我们使用以下规则：

• If N有一个合适的孩子R那么inorderSuccessor(N)是最左边的 的后继者R.
• Else inorderSuccessor(N)是最接近的 祖先，M, of N（如果存在） 这样N是从 的左孩子M。如果没有这样的祖先，则 inorderSucessor 不存在。

考虑一个示例树：

     A
    / \
   B   C
  / \ 
 D   E
    /
   F

其中序遍历给出：D B F E A C

inorderSuccessor(A) = C as C是右孩子的最左边的后裔A.

inorderSuccessor(B) = F as F是右孩子的最左边的后裔B.

inorderSuccessor(C)= 不存在。

inorderSuccessor(D) = B as B是的左孩子D.

inorderSuccessor(E) = A. E没有正确的孩子，所以我们有场景 2。我们去找E这是B, but E是 的右继承人B，所以我们移动到父级B这是A and B被遗弃的A so A就是答案。

inorderSuccessor(F) = E as F是的左孩子E.

程序：

treeNodePtr inorderSucessor(treeNodePtr N) {
        if(N) {
                treeNodePtr tmp;
                // CASE 1: right child of N exists.
                if(N->right) {
                        tmp = N->right;
                        // find leftmost node.
                        while(tmp->left) {
                                tmp = tmp->left;
                        }
                // CASE 2: No right child.
                } else {
                        // keep climbing till you find a parent such that
                        // node is the left decedent of it.
                        while((tmp = N->parent)) {
                                if(tmp->left == N) {
                                        break;
                                }
                                N = tmp;
                        }
                }
                return tmp;
        }
        // No IOS.
        return NULL;
}

代码在行动 http://www.ideone.com/imqy2