在不使用recurrsion的情况下遍历n-ary树

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第一项来进行深度优先遍历.