Обход 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извлекая первый.