/*之前因为一直自己在想怎么构建二叉树，耽搁了继续去求二叉树的宽度；下面我想谈谈我自己关于怎么去求二叉树的最大宽度的想法
我非常肯定一些大神用各种简单的代码求二叉树的宽度，但是自己想出来的也是挺好的，尽管可能早就有人提到了这个想法，但怎么
去实现，还得好好写代码*/
/*首先我们知道，二叉树有先序遍历，后序遍历和中序遍历，层次遍历，我们学校上机老师出题，只考我们前面三个，而且在建树的时候
也算是考了二叉树的遍历，基于老师出的题目，我一直想，是否后面的题目，其思考方向也和前面的题目有关？
后来细想一天，实在不知道怎么用递归思想去求二叉树的宽度，就回头重新看了书本上的部分代码，看到一直被搁置一旁的层次遍历时，
突然想到，既然是层次，那么就可以利用其求宽度：*/
/*二叉树的宽度就是树的各层中结点数最大的个数，利用层次遍历求每次层次的结点数，用一个全局变量记录下这些数，便可求出二叉树
的宽度。*/
在层次遍历的基础上，创建一个替换队列来保存每次清点队列里面的元素个数，然后再把替换队列的元素复制拷贝到层次遍历的队
列元素里面。
下面是核心代码
void GetWidth(BiNode<T> *t) //利用广度优先遍历来算各个层的宽度
{
using std::queue;
int Maxwidth=0;//当前的最大宽度Maxwidth
int width=1;//当前的宽度width
queue<BiNode<T>*>nodeQueue; //待访问的结点的队列
queue<BiNode<T>*>ChangenodeQueue; //计算队列元素个数替换队列
BiNode*pointer=t; //保存根结点
if(pointer)//根结点非空，根结点入队
nodeQueue.push(pointer);
int i=0;
while(!nodeQueue.empty()) //队列为空时结束
{
width=0;
//计算队列元素个数
while(!nodeQueue.empty())
{
width++;
ChangenodeQueue.push(nodeQueue.front()); //把层次遍历的元素复制拷贝到替换队列里面
nodeQueue.pop(); //当结束的时候，nodeQueue队列里面的元素个数为零
}
if(width>Maxwidth)Maxwidth=width; //记录最大的宽度
//备用的队列ChangenodeQueue的元素返回待访问结点的队列nodeQueue
while(!ChangenodeQueue.empty())
{
nodeQueue.push(ChangenodeQueue.front());
ChangenodeQueue.pop();
}
for(i=0;i<1;i++)
{
pointer=nodeQueue.front(); //读取队首结点
cout<<pointer->data;
nodeQueue.pop(); //访问过的结点移出队列
//将访问过的结点的非空左右孩子入队列
if(pointer->lchild)
nodeQueue.push(pointer->lchild);
if(pointer->rchild)
nodeQueue.push(pointer->rchild);
}
}
cout<<Maxwidth;//输出树的宽度
}
具体的代码实现如下：
#include<string>
#include<iostream>
#include<queue>
using namespace std;
//二叉链表表示二叉树
template<class T>
class BiNode
{
public:
T data;//节点数据
BiNode * lchild;//左孩子
BiNode * rchild;//右孩子
BiNode();
BiNode(T d){ data=d; } //new一个结点的时候就给其数据域赋值
~BiNode(){}
void createTree(BiNode<T>* &t, string pre,string in) //后序，中序
{
if(pre.length()==0)
{
t=NULL;
}
if(pre.length()!=0)
{
t=new BiNode<T>(pre[0]);
int index=in.find(pre[0]);
string in_left_str=in.substr(0, index);
string in_right_str=in.substr(index+1);
string pre_left_str=pre.substr(1, index);
string pre_right_str=pre.substr(index+1);
if(t!=NULL)
{
createTree(t->lchild,pre_left_str,in_left_str);
createTree(t->rchild,pre_right_str,in_right_str);
}
}
}
void GetWidth(BiNode<T> *t) //利用广度优先遍历来算各个层的宽度
{
using std::queue;
int Maxwidth=0;//当前的最大宽度Maxwidth
int width=1;//当前的宽度width
queue<BiNode<T>*>nodeQueue; //待访问的结点的队列
queue<BiNode<T>*>ChangenodeQueue; //计算队列元素个数是的替换队列
BiNode*pointer=t; //保存根结点
if(pointer)//根结点非空，根结点入队
nodeQueue.push(pointer);
int i=0;
while(!nodeQueue.empty()) //队列为空时结束
{
width=0;
//计算队列元素个数
while(!nodeQueue.empty())
{
width++;
ChangenodeQueue.push(nodeQueue.front());
nodeQueue.pop();
}
if(width>Maxwidth)Maxwidth=width; //记录最大的宽度
//备用的队列ChangenodeQueue的元素返回待访问结点的队列nodeQueue
while(!ChangenodeQueue.empty())
{
nodeQueue.push(ChangenodeQueue.front());
ChangenodeQueue.pop();
}
for(i=0;i<1;i++)
{
pointer=nodeQueue.front(); //读取队首结点
cout<<pointer->data;
nodeQueue.pop(); //访问过的结点移出队列
//将访问过的结点的左右非空孩子入队列
if(pointer->lchild)
nodeQueue.push(pointer->lchild);
if(pointer->rchild)
nodeQueue.push(pointer->rchild);
}
}
cout<<Maxwidth;//输出树的宽度
}
};
int main()
{
BiNode<char> *t=NULL; //定义树的根结点的指针
string pre="ABDFGCEH"; //前序
string in="BFDGACEH"; //中序
t->createTree(t,pre,in); //建树
t->GetWidth(t); //求最大宽度并输出
cout<<endl;
return 0;
}