Explicar el recorrido del árbol en orden de Morris sin usar pilas o recursividad

¿Alguien puede ayudarme a comprender el siguiente algoritmo transversal de árbol de orden de Morris sin usar pilas o recursividad? Estaba tratando de entender cómo funciona, pero simplemente se me escapa.

 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 que el árbol se modifica de manera que current node, se convierte en el right childde max nodein right subtreey usa esta propiedad para el recorrido en orden. Pero más allá de eso, estoy perdido.

EDITAR: Encontré este código c ++ adjunto. Me costaba entender cómo se restaura el árbol después de que se modifica. La magia está en la elsecláusula, que se activa una vez que se modifica la hoja derecha. Consulte el código para obtener 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 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 */
}

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

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

Primero, Xes la raíz, por lo que se inicializa como current. Xtiene un hijo izquierdo, por lo que Xse convierte en el hijo situado más a la derecha del Xsubárbol izquierdo de, el predecesor inmediato de Xen un recorrido en orden. Entonces Xse convierte en el hijo correcto de B, luego currentse establece en Y. El árbol ahora se ve así:

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

(Y)arriba se refiere ay Ytodos sus elementos secundarios, que se omiten por problemas de recursividad. La parte importante se enumera de todos modos. Ahora que el árbol tiene un vínculo de regreso a X, el recorrido continúa ...

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

Luego Ase genera una salida, porque no tiene un hijo izquierdo, y currentse devuelve a Y, que se hizo Ael hijo derecho en la iteración anterior. En la siguiente iteración, Y tiene ambos hijos. Sin embargo, la condición dual del bucle hace que se detenga cuando llega a sí mismo, lo cual es una indicación de que el subárbol izquierdo ya ha sido atravesado. Entonces, se imprime y continúa con su subárbol derecho, que es B.

Bse imprime y luego se currentconvierte en X, que pasa por el mismo proceso de verificación que lo Yhizo, y también se da cuenta de que su subárbol izquierdo ha sido atravesado, continuando con el Z. El resto del árbol sigue el mismo patrón.

No es necesaria la recursividad, porque en lugar de depender del retroceso a través de una pila, un enlace de regreso a la raíz del (sub) árbol se mueve al punto en el que se accedería en un algoritmo recursivo de recorrido de árbol en orden de todos modos, después de su el subárbol izquierdo ha terminado.

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

Cuando hacemos el DFS, necesitamos saber hacia dónde retroceder (por eso normalmente mantenemos una pila).

A medida que pasamos por un nodo principal al que tendremos que retroceder -> encontramos el nodo desde el que tendremos que retroceder y actualizar su enlace al nodo principal.

¿Cuándo retrocedemos? Cuando no podemos ir más lejos. ¿Cuándo no podemos ir más lejos? Cuando ningún niño dejado presente.

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

Entonces, a medida que seguimos los nodos a lo largo de la ruta secundaria izquierda, 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 a la izquierda mientras podamos hasta que necesitemos dar marcha atrás. Cuando necesitamos retroceder, imprimimos el nodo actual y seguimos el enlace correcto al sucesor.

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

¿Cómo saber si acabamos de dar marcha atrás? Obtenga el predecesor del nodo actual y verifique si tiene un enlace correcto (a este nodo). Si es así, lo seguimos. elimine el enlace para restaurar el árbol.

Si no había un enlace izquierdo => no retrocedimos y deberíamos continuar siguiendo a los niños izquierdos.

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

He hecho una animación para el algoritmo aquí: https://docs.google.com/presentation/d/11GWAeUN0ckP7yjHrQkIB0WT9ZUhDBSa-WR0VsPU38fg/edit?usp=sharing

Con suerte, esto debería ayudar a comprender. El círculo azul es el cursor y cada diapositiva es una iteración del ciclo exterior while.

Aquí está el código para morris traversal (lo copié y modifiqué de geeks para geeks):

