Attraversamento iterativo traverso di profondità con pre e post-visita su ciascun nodo

Question

Qualcuno può indicarmi lo pseudocodice per l'attraversamento iterativo di profondità prima dell'albero, in cui è possibile eseguire azioni su ciascun nodo in entrambi i casi pre- e post-ordine ?

Cioè, un'azione prima decente nei figli di un nodo, quindi un'azione dopo la risalita dai bambini?

Inoltre, il mio albero non è binario - ogni nodo ha 0..n bambini.

Fondamentalmente, il mio caso sta trasformando un attraversamento ricorsivo, dove eseguo le operazioni pre e post sul nodo corrente, entrambi i lati della ricorsione nei bambini.

Answer 1

Il mio piano è quello di utilizzare due pile. Uno per attraversare il preordine e un altro per attraversare il post-ordine. Ora eseguo DFS iterativo standard (deep-first traversal), e non appena I pop dallo stack "pre" lo sposto nello stack "post". Alla fine, il mio stack "post" avrà il nodo figlio in alto e radice in basso.

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 sarà sempre attraversati da ultimo post pila come rimarrà sul fondo.

Questo è semplice codice 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 
    } 
} 

sto presupponendo che questo è un albero, così: alcun ciclo e senza rivisitare stesso nodo nuovo. Ma, se vogliamo, possiamo sempre avere un array visitato e controllarlo.

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

penso di avere esattamente quello che mi serve con l'inserimento di una pre-elaborazione nella funzione postorder fornita da 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

Spero vi sia utile.

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

Codice:

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

Mi rendo conto che questo post è di diversi anni, ma nessuna delle risposte sembrano rispondere direttamente alla domanda, così ho pensato che avrei scritto qualcosa un po 'semplice .

Questo presuppone un numero intero di indice; ma puoi certamente adattarlo se necessario. La chiave per fare in modo iterativo DFS e avere ancora le operazioni di pre-ordine/post-ordinazione NON è solo aggiungere ogni bambino in una sola volta, ma invece comportarsi esattamente come farebbe DFS ricorsivo, che sta aggiungendo solo un nodo figlio allo stack alla volta e rimuovendoli dallo stack una volta terminato. Realizzo questo nel mio esempio creando un nodo wrapper con l'elenco di adiacenze come stack. Basta omettere il controllo del ciclo, se si desidera consentire cicli (non attraversare nodi visitati comunque, quindi continuerà a funzionare)

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

un'implementazione semplice pitone con due diversi visitatori

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