求C++数据结构二叉树的宽度

悠悠 2022-08-18 03:22 100阅读 0赞

/\*之前因为一直自己在想怎么构建二叉树，耽搁了继续去求二叉树的宽度；下面我想谈谈我自己关于怎么去求二叉树的最大宽度的想法

我非常肯定一些大神用各种简单的代码求二叉树的宽度，但是自己想出来的也是挺好的，尽管可能早就有人提到了这个想法，但怎么

去实现，还得好好写代码\*/

/\*首先我们知道，二叉树有先序遍历，后序遍历和中序遍历，层次遍历，我们学校上机老师出题，只考我们前面三个，而且在建树的时候

也算是考了二叉树的遍历，基于老师出的题目，我一直想，是否后面的题目，其思考方向也和前面的题目有关？

后来细想一天，实在不知道怎么用递归思想去求二叉树的宽度，就回头重新看了书本上的部分代码，看到一直被搁置一旁的层次遍历时，

突然想到，既然是层次，那么就可以利用其求宽度：\*/

/\*二叉树的宽度就是树的各层中结点数最大的个数，利用层次遍历求每次层次的结点数，用一个全局变量记录下这些数，便可求出二叉树

的宽度。\*/

在层次遍历的基础上，创建一个替换队列来保存每次清点队列里面的元素个数，然后再把替换队列的元素复制拷贝到层次遍历的队

列元素里面。

下面是核心代码

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;  
\}