本文共 1625 字，大约阅读时间需要 5 分钟。

题型：二叉树的按层遍历

1.针对二叉树的宽度优先遍历

2.宽度优先遍历常使用队列结构

3.面试中，改题目经常对换行有所要求

具体实例：

给定一棵二叉树的头结点head，请按照大家现在看到的方式打印

1

2 3

4 5 6

7 8

此题的思考点在于如何打印换行

用两个变量来解决问题：

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

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

所以，采用宽度优先遍历的方式来遍历二叉树，当遍历的点为last所指向的节点时，打印换行，使得last = nlast。

现在，我们的问题变为了如何正确更新last和nlast 的值

正确方法是：nlast始终指向最新进入队列的节点

以上题实例为例：

1. last指向1节点，1节点进入队列，nlast指向1节点
2. 检查队列是否为空，若是，则跳出循环，结束打印。否则队头节点出队列，打印节点
3. 检查当前打印的节点是否有左孩子，若有，进入队列，使得nlast指向这个左孩子
4. 检查当前打印的节点是否有右孩子，若有，进入队列，使得nlast指向这个右孩子
5. 检查当前打印的节点是否是last指向的节点，若是，打印换行，更新last节点 last  = nlast
6. 进入第二步

代码如下：

#include
   
    #include
    
     using namespace std;struct node{	node(int num)	{		data = num;		left = NULL;		right = NULL;	}	int data;	struct node *left;	struct node *right;};int main(){	//创建二叉树	node elem1 = node(1);	node elem2 = node(2);	node elem3 = node(3);	node elem4 = node(4);	node elem5 = node(5);	node elem6 = node(6);	node elem7 = node(7);	node elem8 = node(8);	elem1.left = &elem2;	elem1.right = &elem3;	elem2.left = &elem4;	elem3.left = &elem5;	elem3.right = &elem6;	elem5.left = &elem7;	elem5.right = &elem8;	node *last = NULL;  //指向正在打印的当前行的最右行节点	node *nlast = NULL;  //指向下一行的最右节点	node * p = NULL;	queue
     
       qu;  //定义队列sk用于宽度优先遍历	last = &elem1;	qu.push(&elem1);  //把节点1入队列	nlast = &elem1;	while (!qu.empty())	{		p = qu.front();		qu.pop();    //取队头节点出队列		cout << p->data;     //打印节点		//检测当前打印节点是否有左孩子，若有，入队列，更新nlast		if (NULL != p->left)		{			qu.push(p->left);			nlast = p->left;		}		//检测当前打印节点是否有右孩子，若有，入队列，更新nlast		if (NULL != p->right)		{			qu.push(p->right);			nlast = p->right;		}		if (p == last) //检查当前节点是否是last指向的节点，若是，打印换行,更新last		{			cout << endl;			last = nlast;		}		}	return 0;}