在不使用任何额外空间的情况下在BST中找到继承者

Question

我正在寻找一种方法来找出BST节点的继承者,而不是使用额外的空间.

Answer 1

要获取给定节点的inorder后继,N我们使用以下规则:

• 如果N有一个正确的孩子,R那么这 inorderSuccessor(N)是最左边的死者R.
• 否则inorderSuccessor(N)是最近的祖先,M中,N(如果存在的话),使得N从左侧子的后裔M.如果没有这样的祖先,则inorderSucessor不存在.

考虑一个示例树:

     A
    / \
   B   C
  / \ 
 D   E
    /
   F

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

inorderSuccessor(A)= C因为C是右子的最左边的继承人A.

inorderSuccessor(B)= F因为F是右子的最左边的继承人B.

inorderSuccessor(C) =不存在.

inorderSuccessor(D)= B正如B左边的孩子一样D.

inorderSuccessor(E)= A.E没有一个合适的孩子,所以我们有场景2.我们去父母的E是B,但是E是正确的继承人B,所以我们转移到母公司的B是A和B留下死者的A所以A是答案.

inorderSuccessor(F)= E正如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;
}

代码在行动

Answer 2

以下方法可帮助您确定顺序继承者,无需任何父节点或额外空间不可回复

struct node * inOrderSuccessor(struct node *root, struct node *n)
   { 
   //*If the node has a right child, return the smallest value of the right sub tree*

   if( n->right != NULL ) 
      return minValue(n->right); 

   //*Return the first ancestor in whose left subtree, node n lies*
   struct node *succ=NULL;
   while(root) 
   { 
      if(n->datadata < root->data) 
         {
            succ=root; root=root->left; 
         }

      else if(n->data > root->data) 
         root=root->right; 
      else break; 
   } 
  return succ;
 }

我很确定这是对的.如果我错了,请纠正我.谢谢.