迭代深度优先树遍历每个节点的访问前和访问后

Question

任何人都可以指出我在伪代码中进行迭代深度优先树遍历,在这种情况下,可以在订单前后对每个节点执行操作吗？

也就是说,在进入节点的孩子之前的行动,然后是从孩子们上升后的行动？

此外,我的树不是二进制 - 每个节点有0..n个孩子.

基本上,我的情况是转换递归遍历,我在当前节点上执行前后操作,在递归到子节点的任一侧.

Answer 1

我的计划是使用两个堆栈.一个用于预订遍历,另一个用于后序遍历.现在,我运行标准迭代DFS(深度优先遍历),并且只要我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
    }
}

我假设这是一棵树,所以:没有循环,也没有重新访问同一个节点.但是,如果我们想要,我们总是可以拥有一个访问过的数组并检查它.

Answer 2

我意识到这篇文章已经有好几年了,但没有一个答案似乎直接回答了这个问题,所以我想我会写一些简单的东西.

这假设一个整数索引图; 但你必须根据需要调整它.迭代地执行DFS并且仍然具有预订/后序操作的关键是不要只是一次追加每个子节点,而是像递归DFS那样行为,这只是在堆栈中添加一个子节点.时间,只有在完成后才从堆栈中删除它们.我在我的示例中通过创建一个包含邻接列表作为堆栈的包装器节点来实现此目的.如果您希望允许循环,则省略循环检查(无论如何它都不会遍历被访问的节点,因此它仍然可以工作)

class Stack(object):
    def __init__(self, l=None):
        if l is None:
            self._l = []
        else:
            self._l = l
        return

    def pop(self):
        return self._l.pop()

    def peek(self):
        return self._l[-1]

    def push(self, value):
        self._l.append(value)
        return

    def __len__(self):
        return len(self._l)

class NodeWrapper(object):
    def __init__(self, graph, v):
        self.v = v
        self.children = Stack(graph[v])
        return

def iterative_postorder(G, s):
    onstack = [False] * len(G)
    edgeto = [None] * len(G)
    visited = [False] * len(G)

    st = Stack()
    st.push(NodeWrapper(G, s))

    while len(st) > 0:
        vnode = st.peek()
        v = vnode.v
        if not onstack[v]:
            print "Starting %d" % (v)
        visited[v] = True
        onstack[v] = True
        if len(vnode.children) > 0:
            e = vnode.children.pop()
            if onstack[e]:
                cycle = [e]
                e = v
                while e != cycle[0]:
                    cycle.append(e)
                    e = edgeto[e]
                raise StandardError("cycle detected: %s, graph not acyclic" % (cycle))
            if not visited[e]:
                edgeto[e] = v
                st.push(NodeWrapper(G, e))
        else:
            vnode = st.pop()
            onstack[vnode.v] = False
            print 'Completed %d' % (vnode.v)