二叉树层次序遍历 [英] Binary tree level order traversal

问题描述

三种树的遍历是序，preorder和职务序列。

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

第四，不太经常使用，遍历层次序遍历。在一个   一级阶traveresal，D的所有节点的深度之前处理   在深度d + 1。等级序遍历任何节点不同于其他   遍历在于它不完成递归;一个队列时，   而不是递归的隐含堆栈。

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.

我上面的文字片段的问题是

My questions on above text snippet are

1. 为什么级别的顺序遍历的递归不能做？
2. 如何队列用于在一级序遍历？请求澄清伪code会有所帮助。

谢谢！

推荐答案

等级序遍历实际上是一个 BFS ，这是不是递归的性质。它采用队列代替的堆栈以认为应当打开的下一个顶点。其原因正是在这样的穿越，你要打开的节点在 FIFO 秩序，而不是一个的 LIFO 秩序，递归获得

Level order traversal is actually a BFS, which is not recursive by nature. It uses Queue instead of Stack to hold the next vertices that should be opened. The reason for it is in this traversal, you want to open the nodes in a FIFO order, instead of a LIFO order, obtained by recursion

正如我所提到的，级别顺序实际上是一个BFS，其[BFS]伪code [摘自维基百科]是：

as I mentioned, the level order is actually a BFS, and its [BFS] pseudo code [taken from wikipedia] is:

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个不同的路径。

(*) in a tree, marking the vertices is not needed, since you cannot get to the same node in 2 different paths.

这篇关于二叉树层次序遍历的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！