按层换行打印二叉树

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

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

基本过程如图所示：

但是，关键是怎么换行？

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

定义两个变量，last 和 nlast 

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

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

步骤：

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

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

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

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

5. 
   

图示过程如下：

先将 1 入队

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

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

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

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

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

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

代码如下：

 #pragma once #include<iostream> #include<cassert> #include<queue> using namespace std; template<class T> struct BinaryTreeNode {	BinaryTreeNode(const T& x)	:_data(x)	, _left(NULL)	, _right(NULL)	{}	T _data;	BinaryTreeNode<T>* _left;	BinaryTreeNode<T>* _right; }; template<class T> class BinaryTree { public:	BinaryTree()	:_root(NULL)	{}	BinaryTree(const T* a, size_t size)	{	size_t index = 0;	_root = _CreateTree(a, size, index);	}	~BinaryTree()	{	_DestroyTree(_root);	_root = NULL;	}	void LevelOrder()  //层次遍历	{	_LevelOrder(_root);  //每层换行！	} protected:	BinaryTreeNode<T>* _CreateTree(const T*& a, size_t size, size_t& index) 	                                                            //创建二叉树	{	assert(a);	BinaryTreeNode<T>* NewNode = NULL;	if (index < size && '#' != a[index])	{	NewNode = new BinaryTreeNode<T>(a[index]);	NewNode->_left = _CreateTree(a, size, ++index);	NewNode->_right = _CreateTree(a, size, ++index);	}	return NewNode;	}	void _DestroyTree(BinaryTreeNode<T>*& root)  //销毁二叉树	{	if (NULL == root)	return;	//后序遍历删除结点	_DestroyTree(root->_left);	_DestroyTree(root->_right);	delete root;	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; }; void Test1() {	int array[] = { 1, 2, 4, '#', '#', '#', 3, 5, 7, '#', '#', 8, '#', '#', 6 };	BinaryTree<int> t1(array, sizeof(array)/sizeof(int));	t1.LevelOrder(); }