znajdź następcę kolejność w BST bez użycia dodatkowej przestrzeni

Question

Szukam sposobu, aby dowiedzieć się, następca w kolejności węzła w BST z wykorzystaniem dodatkowego miejsca.

Answer 1

Aby uzyskać następcę Inorder danego węzła N używamy następujących zasad:

• Jeśli N ma prawo dziecka R wtedy inorderSuccessor(N) jest od lewej decedent z R.
• Else inorderSuccessor(N) jest najbliżej przodek, M, z N (jeśli istnieje) takie, że N pochodzi od lewej dziecka M . Jeśli nie ma takiego przodka, inorderSucessor nie istnieje.

Rozważmy drzewo próbki:

 A 
    /\ 
    B C 
/\ 
D E 
    /
    F 

Czyje Inorder przechodzenie daje: D B F E A C

inorderSuccessor(A) = C jak C jest od lewej decedent prawego dziecka A.

inorderSuccessor(B) = F jako F jest najdłuższym potomkiem właściwego dziecka B.

inorderSuccessor(C) = Nie istnieje.

inorderSuccessor(D) = B jako B to lewe dziecko z D.

inorderSuccessor(E) = A. E nie ma prawa dziecka więc mamy scenariusz 2. Idziemy do rodzica E który jest B, ale E ma rację decedent z B, więc przechodzimy do rodzica B która A i B pozostało decedent z A tak A jest odpowiedzią.

inorderSuccessor(F) = E jako F to lewe dziecko z E.

Procedura:

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

Answer 2

Jeśli możesz uzyskać dostęp do katalogu głównego węzła, to tylko kwestia przesuwania wskaźników, więc nie ma dodatkowej przestrzeni. Zobacz this lecture.

Answer 3

Jeśli podany węzeł ma właściwe dziecko - przejdź do niego, a następnie wykonaj iteracyjnie lewe dzieci aż do węzła N bez lewego dziecka. Zwróć nr

W przeciwnym razie podążaj za rodzicami, dopóki nie znajdziesz rodzica, w którym węzeł jest lewym dzieckiem. Zwróć ten rodzic.

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

Poniższa metoda pozwala określić następcę Inorder BEZ każdego rodzica węzła lub dodatkową przestrzeń NIEPODLEGANIA rekurencyjnie

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

jestem dość to prawda. Popraw mnie, jeśli się mylę. Dzięki.