Explicar el recorrido del árbol inorder de Morris sin utilizar pilas o recursión

Question

¿Puede alguien ayudarme a entender el siguiente algoritmo de cruce de árbol inorder de Morris sin usar pilas o recursión? Estaba tratando de entender cómo funciona, pero me está escapando.

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 

entiendo el árbol se modifica de manera que el current node, se realiza la right child del max node en right subtree y utilizar esta propiedad para recorrido en orden. Pero más allá de eso, estoy perdido.

EDIT: Se encuentra este código de C++ que lo acompaña. Estaba teniendo dificultades para entender cómo se restaura el árbol después de que se modificó. La magia se encuentra en la cláusula else, que se activa una vez que se modifica la hoja derecha. Ver código para la descarga:

/* 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 */ 
} 

Answer 1

Si estoy leyendo la derecha algoritmo, esto debería ser un ejemplo de cómo funciona:

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

En primer lugar, X es la raíz, por lo que se inicializa como current . X tiene un elemento secundario izquierdo, por lo que X se convierte en el elemento secundario situado más a la derecha del subárbol izquierdo X, el predecesor inmediato de X en un recorrido inorden. Por lo tanto, X se convierte en el hijo correcto de B, luego current se establece en Y. El árbol ahora se ve así:

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

(Y) anterior se refiere a Y y todos sus hijos, que se omiten por cuestiones de recursividad. La parte importante se enumera de todos modos. Ahora que el árbol tiene un enlace a X, el recorrido continúa ...

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

Entonces A se emite, ya que no tiene hijo izquierdo, y se volvió a currentY, que se hizo A 's derecho niño en la iteración anterior. En la siguiente iteración, Y tiene ambos hijos. Sin embargo, la condición dual del ciclo hace que se detenga cuando se alcanza a sí mismo, lo cual es una indicación de que su subárbol izquierdo ya ha sido atravesado. Por lo tanto, se imprime a sí mismo y continúa con su subárbol derecho, que es B.

B impresiones de sí mismo, y entonces se convierte en currentX, que pasa por el mismo proceso de comprobación como Y lo hicieron, también darse cuenta de que su subárbol izquierdo ha sido recorrido, continuando con el Z. El resto del árbol sigue el mismo patrón.

No es necesaria la recursividad, porque en lugar de confiar en retroceder a través de una pila, un enlace a la raíz del (sub) árbol se mueve al punto al que se accedería en un algoritmo recursivo inorder tree transversal - después de que su subárbol izquierdo haya terminado.

Answer 2

espero que el pseudo-código de abajo es más revelador:

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 

Haciendo referencia al código C++ en la pregunta, el interior mientras bucle encuentra el predecesor en orden del nodo actual.En un árbol binario estándar, el hijo derecho del predecesor debe ser nulo, mientras que en la versión con subprocesamiento, el hijo derecho debe apuntar al nodo actual. Si el hijo correcto es nulo, se establece en el nodo actual, creando efectivamente el threading, que se utiliza como un punto de retorno que de otro modo tendría que estar almacenado, generalmente en una pila. Si el hijo correcto es no nulo, el algoritmo se asegura de que el árbol original se restaure y luego continúa el recorrido en el subárbol derecho (en este caso, se sabe que se visitó el subárbol izquierdo).

Answer 3

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

creo que este código sería mejor entender, sólo tiene que utilizar un nulo para evitar bucles infinitos, no tiene que usar la magia más. Se puede modificar fácilmente para preordenar.

Answer 4

El recorrido recursivo en orden es: (in-order(left)->key->in-order(right)). (Esto es similar a DFS)

Cuando hacemos el DFS, necesitamos saber a dónde dar marcha atrás (es por eso que normalmente mantenemos una pila).

A medida que avanzamos por un nodo primario al que tendremos que retroceder para encontrar el nodo del que tendremos que retroceder y actualizar su enlace al nodo primario.

¿Cuándo retrocedemos? Cuando no podemos ir más allá. Cuando no podemos ir más allá? Cuando no queda el regalo del niño.

¿A dónde retrocedemos? Aviso: ¡al SUCESOR!

Por lo tanto, como seguimos los nodos a lo largo de la ruta secundaria, configure el predecesor en cada paso para que apunte al nodo actual. De esta forma, los predecesores tendrán enlaces a sucesores (un enlace para retroceder).

Seguimos hacia la izquierda mientras podemos hasta que tengamos que retroceder. Cuando necesitamos retroceder, imprimimos el nodo actual y seguimos el enlace correcto al sucesor.

Si acabamos de retroceder -> tenemos que seguir al niño correcto (hemos terminado con el niño de la izquierda).

¿Cómo saber si acabamos de retroceder? Obtenga el predecesor del nodo actual y verifique si tiene un enlace correcto (a este nodo). Si lo tiene, entonces lo seguimos. eliminar el enlace para restaurar el árbol.

Si no había un enlace izquierdo =>, no retrocedimos y debemos continuar siguiendo a los niños de la izquierda.

Aquí está mi código Java (Lo siento, no es 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; 
}