谁能指出我的迭代深度优先树遍历的伪代码，其中可以在前序和后序对每个节点执行操作？
也就是说，在进入节点的子节点之前的动作，然后是从子节点上升之后的动作？
另外，我的树不是二元的——每个节点都有 0..n 个子节点。
基本上，我的案例是转换递归遍历，我在当前节点上执行前操作和后操作，递归到子节点的任一侧。
问问题
11888 次
7 回答
13
我的计划是使用两个堆栈。一个用于前序遍历，另一个用于后序遍历。现在，我运行标准迭代 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
}
}
我假设这是一棵树，所以：没有循环，也没有再次访问同一个节点。但是，如果我们愿意，我们总是可以拥有一个访问过的数组并对其进行检查。
于 2015-03-04T21:25:19.613 回答
5
我意识到这篇文章已经有好几年了，但似乎没有一个答案能直接回答这个问题，所以我想我会写一些简单的东西。
这假设一个整数索引图；但是您当然可以根据需要对其进行调整。迭代地执行 DFS 并且仍然具有预排序/后排序操作的关键是，不只是一次追加每个子节点，而是完全像递归 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)
于 2013-11-14T02:47:13.117 回答
3
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 )
于 2011-01-12T01:34:56.213 回答
2
希望对你有帮助。
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++;
}
}
}
于 2013-07-26T07:01:39.283 回答
1
我认为通过将 preProcess 插入 El Mariachi 提供的 postorder 函数，我完全有我需要的东西：
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 )
于 2011-01-12T01:45:14.227 回答
1
一个简单的 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())
于 2015-03-11T12:27:19.547 回答
1
非树图的迭代解决方案
在尝试不同的解决方案失败后，让我为迭代解决方案添加伪代码，在该解决方案中，您实际上是在堆栈变量中重新创建函数调用堆栈空间（在递归版本中可能会溢出）。
您需要存储的所有状态是顶点数和已处理的邻居数。这可以是一个元组、一个列表、一个对象，无论你的语言允许什么。
此解决方案的优点是您不会出现堆栈溢出，它也适用于具有循环的图，并且非常强大。如果使用邻接表或矩阵，获取下一个邻居很容易。
这是伪代码，因为它更容易理解，而且您不会只是从 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
于 2020-03-22T18:59:57.727 回答