二叉树采用二叉链表存储:编写计算二叉树最大宽度的算法(二叉树的最大宽度是指二叉树所有层中结点个数的最大值)

二叉树采用二叉链表存储:编写计算二叉树最大宽度的算法
(二叉树的最大宽度是指二叉树所有层中结点个数的最大值)

和二叉树有关的代码,基本都逃不过“先中后层”,这四种遍历

而我们这里是让你计算最大宽度,它是横着来的,那我们就可以断定是要用到层序遍历
对层序遍历不熟悉的,可以看我这篇文章光速上手二叉树层序遍历

代码思路

首先我们有如下的树,和一个空队列,用一个变量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;}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/180793.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Hydra post登录框爆破

文章目录 无token时的Hydra post登录框爆破带Token时的Hydra post登录框爆破 无token时的Hydra post登录框爆破 登录一个无验证码和token的页面&#xff0c;同时抓包拦截 取出发送数据包&#xff1a;usernameadb&password133&submitLogin 将用户名和密码替换 userna…

【2024最新】PE工具箱【下载安装】零基础到大神【附下载链接】

下载链接&#xff1a;点这里 1.PE (Portable Executable) 工具箱通常用于处理Windows可执行文件和动态链接库&#xff08;DLL&#xff09;的二进制文件格式。这些工具对于进行逆向工程、软件分析和系统维护等任务非常有用。以下是PE工具箱的一些常见功能和用法&#xff1a; 查…

【C语言进阶】之动态内存管理笔试题及柔性数组

【C语言进阶】之动态内存管理笔试题 1.动态内存管理笔试题汇总1.1第一道题1.2第二道题1.3第三道题1.4第四道题 2.C/C内存管理3.柔性数组3.1什么是柔性数组3.2柔性数组的使用3.2柔性数组的优点 &#x1f4c3;博客主页&#xff1a; 小镇敲码人 &#x1f680; 欢迎关注&#xff1a…

Webpack搭建本地服务器

一、搭建webpack本地服务 1.为什么要搭建本地服务器&#xff1f; 目前我们开发的代码&#xff0c;为了运行需要有两个操作&#xff1a; 操作一&#xff1a;npm run build&#xff0c;编译相关的代码&#xff1b;操作二&#xff1a;通过live server或者直接通过浏览器&#x…

Draft-P802.11be-D3.2协议学习__$9-Frame-Format__$9.3.1.22-Trigger-frame-format

Draft-P802.11be-D3.2协议学习__$9-Frame-Format__$9.3.1.22-Trigger-frame-format 9.3.1.22.1 Genreal9.3.1.22.2 Common Info field9.3.1.22.3 Special User Info field9.3.1.22.4 HE variant User Info field9.3.1.22.5 EHT variant User Info field9.3.1.22.6 Basic Trigge…

4K Video Downloader Pro v4.28.0(视频下载器)

4K Video Downloader Pro是一款专业的视频下载软件&#xff0c;支持从YouTube、Vimeo、Facebook、Instagram、TikTok等主流视频网站下载高质量的4K、HD和普通视频。它的操作流程简单&#xff0c;只需复制视频链接并粘贴到软件中即可开始下载。此外&#xff0c;该软件还提供了多…

C# Winform串口助手

界面设置 修改控件name属性 了解SerialPort类 实现串口的初始化&#xff0c;开关 创建虚拟串口 namespace 串口助手 {public partial class Form1 : Form{public Form1(){InitializeComponent();}private void Form1_Load(object sender, EventArgs e){//在设计页面已经预先…

在Linux上通过NTLM认证连接到AD服务器(未完结)

这篇文章目前还没有实现具体的功能&#xff0c;只实现了明文登录&#xff0c;因为我缺少一些数据&#xff0c;比如通过密码生成hash&#xff0c;以及通过challenge生成response&#xff0c;我不知道怎么实现&#xff0c;因此这篇文章也是一个交流的文章&#xff0c;希望大佬看见…

深入理解网络IO复用并发模型

本文主要介绍服务端对于网络并发模型以及Linux系统下常见的网络IO复用并发模型。文章内容一共分为两个部分。 第一部分主要介绍网络并发中的一些基本概念以及我们Linux下常见的原生IO复用系统调用&#xff08;epoll/select&#xff09;等。第二部分主要介绍并发场景下常见的网…

el-table树状表格末行合计

