c++ preorder - Spiega Morris inorder tree traversal senza usare stack o ricorsione




binary search (5)

Qualcuno può aiutarmi a capire il seguente algoritmo di attraversamento dell'albero in ordine Morris senza utilizzare pile o ricorsione? Stavo cercando di capire come funziona, ma mi sta sfuggendo.

 1. Initialize current as root
 2. While current is not NULL
  If current does not have left child     
   a. Print current’s data
   b. Go to the right, i.e., current = current->right
  Else
   a. In current's left subtree, make current the right child of the rightmost node
   b. Go to this left child, i.e., current = current->left

Comprendo che l'albero è stato modificato in modo che il current node sia reso il right child del max node nella right subtree e utilizzi questa proprietà per l'attraversamento inorder. Ma oltre a ciò, sono perso.

EDIT: trovato questo codice c ++ di accompagnamento. Stavo attraversando un periodo difficile per capire come viene ripristinato l'albero dopo che è stato modificato. La magia si trova nella clausola else , che viene colpita una volta modificata la foglia destra. Vedi il codice per i dettagli:

/* Function to traverse binary tree without recursion and
   without stack */
void MorrisTraversal(struct tNode *root)
{
  struct tNode *current,*pre;

  if(root == NULL)
     return; 

  current = root;
  while(current != NULL)
  {
    if(current->left == NULL)
    {
      printf(" %d ", current->data);
      current = current->right;
    }
    else
    {
      /* Find the inorder predecessor of current */
      pre = current->left;
      while(pre->right != NULL && pre->right != current)
        pre = pre->right;

      /* Make current as right child of its inorder predecessor */
      if(pre->right == NULL)
      {
        pre->right = current;
        current = current->left;
      }

     // MAGIC OF RESTORING the Tree happens here: 
      /* Revert the changes made in if part to restore the original
        tree i.e., fix the right child of predecssor */
      else
      {
        pre->right = NULL;
        printf(" %d ",current->data);
        current = current->right;
      } /* End of if condition pre->right == NULL */
    } /* End of if condition current->left == NULL*/
  } /* End of while */
}

Answers

L'attraversamento ricorsivo in ordine è: (in-order(left)->key->in-order(right)) . (questo è simile a DFS)

Quando facciamo il DFS, abbiamo bisogno di sapere dove tornare indietro (è per questo che normalmente manteniamo uno stack).

Mentre passiamo attraverso un nodo genitore al quale avremo bisogno di tornare indietro a -> troviamo il nodo di cui avremo bisogno per tornare indietro e aggiornare il suo collegamento al nodo genitore.

Quando torniamo indietro? Quando non possiamo andare oltre. Quando non possiamo andare oltre? Quando nessun bambino è presente a sinistra.

Dove torniamo indietro? Avviso: a SUCCESSORE!

Quindi, mentre seguiamo i nodi lungo il percorso left-child, impostiamo il predecessore ad ogni passaggio in modo che punti al nodo corrente. In questo modo, i predecessori avranno collegamenti ai successori (un collegamento per il backtracking).

Seguiamo a sinistra finché possiamo, finché non abbiamo bisogno di tornare indietro. Quando abbiamo bisogno di tornare indietro, stampiamo il nodo corrente e seguiamo il link giusto per il successore.

Se siamo appena tornati indietro -> dobbiamo seguire il bambino giusto (abbiamo finito con il figlio sinistro).

Come dire se siamo appena tornati indietro? Ottieni il predecessore del nodo corrente e controlla se ha un link giusto (su questo nodo). Se ha - di quello che abbiamo seguito. rimuovere il collegamento per ripristinare l'albero.

Se non ci fosse link a sinistra => non abbiamo fatto il backtrack e dovremmo procedere seguendo i bambini di sinistra.

Ecco il mio codice Java (Scusa, non è C ++)

public static <T> List<T> traverse(Node<T> bstRoot) {
    Node<T> current = bstRoot;
    List<T> result = new ArrayList<>();
    Node<T> prev = null;
    while (current != null) {
        // 1. we backtracked here. follow the right link as we are done with left sub-tree (we do left, then right)
        if (weBacktrackedTo(current)) {
            assert prev != null;
            // 1.1 clean the backtracking link we created before
            prev.right = null;
            // 1.2 output this node's key (we backtrack from left -> we are finished with left sub-tree. we need to print this node and go to right sub-tree: inOrder(left)->key->inOrder(right)
            result.add(current.key);
            // 1.15 move to the right sub-tree (as we are done with left sub-tree).
            prev = current;
            current = current.right;
        }
        // 2. we are still tracking -> going deep in the left
        else {
            // 15. reached sink (the leftmost element in current subtree) and need to backtrack
            if (needToBacktrack(current)) {
                // 15.1 return the leftmost element as it's the current min
                result.add(current.key);
                // 15.2 backtrack:
                prev = current;
                current = current.right;
            }
            // 4. can go deeper -> go as deep as we can (this is like dfs!)
            else {
                // 4.1 set backtracking link for future use (this is one of parents)
                setBacktrackLinkTo(current);
                // 4.2 go deeper
                prev = current;
                current = current.left;
            }
        }
    }
    return result;
}

private static <T> void setBacktrackLinkTo(Node<T> current) {
    Node<T> predecessor = getPredecessor(current);
    if (predecessor == null) return;
    predecessor.right = current;
}

