题目描述： 二叉树，按层打印，并且每层换行


分析： 我们知道，二叉树的层序遍历需要借助队列来实现，每取出一个节点打印，并将该节点的左右孩子放入队列中，依此反复，直到队列为空时，也就完成了二叉树的按层打印。


基本过程如图所示：

但是，关键是怎么换行？


分析：要换行则需要知道什么时候换行，由二叉树我们可以分析，我们需要知道每一层最右边的节点，每次打印完这个节点的值后，再打印一个换行即可。于是我们这样做：


定义两个变量，last 和 nlast

last : 表示正在打印的当前行的最右节点

nlast : 表示下一行的最右节点


步骤：

开始让 last 等于二叉树的根节点，并将其点放入队列中。

队头节点出队列，并打印，将该节点的左孩子入队，并让 nlast 等于该节点，将该节点的右孩子入队，并让 nlast 等于该节点。

如果打印的节点等于 last 当前指向的节点，则打印一次换行，同时让 last 等于 nlast。

重复步骤2,3，知道队列为空为止。


图示过程如下：

先将 1 入队

再将 1 出队，并将 2 ，3 入队，并让 nlast 分别指向 2， 3


此时发现，出队列的节点与 last 指向的节点相等，此时，打印换行符。同时让 last 等于 nlast

重复上述步骤，将 2 出队列，并将 4 入队列，让 nlast 指向 4

再将 3 出队列，并将 5,6 入队列，让 nlast 分别指向 5,6 ，此时发现3 等于 last ，则再打印一次换行，并让 last 等于 nlast



重复上述步骤，最终结果如下：

这样，按层换行打印二叉树就完成啦！


代码如下：

#pragmaonce#include<iostream>#include<cassert>#include<queue>usingnamespacestd;template<classT>structBinaryTreeNode{BinaryTreeNode(constT&x):_data(x),_left(NULL),_right(NULL){}T_data;BinaryTreeNode<T>*_left;BinaryTreeNode<T>*_right;};template<classT>classBinaryTree{public:BinaryTree():_root(NULL){}BinaryTree(constT*a,size_tsize){size_tindex=0;_root=_CreateTree(a,size,index);}~BinaryTree(){_DestroyTree(_root);_root=NULL;}voidLevelOrder()//层次遍历{_LevelOrder(_root);//每层换行！}protected:BinaryTreeNode<T>*_CreateTree(constT*&a,size_tsize,size_t&index)//创建二叉树{assert(a);BinaryTreeNode<T>*NewNode=NULL;if(index<size&&'#'!=a[index]){NewNode=newBinaryTreeNode<T>(a[index]);NewNode->_left=_CreateTree(a,size,++index);NewNode->_right=_CreateTree(a,size,++index);}returnNewNode;}void_DestroyTree(BinaryTreeNode<T>*&root)//销毁二叉树{if(NULL==root)return;//后序遍历删除结点_DestroyTree(root->_left);_DestroyTree(root->_right);deleteroot;root=NULL;}void_LevelOrder(BinaryTreeNode<T>*&root){if(NULL==root)return;std::queue<BinaryTreeNode<T>*>q;q.push(root);BinaryTreeNode<T>*last=root;BinaryTreeNode<T>*nlast=NULL;while(!q.empty()){BinaryTreeNode<T>*cur=q.front();cout<<cur->_data<<"";q.pop();if(cur->_left){q.push(cur->_left);nlast=cur->_left;}if(cur->_right){q.push(cur->_right);nlast=cur->_right;}if(cur==last){cout<<endl;last=nlast;}}cout<<endl;}protected:BinaryTreeNode<T>*_root;};voidTest1(){intarray[]={1,2,4,'#','#','#',3,5,7,'#','#',8,'#','#',6};BinaryTree<int>t1(array,sizeof(array)/sizeof(int));t1.LevelOrder();}