不使用递归遍历n叉树

Question

如何在不使用递归的情况下遍历

n

二叉树？

递归方式：

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

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

Answer 1

你所做的本质上是树的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);
    }
}

如果您想要其他方式进行遍历，则必须遵循相同的方法，尽管使用不同的数据结构来存储节点。也许是一个优先级队列（如果您想在每个节点评估一个函数，然后根据该值处理节点）。

Answer 2

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

1. 父节点。所以如果你完成了，你可以回到父母那里。

2. 当前子节点，以便您知道下一步要选择哪个。

   • 对于每个节点，您处理所有的孩子。
   • 如果处理了一个孩子，您检查是否有下一个孩子并处理它（更新当前的）。
   • 如果所有孩子都已处理完毕，请返回家长。
   • 如果节点为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;
    }
  }
}

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

请注意，这是广度优先遍历，而不是问题中给出的深度优先遍历。您应该能够通过

pop

删除

nodes

列表中的最后一项而不是

shift

删除第一个项目来进行深度优先遍历。

Answer 4

（1）每个节点有一个“向上”指针，（2）每个节点有一个遍历计数器。您不需要堆栈，因为树本身已经是（或包含）您需要的所有堆栈。

组合器处理程序Combo使用完全非递归树例程，沿着类似的路线。

您只需要注意（如“Combo”源代码中所述），如果您要在并发环境中执行此操作，则需要采取特殊措施。实际上......源代码甚至不使用“向上”指针。我刚刚注意到了。这是你的挑战。尝试在没有“向上”指针的情况下进行操作。