Explicar a Morris en el recorrido del árbol sin usar stacks o recursión

¿Puede alguien ayudarme a entender el siguiente algoritmo de cruce de árbol inorder de Morris sin usar stacks 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, ie, 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, ie, current = current->left 

Entiendo que el árbol se modifica de forma que el current node se convierta en el elemento right child del max node en right subtree y use esta propiedad para el recorrido inorden. Pero más allá de eso, estoy perdido.

EDITAR: Encontré este código de c ++ adjunto. 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 golpea una vez que se modifica la hoja derecha. Ver código para más detalles:

 /* 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 restre the original tree ie, 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 */ } 

    Si estoy leyendo el algoritmo correctamente, este debería ser un ejemplo de cómo funciona:

      X / \ YZ / \ / \ ABCD 

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

      Y / \ AB \ X / \ (Y) Z / \ CD 

    (Y) arriba se refiere a Y y a todos sus hijos, que se omiten por problemas de recursión. 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 / \ CD 

    A continuación, se emite A, porque no tiene ningún elemento secundario izquierdo, y la current se devuelve a Y , que se convirtió en el secundario derecho de A 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. Entonces, se imprime a sí mismo y continúa con su subárbol derecho, que es B

    B imprime a sí mismo, y luego la current convierte en X , que pasa por el mismo proceso de comprobación que Y , y se da cuenta de que su subárbol izquierdo ha sido atravesado, continuando con la Z El rest del árbol sigue el mismo patrón.

    No es necesaria ninguna recursividad, porque en lugar de confiar en el rastreo retroactivo a través de una stack, un enlace de regreso a la raíz del (sub) árbol se mueve al punto al que se accedería en un algoritmo recursivo de cruce de árboles ordenados de todos modos: después de su el subárbol izquierdo ha terminado.

    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 stack).

    A medida que avancemos por un nodo padre al que tendremos que retroceder hasta -> encontramos el nodo del que necesitaremos retroceder y actualizar su enlace al nodo padre.

    Cuando 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, a medida que seguimos los nodos a lo largo de la ruta del hijo izquierdo, establece el predecesor en cada paso para apuntar al nodo actual. De esta forma, los predecesores tendrán enlaces a sucesores (un enlace para retroceder).

    Seguimos hacia la izquierda mientras podamos 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 ningún enlace izquierdo =>, no retrocedimos y debemos continuar siguiendo a los niños de la izquierda.

    Aquí está mi código de Java (lo siento, no es C ++)

     public static  List traverse(Node bstRoot) { Node current = bstRoot; List result = new ArrayList<>(); Node 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  void setBacktrackLinkTo(Node current) { Node predecessor = getPredecessor(current); if (predecessor == null) return; predecessor.right = current; } private static boolean needToBacktrack(Node current) { return current.left == null; } private static  boolean weBacktrackedTo(Node current) { Node predecessor = getPredecessor(current); if (predecessor == null) return false; return predecessor.right == current; } private static  Node getPredecessor(Node current) { // predecessor of current is the rightmost element in left sub-tree Node 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 } } } 

    Creo que este código sería mejor de entender, solo usa un nulo para evitar bucles infinitos, no tienes que usar magic else. Se puede modificar fácilmente para preordenar.

    Espero que el pseudo-código a continuación sea 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 

    Con respecto al código C ++ en la pregunta, el ciclo while interior 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 derecho es nulo, se establece en el nodo actual, creando efectivamente el subprocesamiento , que se utiliza como un punto de retorno que de otro modo tendría que estar almacenado, generalmente en una stack. Si el hijo correcto no es nulo, entonces 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).