algorithm - 在每个节点进行前后访问的迭代深度优先树遍历

Question

谁能指出迭代深度优先树遍历的伪代码，其中可以在前序和后序对每个节点执行操作？

也就是说，在下降到一个节点的子节点之前的一个 Action ，然后是从子节点上升之后的一个 Action ？

此外，我的树不是二叉树 - 每个节点都有 0..n 个子节点。

基本上，我的案例是转换递归遍历，我在当前节点上执行前操作和后操作，递归的任一侧到子节点。

Answer 1

我的计划是使用两个堆栈。一种用于前序遍历，另一种用于后序遍历。 现在，我运行标准的迭代 DFS(深度优先遍历)，一旦我从“pre”堆栈中pop，我就将它插入“post”堆栈。 最后，我的“post”堆栈将在顶部有子节点，在底部有根节点。

treeSearch(Tree root) {
    Stack pre;
    Stack post;
    pre.add(root);
    while (pre.isNotEmpty()) {
        int x = pre.pop();
        // do pre-order visit here on x
        post.add(x);
        pre.addAll(getChildren(x));
    }
    while (post.isNotEmpty()) {
        int y = post.pop();
        // do post-order visit here on y
    }
}

root 将始终从 post 堆栈中最后遍历，因为它将停留在底部。

这是简单的java代码:

public void treeSearch(Tree tree) {
    Stack<Integer> preStack = new Stack<Integer>();
    Stack<Integer> postStack = new Stack<Integer>();
    preStack.add(tree.root);
    while (!preStack.isEmpty()) {
        int currentNode = preStack.pop();
        // do pre-order visit on current node
        postStack.add(currentNode);
        int[] children = tree.getNeighbours(currentNode);
        for (int child : children) {
            preStack.add(child);
        }
    }

    while (!postStack.isEmpty()) {
        int currentNode = postStack.pop();
        // do post-order visit on current node
    }
}

我假设这是一棵树，所以:没有循环并且没有重新访问相同的节点。但是，如果我们愿意，我们始终可以拥有一个已访问数组并对其进行检查。