迭代深度優先樹遍歷與每個節點訪問前後訪問

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())