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