private static boolean needToBacktrack(Node current) {
    return current.left == null;
}

private static <T> boolean weBacktrackedTo(Node<T> current) {
    Node<T> predecessor = getPredecessor(current);
    if (predecessor == null) return false;
    return predecessor.right == current;
}

private static <T> Node<T> getPredecessor(Node<T> current) {
    // predecessor of current is the rightmost element in left sub-tree
    Node<T> result = current.left;
    if (result == null) return null;
    while(result.right != null
            // this check is for the case when we have already found the predecessor and set the successor of it to point to current (through right link)
            && result.right != current) {
        result = result.right;
    }
    return result;
}

public static void morrisInOrder(Node root) {
        Node cur = root;
        Node pre;
        while (cur!=null){
            if (cur.left==null){
                System.out.println(cur.value);      
                cur = cur.right; // move to next right node
            }
            else {  // has a left subtree
                pre = cur.left;
                while (pre.right!=null){  // find rightmost
                    pre = pre.right;
                }
                pre.right = cur;  // put cur after the pre node
                Node temp = cur;  // store cur node
                cur = cur.left;  // move cur to the top of the new tree
                temp.left = null;   // original cur left be null, avoid infinite loops
            }        
        }
    }

Penso che questo codice sarebbe meglio da capire, basta usare un null per evitare loop infiniti, non usare la magia altrimenti. Può essere facilmente modificato per preordinare.


Spero che lo pseudo-codice qui sotto sia più rivelatore:

node = root
while node != null
    if node.left == null
        visit the node
        node = node.right
    else
        let pred_node be the inorder predecessor of node
        if pred_node.right == null /* create threading in the binary tree */
            pred_node.right = node
            node = node.left
        else         /* remove threading from the binary tree */
            pred_node.right = null 
            visit the node
            node = node.right

Facendo riferimento al codice C ++ nella domanda, il ciclo while interno trova il predecessore in ordine del nodo corrente. In un albero binario standard, il figlio destro del predecessore deve essere nullo, mentre nella versione con thread il figlio giusto deve puntare al nodo corrente. Se il figlio destro è nullo, viene impostato sul nodo corrente, creando effettivamente il threading , che viene utilizzato come punto di ritorno che altrimenti dovrebbe essere memorizzato, solitamente in pila. Se il figlio destro non è nullo, l'algoritmo si assicura che l'albero originale sia ripristinato e quindi prosegua l'attraversamento nella sottostruttura di destra (in questo caso è noto che la sottostruttura di sinistra è stata visitata).


Se sto leggendo correttamente l'algoritmo, questo dovrebbe essere un esempio di come funziona:

     X
   /   \
  Y     Z
 / \   / \
A   B C   D

Innanzitutto, X è la radice, quindi è inizializzata come current . X ha un figlio di sinistra, quindi X è il figlio di destra più a destra della sottostruttura di sinistra di X - il predecessore immediato di X in un traversal inorder. Quindi X è il figlio giusto di B , quindi la current è impostata su Y L'albero ora si presenta così:

    Y
   / \
  A   B
       \
        X
       / \
     (Y)  Z
         / \
        C   D

(Y) sopra si riferisce a Y e a tutti i suoi figli, che sono omessi per problemi di ricorsione. La parte importante è elencata comunque. Ora che l'albero ha un link a X, l'attraversamento continua ...

 A
  \
   Y
  / \
(A)  B
      \
       X
      / \
    (Y)  Z
        / \
       C   D

Quindi A viene emesso, poiché non ha un figlio sinistro, e la current viene restituita a Y , che è stata resa figlia di A destra nell'iterazione precedente. Alla successiva iterazione, Y ha entrambi i bambini. Tuttavia, la duplice condizione del loop lo fa arrestare quando raggiunge se stesso, il che indica che è già stato attraversato il sottoalbero sinistro. Quindi, si stampa da solo, e continua con il suo sottoalbero destro, che è B

B stampa da solo, e quindi la current diventa X , che passa attraverso lo stesso processo di controllo di Y , realizzando anche che il suo sottoalbero sinistro è stato attraversato, continuando con la Z Il resto dell'albero segue lo stesso schema.

Non è necessaria alcuna ricorsione, perché invece di ricorrere al backtracking attraverso uno stack, un collegamento alla radice dell'albero (sub) viene spostato al punto in cui si accederà comunque in un algoritmo di attraversamento ad albero ricorsivo in ordine il sottoalbero sinistro è finito.


Per verificare se un albero binario non è un albero binario di ricerca, ecco un approccio alternativo.

Traverse Tree In Inorder Fashion (es. Left Child -> Parent -> Right Child), Memorizza i dati del nodo attraversato in una variabile temporanea lascia dire temp , appena prima di essere memorizzato in temp , Controlla che i dati correnti del nodo siano più alti di quelli precedenti o no . Quindi, basta rompere , Albero non è Albero di ricerca binaria, altrimenti attraversa fino alla fine.

Di seguito è riportato un esempio con Java:

public static boolean isBinarySearchTree(Tree root)
{
    if(root==null)
        return false;

    isBinarySearchTree(root.left);
    if(tree.data<temp)
        return false;
    else
        temp=tree.data;
    isBinarySearchTree(root.right);
    return true;
}

Mantenere la variabile temp all'esterno







c++ binary-tree tree-traversal