首先,由于我的表头是动态的,所以就稍微复杂一点 效果图 表头数据格式是这样的 表格的数据格式是这样的 然后用合并的方法,此处就需要递归去计算,根据props去匹配每一列的数据,然后加起来,关键代码 //合计处理getSummaries(param) {const { columns, data } param;const su…

树结构及其算法-二叉排序树

目录 树结构及其算法-二叉排序树 C代码 树结构及其算法-二叉排序树 事实上&#xff0c;二叉树是一种很好的排序应用模式&#xff0c;因为在建立二叉树的同时&#xff0c;数据已经经过初步的比较&#xff0c;并按照二叉树的建立规则来存放数据&#xff0c;规则如下&#xff1…

解决方案中word中分节符的使用

解决方案中必不可少的两个“符号”&#xff0c;分页符&#xff0c;分节符 有了分节符&#xff0c;可以为不同节设置不同的页眉页脚、分栏格式、纸张大小及方向、页边距、不同节间采用不同的页码序号&#xff0c;常用的功能主要是把word下一次的由原来的“竖版”&#xff0c;变…

深入剖析:正则表达式的奥秘

简介 正则表达式&#xff08;Regular Expressions&#xff09;是一种强大的文本处理工具&#xff0c;一种用于匹配文本模式的字符串。它由特定的字符和操作符组成&#xff0c;用于定义一个搜索模式。这些搜索模式可以用于文本搜索、替换、验证和提取数据等多种用途。 以下是一…

canal+es+kibana+springboot

1、环境准备 服务器&#xff1a;Centos7 Jdk版本&#xff1a;1.8 Mysql版本&#xff1a;5.7.44 Canal版本&#xff1a;1.17 Es版本&#xff1a;7.12.1 kibana版本&#xff1a;7.12.1 软件包下载地址&#xff1a;链接&#xff1a;https://pan.baidu.com/s/1jRpCJP0-hr9aI…

【Python语言】序列(列表,元组,字符串)切片操作

目录 序列切片操作 1.1 对list进行切片&#xff0c;从1开始&#xff0c;到5结束&#xff0c;步长为1 [ 1 : 5 ] 1.2 对tuple进行切片&#xff0c;从头开始&#xff0c;到最后结束&#xff0c;步长为1 [ : ] 1.3 对str进行切片&#xff0c;从头开始&#xff0c;到最…

『精』Vue 组件如何模块化抽离Props

『精』Vue 组件如何模块化抽离Props 文章目录 『精』Vue 组件如何模块化抽离Props一、为什么要抽离Props二、选项式API方式抽离三、组合式API方式抽离3.1 TypeScript类型方式3.2 文件分离方式3.3 对文件分离方式优化 参考资料&#x1f498;推荐博文&#x1f357; 一、为什么要抽…

Cordova插件开发二:高精度定位之卫星数据解析

文章目录 1.最终效果预览2.坐标获取方法3.在公共类中封装获取坐标的通用方法4.插件js中封装startGeoLocation方法5.插件主界面封装的方法1.最终效果预览 2.坐标获取方法 let obj = Object.assign({}, this.mapConfig.mapLocationObj)obj.isKeepCallBack = falselet res = await…

探索无限可能:APITable免费开源多维表格与可视化数据库远程访问的魅力

APITable免费开源的多维表格与可视化数据库公网远程访问 文章目录 APITable免费开源的多维表格与可视化数据库公网远程访问前言1. 部署APITable2. cpolar的安装和注册3. 配置APITable公网访问地址4. 固定APITable公网地址 前言 vika维格表作为新一代数据生产力平台&#xff0c…

代码生成器

Easycode Entity ##导入宏定义 $!{define.vm}##保存文件&#xff08;宏定义&#xff09; #save("/entity", ".java")##包路径&#xff08;宏定义&#xff09; #setPackageSuffix("entity")##自动导入包&#xff08;全局变量&#xff09; $!{au…

半导体工厂将应用哪些制造创新技术?

半导体工厂是高科技产业的结晶&#xff0c;汇聚了世界上最新的技术。 在半导体的原料硅晶片上绘制设计图纸&#xff0c;不产生误差&#xff0c;准确切割并包装&#xff0c;然后用芯片生产出我们使用的电脑、智能手机、手表等各种电子产品。绝大多数半导体厂都采用一贯的工艺&a…