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

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

Я понимаю, что этому посту уже несколько лет, но ни один из ответов не дает прямого ответа на вопрос, поэтому я решил написать что-то несколько простое.

Это предполагает граф с целочисленным индексом; но вы, конечно, можете адаптировать его по мере необходимости. Ключом к итеративному выполнению DFS и сохранению операций предварительного/последующего заказа является НЕ простое добавление каждого дочернего элемента сразу, а вместо этого поведение точно так же, как рекурсивный DFS, то есть добавление только одного дочернего элемента. -node в стек за раз и удаляя их из стека только после его завершения. В моем примере я достигаю этого, создавая узел-оболочку со списком смежности в виде стека. Просто пропустите проверку цикла, если вы хотите разрешить циклы (он все равно не проходит через посещенные узлы, поэтому он все равно будет работать)

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)

Я надеюсь, что вы найдете это полезным.

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

Я думаю, что у меня есть именно то, что мне нужно, вставив предварительный процесс в функцию постзаказа, предоставленную Эль Мариачи:

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 )

простая реализация 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())

Итеративное решение для графов, не являющихся деревьями

После безуспешных экспериментов с различными решениями позвольте мне добавить псевдокод для итеративного решения, в котором вы по существу воссоздаете пространство стека вызовов функций (которое может переполниться в рекурсивной версии) в переменной стека.

Все состояние, которое вам нужно сохранить, — это номер вершины и количество уже обработанных соседей. Это может быть кортеж, список, объект — все, что позволяет ваш язык.

Преимущество этого решения в том, что вы не получаете переполнения стека, оно также работает для графов, содержащих циклы, и оно довольно надежное. Получить следующего соседа легко, если вы используете список смежности или матрицу.

Это псевдокод, потому что его легче понять, и вы бы не стали просто копировать код из SO, не так ли?

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