algorithm - 不使用递归遍历一棵 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);
    }
}

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