c++ - ventajas - recursividad javascript ejemplos

Explicar a Morris en el recorrido del árbol sin usar 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 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 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

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

Answer 2

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

Answer 3

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

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

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
   / /
  A   B
       /
        X
       / /
     (Y)  Z
         / /
        C   D

(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
        / /
       C   D

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 resto 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 pila, 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.

Answer 4

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.