algorithm - 在不使用任何额外空间的情况下在 BST 中找到顺序后继

Question

我正在寻找一种无需使用额外空间即可在 BST 中找出节点的有序后继者的方法。

Answer 1

要获得给定节点 N 的有序后继，我们使用以下规则:

• 如果 N 有一个右 child R 那么inorderSuccessor(N) 最左边R 的后裔。
• Else inorderSuccessor(N) 是最接近的N 的祖先，M(如果存在)这样 N 是从M 的左 child 。如果没有这样的祖先，则 inorderSucessor 不存在。

考虑一棵示例树:

     A
    / \
   B   C
  / \ 
 D   E
    /
   F

谁的中序遍历给出:D B F E A C

inorderSuccessor(A) = C 因为 C 是 A 的右 child 的最左边的后裔。

inorderSuccessor(B) = F 因为 F 是 B 的右 child 的最左边的后裔。

inorderSuccessor(C) = 不存在。

inorderSuccessor(D) = B 因为 B 是 D 的左 child 。

inorderSuccessor(E) = A。 E 没有右 child ，所以我们有场景 2。我们转到 E 的父级，即 B，但是 E 是 B 的右后代，所以我们移动到 B 的父级，即 A 和 B 是A 的左后裔所以 A 是答案。

inorderSuccessor(F) = E 因为 F 是 E 的左 child 。

程序:

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;
}

Code In Action