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

Question

任何人都可以伪代码指向我进行迭代深度优先树遍历，可以在前后顺序对每个节点执行操作？

也就是说，一个行动体面地进入一个节点的孩子，然后从孩子上升后的行动？

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

基本上，我的情况正在改变一个递归遍历，我在当前节点上执行前后操作，递归到子节点的任一侧。

Answer 1

我的计划是使用两个栈。一个用于预订遍历，另一个用于后序遍历。 现在，我运行标准迭代DFS（深度优先遍历），并且只要我从“pre”堆栈中将它推入“post”堆栈中。 最后，我的“帖子”堆栈的顶部是子节点，底部是root。

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

class Node: 
    def __init__(self, value): 
    self.value = value 
    self.children = [] 

def preprocess(node): 
    print(node.value) 

def postprocess(node): 
    print(node.value) 

def preorder(root): 
    # Always a flat, homogeneous list of Node instances. 
    queue = [ root ] 
    while len(queue) > 0: 
    a_node = queue.pop(0) 
    preprocess(a_node) 
    queue = a_node.children + queue 

def postorder(root): 
    # Always a flat, homogeneous list of Node instances: 
    queue = [ root ] 
    visited = set() 
    while len(queue) > 0: 
    a_node = queue.pop(0) 
    if a_node not in visited: 
     visited.add(a_node) 
     queue = a_node.children + [ a_node ] + queue 
    else: 
     # this is either a leaf or a parent whose children have all been processed 
     postprocess(a_node) 

Answer 3

我觉得我有什么，我需要通过将预处理成杀手悲歌提供的后序功能：

def postorder(root): 
# Always a flat, homogeneous list of Node instances: 
queue = [ root ] 
visited = set() 
while len(queue) > 0: 
    a_node = queue.pop(0) 
    if a_node not in visited: 
    preprocess(a_node)     # <<<<<<<< Inserted 
    visited.add(a_node) 
    queue = a_node.children + [ a_node ] + queue 
    else: 
    # this is either a leaf or a parent whose children have all been processed 
    postprocess(a_node) 

Answer 4

我希望你觉得它有用。

http://www.vvlasov.com/2013/07/post-order-iterative-dfs-traversal.html

代码：

public void dfsPostOrderIterative(AdjGraph graph, AdjGraph.Node vertex, Callback callback) { 
    Stack<Level> toVisit = new Stack<Level>(); 
    toVisit.push(new Level(Collections.singletonList(vertex))); 

    while (!toVisit.isEmpty()) { 
     Level level = toVisit.peek(); 

     if (level.index >= level.nodes.size()) { 
      toVisit.pop(); 
      continue; 
     } 

     AdjGraph.Node node = level.nodes.get(level.index); 

     if (!node.isVisited()) { 
      if (node.isChildrenExplored()) { 
       node.markVisited(); 
       callback.nodeVisited(graph, node); 
       level.index++; 
      } else { 
       List<AdjGraph.Node> edges = graph.edges(node); 
       List<AdjGraph.Node> outgoing = Lists.newArrayList(Collections2.filter(edges, new Predicate<AdjGraph.Node>() { 
        @Override 
        public boolean apply(AdjGraph.Node input) { 
         return !input.isChildrenExplored(); 
        } 
       })); 

       if (outgoing.size() > 0) 
        toVisit.add(new Level(outgoing)); 
       node.markChildrenExplored(); 
      } 
     } else { 
      level.index++; 
     } 
    } 
} 

Answer 5

我知道这个帖子是几年前的，但没有一个答案似乎直接回答这个问题，所以我想我会写一些东西有点简单。

这里假设一个整数索引图;但你可以根据需要进行调整。迭代地执行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) 

Answer 6

一个简单的Python实现两种不同的游客

class Print_visitor(object): 
    def __init__(self): 
     pass 
    def pre_visit(self, node): 
     print "pre: ", node.value 
    def post_visit(self, node): 
     print "post:", node.value 

class Prettyprint_visitor(object): 
    def __init__(self): 
     self.level=0 
    def pre_visit(self, node): 
     print "{}<{}>".format(" "*self.level, node.value) 
     self.level += 1 
    def post_visit(self, node): 
     self.level -= 1 
     print "{}</{}>".format(" "*self.level, node.value) 

class Node(object): 
    def __init__(self, value): 
     self.value = value 
     self.children = [] 
    def traverse(self, visitor): 
     visitor.pre_visit(self) 
     for child in self.children: 
      child.traverse(visitor) 
     visitor.post_visit(self) 

if __name__ == '__main__': 
    #test 
    tree = Node("root") 
    tree.children = [Node("c1"), Node("c2"), Node("c3")] 
    tree.children[0].children = [Node("c11"), Node("c12"), Node("c13")] 
    tree.children[1].children = [Node("c21"), Node("c22"), Node("c23")] 
    tree.children[2].children = [Node("c31"), Node("c32"), Node("c33")] 
    tree.traverse(Print_visitor()) 
    tree.traverse(Prettyprint_visitor())