trova inorder successore in BST senza utilizzare ulteriore spazio

Question

Sto cercando un modo per scoprire il successore inorder di un nodo in BST senza utilizzare spazio aggiuntivo.

Answer 1

Per ottenere il successore ordine simmetrico di un dato nodo N usiamo le seguenti regole:

• Se N ha un figlio destro R poi il inorderSuccessor(N) è il più a sinistra defunto di R.
• Else inorderSuccessor(N) è il più vicino antenato , M, di N (se esiste) tale che N discende dalla figlio sinistro di M. Se non esiste un tale antenato, inorderSucessor non esiste.

consideri un albero campione:

 A 
    /\ 
    B C 
/\ 
D E 
    /
    F 

Di chi dà ordine simmetrico: D B F E A C

inorderSuccessor(A) = C come C è il defunto più a sinistra del figlio destro di A.

inorderSuccessor(B) = F come F è il defunto più a sinistra del figlio destro di B.

inorderSuccessor(C) = Non esiste.

inorderSuccessor(D) = B come B è il figlio sinistro di D.

inorderSuccessor(E) = A. E non hai un bambino a destra in modo che abbiamo scenario 2. Andiamo a controllante di E che è B, ma E è giusto defunto di B, quindi passiamo alla madre di B che è A e B resta defunto di A così A è la risposta.

inorderSuccessor(F) = E come F è il figlio sinistro di 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

Se è possibile accedere alla radice di un nodo, è solo questione di spostare i puntatori in giro, quindi non c'è spazio extra. Vedi this lecture.

Answer 3

Se il nodo specificato ha un figlio destro, andare ad esso e quindi seguire iterativamente i bambini di sinistra finché non si raggiunge un nodo N senza figli di sinistra. Ritorno N.

Altrimenti, seguire i genitori fino a quando non si trova prima un genitore in cui il nodo è figlio sinistro. Restituisci questo genitore

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

Il seguente metodo consente di determinare il successore inorder SENZA nodo padre o extra spazio non ricorsivo

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

Sono abbastanza certo questo è giusto. Correggi se sbaglio. Grazie.