找到序后继BST中不使用任何额外的空间 [英] find inorder successor in BST without using any extra space

问题描述

我要寻找一个办法，找出序在BST节点的后继withut使用额外的空间。

I am looking a way to find out inorder successor of a node in BST withut using extra space.

推荐答案

要获得一个给定的节点 N 我们用下面的规则的序后继：

To get the inorder successor of a given node N we use the following rules:

• 如果 N 有一个正确的子研究则 inorderSuccessor（N）是最左边 对被继承人研究。
• 否则 inorderSuccessor（N）是最接近 祖先ñ的 M ，（如果存在） 这样 N 从下降 的左子中号。如果没有这样的祖先，inorderSucessor不存在。

• If N has a right child R then the inorderSuccessor(N) is the leftmost decedent of R.
• Else inorderSuccessor(N) is the closest ancestor, M, of N (if it exists) such that N is descended from the left child of M. If there is no such ancestor, inorderSucessor does not exist.

请看下面一个简单的树：

Consider a sample tree:

     A
    / \
   B   C
  / \ 
 D   E
    /
   F

谁序遍历给出： DBFEAC

inorderSuccessor（A） = C 为 C 是的右孩子的最左边的继承人 A 。

inorderSuccessor(A) = C as C is the leftmost decedent of the right child of A.

inorderSuccessor（B） = F 为 F 是的右孩子的最左边的继承人 B 。

inorderSuccessor(B) = F as F is the leftmost decedent of the right child of B.

inorderSuccessor（C） =不存在。

inorderSuccessor（D） = B 为 B 是的左子 D 。

inorderSuccessor（E） = A 。 电子并没有一个合适的孩子，所以我们已经场景2.我们去电子是<$ C的父$ C> B ，而电子是 B 权继承人，所以我们转移到 B 是 A 和 B 的父母留给继承人对 A 让 A 就是答案。

inorderSuccessor(E) = A. E does not have a right child so we have scenario 2. We go to parent of E which is B, but E is right decedent of B, so we move to parent of B which is A and B is left decedent of A so A is the answer.

inorderSuccessor（F） = 电子为 F 是电子的左子。

步骤：

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在行动

这篇关于找到序后继BST中不使用任何额外的空间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！