найти преемника в BST, не занимая лишних пробелов

Question

Я ищу способ узнать преемника преемника узла в BST без использования дополнительного пространства.

Answer 1

Чтобы получить преемника-преемника данного узла 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;
 }

Я совершенно уверен, что это правильно. Поправь меня, если я ошибаюсь. Благодарю.

Answer 3

Если у данного узла есть правый дочерний элемент - перейдите к нему, а затем итеративно следуйте левым дочерним элементам, пока не достигнете узла N без левых дочерних элементов.Верните N.

В противном случае следуйте за родителями, пока не найдете сначала родителя, в котором узел является левым дочерним элементом.Верните этого родителя.

Node InOrderSuccessor(Node node) {
    if (node.right() != null) {
        node = node.right()
        while (node.left() != null) 
            node = node.left()
        return node
    } else {
        parent = node.getParent();
        while (parent != null && parent.right() == node) {
            node = parent
            parent = node.getParent()
        }
        return parent
    }
}

Answer 4

Если вы можете получить доступ к корню узла, то это просто вопрос перемещения указателей, так что нет лишнего пространства.Смотрите эту лекцию .