algorithm - 树遍历以层次优先顺序和深度优先顺序递归

Question

有没有什么算法可以先递归遍历树，后序非递归遍历。非常感谢。

Answer 1

要获得有效的递归广度优先搜索，您可以使用 iterative deepening depth-first search .它特别适用于分支因子较高的情况，在这种情况下，常规广度优先搜索往往会因内存消耗过多而窒息。

编辑: Marcos Marin already mentioned it ，但为了完整起见，the Wikipedia page on breadth-first traversal如此描述算法:

1. Enqueue the root node.
2. Dequeue a node and examine it.
   • If the element sought is found in this node, quit the search and return a result.
   • Otherwise enqueue any successors (the direct child nodes) that have not yet been discovered.
3. If the queue is empty, every node on the graph has been examined – quit the search and return "not found".
4. Repeat from Step 2.

Note: Using a stack instead of a queue would turn this algorithm into a depth-first search.

如果您想进行非递归深度优先遍历，那么最后一行显然对您很有趣。获得预购或后购只是修改您在步骤 2.b 中附加节点的方式的问题。