二叉树采用二叉链表存储:编写计算二叉树最大宽度的算法
(二叉树的最大宽度是指二叉树所有层中结点个数的最大值)
和二叉树有关的代码,基本都逃不过“先中后层”,这四种遍历
而我们这里是让你计算最大宽度,它是横着来的,那我们就可以断定是要用到层序遍历了
对层序遍历不熟悉的,可以看我这篇文章光速上手二叉树层序遍历
代码思路:
首先我们有如下的树,和一个空队列,用一个变量max记录最大宽度
所谓的计算最大宽度,不就是让你在进行层序遍历的时候多统计一下每层的数目吗?
那我们可以用一个point值记录当前队列里面还有多少元素,然后point依次- -,出队头,入队头左右孩子,当point结束一轮,也就是point到0的时候,那么上一层元素全部清除,下一层元素全部到队列中,这时候你统计max和当前队列长度哪个更大,就是新的max
注:每次我们用point记录当前队列有多少元素,然后point依次- -直到point=0,是把这一层的元素全部出掉,换成下一层元素,这样就可以保证我们每次统计到的都是一层的宽度。
举例说明:
第一层遍历:
根节点A入队,此时队列中只有一个元素A,那么point=队列长度=1
一开始max=0,0<1,所以max更新为1
此时point=1>0,说明下一层还没有完全进队列
point–,A左右孩子入队,
point=0,说明第一层遍历结束
第二层遍历:
用point记录当前队列长度,point=2
max也更新为2
然后point依次- -
point=1,B出队,B左右孩子DE入队
point --,point=0,C出队,C的右孩子F入队(这里C没有左孩子)
第三层遍历:
用point记录当前队列长度,point=3
max更新为3
point依次- -,直到point=0
和上面是同理的,就是把该层元素DEF全出掉,然后DEF的孩子全入队,也就是下一层元素全入队,第三层遍历的最终结果如下图:
第四层遍历:
用point记录当前队列长度,point=2
2<max=3,所以不用更新max
然后和前面一样,point依次 - -,直到point=0,然后该层元素全部出掉,下一层元素全部入队
最终结果如下图:
第五层遍历:
用point记录当前队列长度,point=1
1<max=3,所以不用更新max
point依次- -,直到point等于0,出该层元素,入下一层元素。
到这里,大家会发现,队中无元素了,也就是队列为空的情况,这就是层序遍历结束了
然后你打印最后的max=3即可
代码实现如下:
一些队列的基本操作你可以去我往期的队列文章里面看,我这里就直接上函数接口了
数据结构队列万字详解链接
//用的队列的相关操作
void InitQueue(SqQueue* Q);//初始化队列
int EnQueue(SqQueue* Q,BiTree e);//入队
void DeQueue(SqQueue* Q);//出队
int QueueEmpty(SqQueue Q);//队列判空
int QueueLength(SqQueue Q);//获取队列长度//求二叉树最大宽度
int BiTreeWidth(BiTree T){if(T==NULL){//树为空,宽度为0return 0;}else{SqQueue Q;//声明一个辅助队列InitQueue(&Q);//初始化队列int max=0;//记录最大宽度EnQueue(&Q,T);//根节点入队while(!QueueEmpty(Q)){//层序遍历int point=QueueLength(Q);//记录该层元素个数(该层宽度)max=max>point?max:point;//如果该层宽度更大,更新maxwhile(point){//移除当前层元素,入下一层元素BiTree tmp=Q.data[Q.front];//出队头元素,用tmp记录出队结点DeQueue(&Q);if(tmp->lchild!=NULL){//出队的结点有左孩子EnQueue(&Q,tmp->lchild);//左孩子入队}if(tmp->rchild!=NULL){//出队的结点有右孩子EnQueue(&Q,tmp->rchild);//右孩子入队}}}return max;}
}