Итеративный обход дерева с предварительным и последующим посещением на каждом узле

Question

Может ли кто-нибудь указать мне на псевдокод для итеративного обхода дерева по глубине, где можно выполнять действия на каждом узле как в пред-, так и в пост-порядке ?

То есть, действие до приличного в дочерние узлы, а затем действие после восхождения от детей?

Кроме того, мое дерево не двоично - каждый узел имеет 0..n детей.

В принципе, мой случай преобразует рекурсивный обход, где я делаю пред- и пост-операции на текущем узле с обеих сторон рекурсии в дочерние элементы.

Answer 1

Мой план заключается в использовании двух стеков. Один для предварительного обхода, а другой - для обхода после заказа. Теперь я запускаю стандартный итеративный DFS (первый шаг по пересечению), и как только я pop из «pre» стека, я нажимаю его в стек «пост». В конце мой стек «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

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

Я думаю, что у меня есть именно то, что мне нужно, вставив Preprocess в функцию postorder предоставленной El Mariachi:

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

простая реализация питон с двумя различными посетителями

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