3.10分层遍历二叉树-扩展问题

1.问题定义

给定一棵二叉树，要求按分层遍历该二叉树，即从上到下按层次访问该二叉树(每一层将单独输出一行)，每一层要求访问的顺序为从左到右，并将节点依次编号。要求遍历输出的结果分别为图2，图3和图4，其中图3和图4是扩展问题。

图1 图2 图3 图4

2.原问题

编程之美书上，采用的是容器构成的数组来实现的，相比于递归算法，时间复杂度大大降低，仅为O(n)，但其空间复杂度并非最优。此处采用STL中的Queue来解决此问题，代码如下：

节点数据：

struct node
{
	char value;
	node* pleft;
	node* pright;
};

实现代码：

queue<node*> Queue3;//------------------使用系统的STL的queue
void cengxu3(node* root)
{
	node *temp;
	Queue3.push(root);
	int len=Queue3.size();
	int cur=0;
	while(!Queue3.empty())
	{
		while(cur++<len)//cur++,注意一些小的逻辑
		{
			temp=Queue3.front();
			Queue3.pop();
			cout<<temp->value<<" ";
			if (temp->pleft)
			   Queue3.push(temp->pleft);
			if (temp->pright)
			   Queue3.push(temp->pright);
		}
		cout<<endl;
		cur=0;
		len=Queue3.size();
	}
}

分析总结：

该法中采用队列，将已输出的节点弹出，节省了空间开销，降低了空间复杂度。

对于输出指定行的节点数据，只需引入一个变量保存层数即可，代码如下：

queue<node*> Queue5;
void cengxu_n_ceng(node *root,int ceng)
{
	int cur=0,len=1,cengshu=0;
	Queue5.push(root);
	while(!Queue5.empty())
	{
		while(cur++<len)
		{
			node *temp=Queue5.front();
			Queue5.pop();
			if (cengshu==ceng)
			{
			   cout<<temp->value<<" ";
			}
			if (temp->pleft)
			  Queue5.push(temp->pleft);
			if (temp->pright)
                          Queue5.push(temp->pright);
		}
		if (cengshu==ceng)
		{
                    cout<<endl;
		    return;
		}
		else
		cengshu++;
		cur=0;
		len=Queue5.size();
	}
}

3.扩展问题

图3中的输出顺序刚好是图1中的逆序，先压人栈中，再出栈即可。图4中，每一行的输出顺序和原问题的顺序相同，可压人队列存储，行序和原问题相反，可将每一行作为队列压入栈中。再出栈、出队列输出即可。方便起见，将原问题和扩展图3和图4的扩展问题的代码，编写在一起，如下：

#include "stdafx.h"
#include <iostream>
#include <stdio.h>
#include <string>
#include <queue>
#include <vector>
#include <stack>
using namespace std;
struct node
{
	char value;
	node* pleft;
	node* pright;
};
queue<node*> Queue3;//------------------使用系统的STL的queue
stack<int> Queue3_temp;
stack<queue<node*>> Queue3_tempfan;
void cengxu3(node* root)
{
	node *temp;
	queue<node*> Queue3_fuzhu;
	char temp_value;
	Queue3.push(root);
	Queue3_tempfan.push(Queue3);
	int len=Queue3.size();
	int cur=0;
	while(!Queue3.empty())
	{
		while(cur++<len)//cur++,注意一些小的逻辑、图2的结果
		{
			temp=Queue3.front();
			Queue3_temp.push(temp->value);
			Queue3.pop();
			cout<<temp->value<<" ";
			if (temp->pleft)
			{
				Queue3.push(temp->pleft);
			}
			if (temp->pright)
			{
				Queue3.push(temp->pright);
			}
		}
		Queue3_tempfan.push(Queue3);
		Queue3_temp.push('
');
		cout<<endl;
		cur=0;
		len=Queue3.size();
	}
	while(!Queue3_temp.empty())//图3的结果
	{
		temp_value=Queue3_temp.top();
		Queue3_temp.pop();
		if (temp_value=='
')
		{
                  cout<<temp_value;
		}
		else
                  cout<<temp_value<<" ";
	}

	while(!Queue3_tempfan.empty())//图4的结果
	{
		Queue3_fuzhu=Queue3_tempfan.top();//注意要弹出
		Queue3_tempfan.pop();
		while(!Queue3_fuzhu.empty())
		{
			temp=Queue3_fuzhu.front();
			Queue3_fuzhu.pop();
			cout<<temp->value<<" ";
		}
		cout<<endl;		
	}
}

4.测试结果

采用先序和中序结果重建二叉树（代码见3.9），再对其进行遍历的测试结果如图5所示，前四行分别为先序、中序、后序和层序遍历结果，后面3个三角形分别对应图2、图3、图4中的结果。