Can anyone point me at pseudocode for iterative depth-first tree traversal, where it's possible to do actions on each node at both pre- and post- order?

That is, an action before descent into a node's children, then an action after ascent from the children?

Also, my tree is not binary - each node has 0..n children.

Basically, my case is transforming a recursive traversal, where I do the pre- and post- operations on the current node, either sid开发者_运维技巧e of the recursion into the children.

My plan is to use two stacks. One for pre-order traversal and another one is for post-order traversal. Now, I run standard iterative DFS (depth-first traversal), and as soon as I pop from the "pre" stack i push it in "post" stack. At the end, my "post" stack will have child node at top and and root at bottom.

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 will always be traversed last from post stack as it will stay at the bottom.

This is simple java code:

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
    }
}

I am assuming this is a tree, so: no cycle and no revisiting the same node again. But, if we want we can always have a visited array and check against that.

I realize this post is several years old, but none of the answers seem to directly answer the question, so I figured I'd write up something somewhat simple.

This assumes an integer indexed graph; but you can certainly adapt it as necessary. The key to doing DFS iteratively and still having pre-order/post-order operations is to NOT just append every child at once, but instead, behave exactly as recursive DFS would, which is adding just one child-node to the stack at a time, and only removing them from the stack once it has finished. I accomplish this in my example by creating a wrapper node with the adjacency list as a stack. Just omit the cycle check if you wish to allow cycles (it doesn't traverse visited nodes anyway, so it will still work)

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)

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 )

I hope you find it useful.

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

Code:

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++;
        }
    }
}

I think I have exactly what I need by inserting a preProcess into the postorder function provided by 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 )

a simple python implementation with two different visitors

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

Iterative solution for non-tree graphs

After unsuccessfully experimenting with different solutions, let me add pseudocode for an iterative solution where you essentially recreate the function call stack space (that could overflow in a recursive version) in a stack variable.

All the state that you need to store is the vertex number and the number of neighbors already processed. This can be a tuple, a list, an object, whatever your language allows.

The advantage of this solution is that you don't get stack overflow, it also works for graphs having cycles and it's pretty robust. Getting the next neighbor is easy if you use an adjacency list or matrix.

This is pseudocode because it's easier to understand, and you wouldn't just copy code from SO, would you?

globals: isProcessed, preOrder, postOrder

depthFirstSearch()
    set isProcessed to all false
    for each vertex
        if !isProcessed(vertex)
            explore(vertex)

explore(root)
    create stack
    add (root, 0) to stack
    visited = empty list 
        // a list of visited vertices e.g. for finding connected components

    while stack is not empty
        (vertex, processedNeighbors) ← pop from stack

        if !isProcessed(vertex)
            // previsit
            add vertex to preOrder list
            isProcessed(vertex) ← true

        if processedNeighbors < number of vertex's neighbors
            nextNeighborNumber ← processedNeighbors + 1
            push (vertex, nextNeighborNumber) to stack
            nextNeighbor ← 'nextNeighborNumber'th neighbor of vertex

            if !isProcessed(nextNeighbor)
                push (nextNeighbor, 0) to stack
        else
            // postvisit
            add vertex to postOrder list