有人可以在深度优先的遍历树遍历的伪代码中指向我，在伪代码中可以对每个节点进行前后排序吗？
也就是说，是在对一个节点的子节点进行正当操作之前，然后是从这些子节点提升后的操作？
而且，我的树不是二叉树-每个节点都有0..n个子节点。
[基本上，我的情况是转换递归遍历，在该过程中，我在当前节点上进行前和后操作，将递归的任一端都放入子节点中。
我的计划是使用两个堆栈。一个用于前遍历，另一个用于后遍历。现在，我运行标准的迭代DFS（深度优先遍历），并且当我从“前”堆栈中将pop推送到“后”堆栈中时。最后，我的“ post”堆栈将在顶部具有子节点，在底部具有root。
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并仍具有前顺序/后顺序操作的关键是不只是立即附加every子代，而是要完全像递归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)
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 )
我想通过将PreProcess插入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 )
希望您觉得它有用。
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++;
}
}
}
具有两个不同访问者的简单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())