有人可以给我提供迭代深度优先树遍历的伪代码吗？并且可以在每个节点进行前序和后序操作吗？
也就是说，在下降到节点的子节点之前执行某个操作，然后在从子节点上升后执行另一个操作？
此外，我的树不是二叉树 - 每个节点都有0..n个子节点。
基本上，我的情况是将递归遍历转换为迭代遍历，在递归进入子节点之前和之后对当前节点执行前序和后序操作。
在每个节点进行前序和后序遍历的迭代深度优先树遍历
10
- xeolabs
5
这是一个相当通用的问题，但有着相当具体的要求。不妨询问一下关于迭代遍历的提示 - 前/后操作将会很容易实现。 - Marcus Borkenhagen
听起来像是“有人能向我展示如何迭代数组并在每个元素上执行函数”。按照你描述的一步一步迭代有什么问题吗？ - Nikita Rybak
2每个父元素在访问其子元素之前（前置操作）都需要被访问一次，然后在访问其子元素之后再被访问一次（后置操作）。当我们迭代一个数组时，我们会丢失这个上下文。递归很容易实现，但我不知道如何进行迭代式的实现。 - xeolabs
2树的遍历本质上是递归的。在转换为迭代方法时，仍需要使用自己的堆栈来能够跟踪回到树的顶部。 - moinudin
1我不知道这是否适用，但我曾为一项大学项目做过类似的事情。基本上，这是一个程序，你可以输入一个二进制公式，它会尝试解决它。为此，公式树必须被多次转换，所以我制作了一个系统，在树的每个节点上应用“行者”，从根到叶子。当行者返回非空值时，它将用返回的值替换节点。在此处查看源代码 https://github.com/narrowtux/TIL-project-3/blob/master/src/main/java/de/unikassel/til3/formula/Formula.java#L90 - narrowtux
9个回答
13
我的计划是使用两个栈。一个用于先序遍历，另一个用于后序遍历。 现在，我运行标准的迭代深度优先遍历(DFS)，并且一旦从"pre"栈中弹出，就将其推入"post"栈中。 最后，我的"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
}
}
post 栈中的 root 始终会最后遍历，因为它将保留在底部。
这是简单的 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
}
}
我假设这是一棵树，因此：没有环，也不会重新访问同一个节点。但是，如果需要的话，我们可以始终使用一个visited数组并对其进行检查。
- minhaz
1
2看起来这将首先对所有节点进行预访问，然后进行后访问，但是如果需要在下一个兄弟的前访问之前进行子级的后访问，则无法正常工作。 - Creak
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)
- jamie
1
太棒了。感谢您真正考虑到我的前/后操作核心要求。 - xeolabs
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 )
- El Mariachi
1
将其应用于一般图的DFS，而不是树的DFS，难度大吗？它不能像现在这样工作，因为在一般图中，“a_node”可能在“visited”中而不是父节点。 - max
3
非树形图的迭代解决方案
在尝试了不同的解决方案后，让我添加一个迭代解决方案的伪代码，其中你基本上重新创建了函数调用堆栈空间（在递归版本中可能会溢出），并将其保存在一个堆栈变量中。
你需要存储的所有状态都是顶点编号和已处理邻居的数量。这可以是元组、列表、对象或任何你的语言允许的东西。
这种解决方案的优点是你不会遇到堆栈溢出问题，它也适用于具有循环的图表，而且相当健壮。如果使用邻接列表或矩阵，则很容易获得下一个邻居。
这是伪代码，因为它更容易理解，你不会只从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
- gombosg
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++;
}
}
}
- Vasily
1
我认为通过在El Mariachi提供的后序函数中插入preProcess，我已经得到了我需要的东西：
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 )
- xeolabs
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())
- stefan
1
1它可以工作，但它不再是迭代的了（如作者的问题所要求的）。 - Creak
0
另一种变化，允许将所有子节点一次性推入堆栈，只需要进行最少的状态跟踪。
请注意，它与原始递归遍历产生不同的结果，因为它以相反的顺序进入相邻边。如果这是一个问题，您可以在将它们推入堆栈之前反转邻居列表。
private void TraverseDepthFirst(Node entryNode, Action<Node>? preVisit = null, Action<Node>? postVisit = null)
{
var worklist = new Stack<(Node node, bool entered)>();
var visited = new HashSet<Node>(); //not necessary for trees/acyclic-graphs.
worklist.Push((entryNode, false));
visited.Add(entryNode);
while (worklist.Count > 0) {
var (node, entered) = worklist.Pop();
if (!entered) {
worklist.Push((node, true));
preVisit?.Invoke(node);
foreach (var neighbor in node.Neighbors) {
if (visited.Add(neighbor)) {
worklist.Push((neighbor, false));
}
}
} else {
postVisit?.Invoke(node);
}
}
}
- user20361255
0
对于需要在下一个兄弟节点的预访问之前进行子节点的后访问的解决方案，可以参考@Creak提到的方法（C#）：
public void DepthFirstTraversal2(Node root)
{
Stack<Node> stack = new Stack<Node>();
HashSet<Node> visited = new HashSet<Node>();
stack.Push(root);
while (stack.TryPeek(out var node))
{
if (!visited.Contains(node))
{
visited.Add(node);
Console.WriteLine($"Pre-visit node {node.Value}");
foreach (Node child in node.Children)
{
stack.Push(child);
}
}
else
{
stack.Pop();
Console.WriteLine($"Post-visit node {node.Value}");
}
}
}
- Martin Cohen
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接