def MorrisTraversal(root):
    # Set cursor to root of binary tree
    cursor = root
    while cursor is not None:
        if cursor.left is None:
            print(cursor.value)
            cursor = cursor.right
        else:
            # Find the inorder predecessor of cursor
            pre = cursor.left
            while True:
                if pre.right is None:
                    pre.right = cursor
                    cursor = cursor.left
                    break
                if pre.right is cursor:
                    pre.right = None
                    cursor = cursor.right
                    break
                pre = pre.right
#And now for some tests. Try "pip3 install binarytree" to get the needed package which will visually display random binary trees
import binarytree as b
for _ in range(10):
    print()
    print("Example #",_)
    tree=b.tree()
    print(tree)
    MorrisTraversal(tree)

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 use un nulo para evitar bucles infinitos, no tiene que usar magia más. Se puede modificar fácilmente para reservar.

Encontré una muy buena explicación pictórica de Morris Traversal .

Espero que el pseudocó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

Refiriéndose al código C ++ en la pregunta, el bucle while interno 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 subprocesos, el hijo derecho debe apuntar al nodo actual. Si el hijo correcto es nulo, se establece en el nodo actual, creando de manera efectiva el subproceso , que se usa como un punto de retorno que de otra manera tendría que estar almacenado, generalmente en una pila. Si el hijo derecho no es nulo, entonces el algoritmo se asegura de que se restaure el árbol original y luego continúa el recorrido en el subárbol derecho (en este caso se sabe que se visitó el subárbol izquierdo).

Complejidad del tiempo de la solución de Python: O (n) Complejidad del espacio: O (1)

Excelente explicación transversal de Morris Inorder

class Solution(object):
def inorderTraversal(self, current):
    soln = []
    while(current is not None):    #This Means we have reached Right Most Node i.e end of LDR traversal

        if(current.left is not None):  #If Left Exists traverse Left First
            pre = current.left   #Goal is to find the node which will be just before the current node i.e predecessor of current node, let's say current is D in LDR goal is to find L here
            while(pre.right is not None and pre.right != current ): #Find predecesor here
                pre = pre.right
            if(pre.right is None):  #In this case predecessor is found , now link this predecessor to current so that there is a path and current is not lost
                pre.right = current
                current = current.left
            else:                   #This means we have traverse all nodes left to current so in LDR traversal of L is done
                soln.append(current.val) 
                pre.right = None       #Remove the link tree restored to original here 
                current = current.right
        else:               #In LDR  LD traversal is done move to R  
            soln.append(current.val)
            current = current.right

    return soln

Explicación del PFB del recorrido en orden de Morris.

  public class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
        {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    class MorrisTraversal
    {
        public static IList<int> InOrderTraversal(TreeNode root)
        {
            IList<int> list = new List<int>();
            var current = root;
            while (current != null)
            {
                //When there exist no left subtree
                if (current.left == null)
                {
                    list.Add(current.val);
                    current = current.right;
                }
                else
                {
                    //Get Inorder Predecessor
                    //In Order Predecessor is the node which will be printed before
                    //the current node when the tree is printed in inorder.
                    //Example:- {1,2,3,4} is inorder of the tree so inorder predecessor of 2 is node having value 1
                    var inOrderPredecessorNode = GetInorderPredecessor(current);
                    //If the current Predeccessor right is the current node it means is already printed.
                    //So we need to break the thread.
                    if (inOrderPredecessorNode.right != current)
                    {
                        inOrderPredecessorNode.right = null;
                        list.Add(current.val);
                        current = current.right;
                    }//Creating thread of the current node with in order predecessor.
                    else
                    {
                        inOrderPredecessorNode.right = current;
                        current = current.left;
                    }
                }
            }

            return list;
        }

        private static TreeNode GetInorderPredecessor(TreeNode current)
        {
            var inOrderPredecessorNode = current.left;
            //Finding Extreme right node of the left subtree
            //inOrderPredecessorNode.right != current check is added to detect loop
            while (inOrderPredecessorNode.right != null && inOrderPredecessorNode.right != current)
            {
                inOrderPredecessorNode = inOrderPredecessorNode.right;
            }

            return inOrderPredecessorNode;
        }
    }