原文链接：http://www.cnblogs.com/miloyip/archive/2010/05/12/binary_tree_traversal.html
?
作者叶劲峰正在为博文视点翻译《Game Engine Architecture》一书。
?
之前重温本书写时，也尝试找寻更好的编程解法。今天把另一个问题的实现和大家分享。 给定一棵二叉树，要求按分层遍历该二叉树，即从上到下按层次访问该二叉树(每一层将单独输出一行)，每一层要求访问的顺序为从左到右，并将节点依次编号。下面是一个例子: 输出: 节点的定义: 书上举出两个解法。{dy}个解法是用递归方式，搜寻并打印某一层的节点，再打印下一层的节点。这方法简单但时间效率不高(但不需要额外空间)，因此书中亦提供了第二个解法。 书中第二个解法，使用vector容器来储存n个节点信息，并用一个游标变量last记录前一层的访问结束条件，实现如下: 书中没有提及，本问题其实是以(, BFS)去遍历一个树结构。广度优先搜索的典型实现是使用队列(queue)。其伪代码如下: 书上的解法，事实上也使用了一个队列。但本人认为，使用vector容器，较不直觉，而且其空间复杂度是O(n)。 如果用队列去实现BFS，不处理换行，能简单翻译伪代码为C++代码: 本人觉得这样的算法实现可能比较清楚，而且空间复杂度只需O(m)，m为树中最多节点的层的节点数量。最坏的情况是当二叉树为完整，m = n/2。 之后的难点在于如何换行。 {dy}个尝试，利用了两个队列，一个储存本层的节点，另一个储存下层的节点。遍历本层的节点，把其子代节点排入下层队列。本层遍历完毕后，就可换行，并交换两个队列。 本实现使用deque而不是queue，因为deque才支持swap()操作。注意，swap()是O(1)的操作，实际上只是交换指针。 这实现要用两个循环(书上的实现也是)，并且用了两个队列。能够只用一个循环、一个队列么? 换行问题其实在于如何表达一层的结束。书上采用了游标，而{dy}个尝试则用了两个队列。本人想到第三个可行方案，是把一个结束信号放进队列里。由于使用queue<Node*>，可以插入一个空指针去表示一层的遍历结束。 这个实现的代码很贴近之前的PrintBFS()，也只有一个循环。注意一点，当发现空指针(结束信号)时，要检查队列内是否还有节点，如果没有的话还插入新的结束信号，则会做成死循环。 {dy}个尝试是几个月前做的，没想到今晚写博文又想到了第二个尝试。两个尝试难分优劣，但两种思维或许也可以解决其他问题。还有其他方法么？
1
2 3
4 5 6
7 8
