Traverser un arbre n-aire sans recourir à la récurrence

Comment puis-je traverser un n-ary arbre sans utiliser la récursivité?

Façon récursive:

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

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

source d'informationauteur ako

  1. 10

    Vous pouvez le faire sans récursivité et sans pile. Mais vous devez ajouter deux pointeurs vers le nœud:

    1. Le nœud parent. Ainsi, vous pouvez revenir à la mère si vous avez terminé.

    2. L'actuel nœud enfant afin de savoir laquelle prendre.

      • Pour chaque nœud, vous permet de gérer tous les enfants.
      • Si un enfant est traitée, vous vérifiez si il y a un côté enfant et de le gérer (la mise à jour de l'actuel).
      • Si tous les enfants sont manipulés, aller à la maison mère.
      • Si le nœud est NULLE, à cesser de fumer.

    Avec pseudocode cela ressemble à:

    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;
    }
  }
}
  2. 17

    Ce que vous faites est essentiellement un DFS de l'arbre. Vous pouvez éliminer la récursivité à l'aide d'un pile:

    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 vous voulez un BFS utiliser une file d'attente:

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

    Dans le cas où vous voulez quelques autres de chemin à parcourir, vous aurez à suivre la même démarche mais avec une autre structure de données pour stocker le nœud. Peut-être une file d'attente de priorité (si vous voulez l'évaluation d'une fonction à chaque nœud, puis le processus de nœuds en fonction de cette valeur).

  3. 9

    Pas de langue donné, donc en pseudo-pseudo-code:

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

    Remarque que c'est une largeur d'abord traversée par opposition à la profondeur de la première traversée de donnée dans la question. Vous devriez être en mesure de le faire d'une profondeur d'abord traversée par poping le dernier élément hors de la nodes liste au lieu de shifting la première.