Cruce iterativo de árbol en profundidad con visita previa y posterior en cada nodo

Question

¿Alguien me puede señalar en pseudocódigo para el cruce iterativo de árboles en profundidad, donde es posible realizar acciones en cada nodo tanto antes como después de la orden ?

Es decir, una acción antes de la decencia en los hijos de un nodo, luego una acción después del ascenso de los niños?

Además, mi árbol no es binario: cada nodo tiene 0..n hijos.

Básicamente, mi caso está transformando un recorrido recursivo, donde hago las operaciones previas y posteriores en el nodo actual, cualquier lado de la recursión en los niños.

Answer 1

Mi plan es utilizar dos pilas. Uno para el recorrido previo a la orden y el otro para el recorrido posterior al pedido. Ahora, ejecuto DFS iterativo estándar (recorrido transversal en profundidad), y tan pronto como I pop de la pila "pre" lo empujo en la pila "publicar". Al final, mi pila de "publicaciones" tendrá un nodo hijo en la parte superior y una raíz en la parte inferior.

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 siempre ser recorridos duran de post pila, ya que se quedará en la parte inferior.

Esto es simple código 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 
    } 
} 

estoy asumiendo que esto es un árbol, por lo que: ningún ciclo y sin volver a visitar el mismo nodo nuevo. Pero, si queremos, siempre podemos tener una matriz visitada y verificar eso.

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

creo que tengo exactamente lo que necesito insertando un preproceso en la función de orden posterior proporcionada por 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

espero que les sea útil.

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

Código:

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

Soy consciente de que este post es de hace varios años, pero ninguna de las respuestas parecen responder directamente a la pregunta, así que pensé que me gustaría escribir algo algo simple .

Esto supone un gráfico indexado entero; pero ciertamente puedes adaptarlo según sea necesario. La clave para realizar DFS de forma iterativa y aún tener operaciones de preordenar/post orden es NO anexar cada hijo a la vez, sino que se comporta exactamente como DFS recursivo, que agrega solo un nodo hijo a la pila a la vez, y solo eliminarlos de la pila una vez que haya terminado. Lo logro en mi ejemplo creando un nodo envoltorio con la lista de adyacencia como una pila. Basta con omitir la comprobación de ciclo si desea permitir a los ciclos (que no atraviesa los nodos visitados de todos modos, por lo que todavía funciona)

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

una sencilla aplicación de pitón con dos visitantes diferentes

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