algorithm - 不使用递归遍历 n 叉树

Question

如何在n不使用递归的情况下遍历 -ary 树？

递归方式：

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

请注意，这是与问题中给出的深度优先遍历相反的广度优先遍历。您应该能够通过ing列表中pop的最后一项而不是第一项来进行深度优先遍历。nodesshift