不使用递归遍历 n 叉树

Question

如何在不使用递归的情况下遍历一个 n 叉树？

递归方法：

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

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

- ako

---

任何递归算法都可以被转换成循环加栈的形式，因此这并不会限制我们使用。你可以用 Google 上找到的任何算法来完成任务。请注意在翻译过程中不改变原文意思，并尽量使翻译通俗易懂。 - Matthew Scharley

我心情很好，所以我已经为您翻译了算法。总的来说，这并不是一件非常困难的事情，一个快速的谷歌搜索就可以找到许多结果。树遍历在历史上已经成为一个非常明确的问题。 - Matthew Scharley

只是有趣的问题@ako。为什么你想要不使用递归来完成它？这是有原因的还是只是为了赚取声望而提出的问题？ - Mihran Hovsepyan

为什么用户会加入Stack Overflow并在之前从未使用过的网站上获取声望？ - Nicolas78

Answer 1

你正在做的本质上是树的深度优先遍历。你可以通过使用堆栈来消除递归：

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

如果您想使用其他遍历方式，您将需要采取相同的方法，但使用不同的数据结构来存储节点。也许可以使用优先队列（如果您想要在每个节点上评估一个函数并根据该值处理节点）。

- BiGYaN

---

BFS代表广度优先搜索，DFS代表深度优先搜索。 - Marduk

process(top) 意味着什么？它是做什么用的？ - jbuddy_13

@jbuddy_13 通常人们会遍历树的原因是为了某个目的（例如打印节点内容的值）。process 处理这个过程。 - BiGYaN

Answer 2

你可以在不使用递归和栈的情况下完成此操作。但是你需要向节点添加两个额外的指针:

1.父节点，以便在完成后返回到父节点。 2.当前子节点，以便知道下一步该选择哪一个。

对于每个节点，你都要处理所有的孩子节点。 如果某个孩子节点已被处理，则检查是否有下一个孩子节点并处理它（更新当前）。 如果所有孩子节点都已被处理，则返回到父节点。 如果节点为空，则退出。

伪代码如下：

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

- Toon Krijthe

---

好的，现在我明白了。然而，这个解决方案对数据结构施加了很多限制。更不用说多线程了。 - Björn Pollex

@Space_C0wb0y，没错，这只是另一种表明递归方式最清晰的方法。 - Toon Krijthe

Answer 3

没有提供语言，因此使用伪代码进行举例：

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

请注意这是广度优先遍历，不同于问题中给出的深度优先遍历。你可以通过从nodes列表中pop最后一项而不是shift第一项来进行深度优先遍历。

- Matthew Scharley

---

如果您使用pop而不是shift，那么它将不会是深度优先搜索(DFS)，因为它仍然从根节点开始。DFS从最深的(左)叶子节点开始。 - Marco M.

@MarcoM。OP的解决方案也会搜索根节点，因为它使用尾递归。我认为对于大多数实际应用来说已经足够接近了。 - Matthew Scharley