algorithm - orden - Atravesando un árbol n-ario sin usar recurrsion

orden de un arbol

Question

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

Vía recursiva:

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

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

Answer 1

Lo que estás haciendo es esencialmente un DFS del árbol. Puedes eliminar la recursión usando 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 usa 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 desee alguna otra forma de atravesar, deberá 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 en función de ese valor).

Answer 2

Puedes hacer esto sin recursión y sin una pila. Pero necesitas agregar dos punteros adicionales al nodo:

1. El nodo padre. Así que puedes volver con el padre si has terminado.

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

   • Para cada nodo, manejas a todos los niños.
   • Si se maneja a un niño, verifica si hay un próximo niño y lo manejas (actualizando el actual).
   • Si todos los niños son manejados, vuelva con los padres.
   • Si el nodo es NULL, salga.

Con pseudocódigo esto se ve como:

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 3

Sin idioma dado, así 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 oposición al recorrido primero en profundidad dado en la pregunta. Debería poder hacer un recorrido primero en profundidad sacando el último elemento de la lista de nodes lugar de shift el primero.