Atravesar un árbol n-ario sin usar recurrsion

Question

¿Cómo puedo atravesar un árbol n -ary sin usar recursión?

manera recursiva:

traverse(Node node) 
{ 
    if(node == null) 
     return; 

    for(Node child : node.getChilds()) { 
     traverse(child); 
    } 
} 

Answer 1

Puede hacerlo sin recursion y sin una pila. Pero debe agregar dos punteros adicionales al nodo:

1. El nodo primario. Entonces puedes volver con el padre si terminaste.

2. El nodo hijo actual para que sepa cuál tomará a continuación.

   • Para cada nodo, usted maneja a todos los niños.
   • Si se maneja un niño, usted verifica si hay un próximo niño y lo maneja (actualizando el actual).
   • Si se manejan todos los niños, regrese con el padre.
   • Si el nodo es NULL, salga.

Con pseudocódigo será similar a:

traverse(Node node) { 
    while (node) { 
    if (node->current <= MAX_CHILD) { 
     Node prev = node; 
     if (node->child[node->current]) { 
     node = node->child[node->current]; 
     } 
     prev->current++; 
    } else { 
     // Do your thing with the node. 
     node->current = 0; // Reset counter for next traversal. 
     node = node->parent; 
    } 
    } 
} 

Answer 2

Ningún lenguaje dado, por lo que en pseudo-pseudocódigo:

traverse(Node node) 
{ 
    List<Node> nodes = [node]; 

    while (nodes.notEmpty) { 
    Node n = nodes.shift(); 

    for (Node child in n.getChildren()) { 
     nodes.add(child); 
    } 

    // do stuff with n, maybe 
    } 
} 

Tenga en cuenta que este es un recorrido primero en amplitud en comparación con el recorrido en profundidad dada en la pregunta. Debería poder hacer un recorrido en profundidad por pop al último elemento de la lista nodes en lugar de shift en el primero.

Answer 3

Lo que está haciendo es esencialmente un DFS del árbol. Puede eliminar la recursividad utilizando una pila:

traverse(Node node) { 
    if (node==NULL) 
     return; 

    stack<Node> stk; 
    stk.push(node); 

    while (!stk.empty()) { 
     Node top = stk.pop(); 
     for (Node child in top.getChildren()) { 
      stk.push(child); 
     } 
     process(top); 
    } 
} 

Si quieres un BFS utilizar una cola:

traverse(Node node) { 
    if (node==NULL) 
     return; 

    queue<Node> que; 
    que.addRear(node); 

    while (!que.empty()) { 
     Node front = que.deleteFront(); 
     for (Node child in front.getChildren()) { 
      que.addRear(child); 
     } 
     process(front); 
    } 
} 

En caso de que quiera alguna otra forma de recorrer, que tendrá que seguir el mismo enfoque, aunque con una estructura de datos diferente para almacenar el nodo. Tal vez una cola de prioridad (si desea evaluar una función en cada nodo y luego procesar los nodos según ese valor).