Обхождане на n-арно дърво без използване на рекурсия

Можете да направите това без рекурсия и без стек. Но трябва да добавите два допълнителни указателя към възела:

1. Родителският възел. Така че можете да се върнете при родителя, ако сте приключили.

2. Текущият дъщерен възел, за да знаете кой да вземете следващия.

   • For each node, you handle all the kids.
   • Ако едно дете е обработено, вие проверявате дали има следващо дете и го обработвате (актуализиране на текущото).
   • Ако всички деца са обработени, върнете се при родителя.
   • Ако възелът е NULL, излезте.

С псевдокод това изглежда така:

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

Това, което правите, е по същество DFS на дървото. Можете да премахнете рекурсията, като използвате стек:

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

Ако искате BFS, използвайте опашка:

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

В случай, че искате някакъв друг начин за преминаване, ще трябва да следвате същия подход, макар и с различна структура от данни, за да съхраните възела. Може би приоритетна опашка (ако искате да оцените функция във всеки възел и след това да обработвате възли въз основа на тази стойност).

Не е даден език, така че в псевдо-псевдокод:

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

Имайте предвид, че това е обхождане първо в ширина, за разлика от обхождането първо в дълбочина, дадено във въпроса. Трябва да можете да направите обхождане първо в дълбочина, като popвключите последния елемент от nodes списъка, вместо shiftвключвайки първия.