algorithm - 二叉树层次顺序遍历

Question

Three types of tree traversals are inorder, preorder, and post order.

A fourth, less often used, traversal is level-order traversal. In a level-order traveresal, all nodes at depth "d" are processed before any node at depth d + 1. Level-order traversal differs from the other traversals in that it is not done recursively; a queue is used, instead of the implied stack of recursion.

我对以上文本片段的问题是

1. 为什么层序遍历不是递归完成的？
2. 层序遍历如何使用队列？使用伪代码请求澄清会很有帮助。

谢谢!

Answer 1

Level order traversal实际上是一个 BFS , 这本质上不是递归的。它使用 Queue而不是 Stack保存下一个应该打开的顶点。原因是在这个遍历中，你要打开一个FIFO中的节点订单，而不是 LIFO顺序，递归得到

正如我提到的，级别顺序实际上是一个 BFS，其 [BFS] 伪代码 [取自维基百科] 是:

1  procedure BFS(Graph,source):
2      create a queue Q
3      enqueue source onto Q
4      mark source
5      while Q is not empty:
6          dequeue an item from Q into v
7          for each edge e incident on v in Graph:
8              let w be the other end of e
9              if w is not marked:
10                 mark w
11                 enqueue w onto Q

(*) 在树中，不需要标记顶点，因为您无法通过 2 条不同的路径到达同一节点。