【初阶数据结构篇】链式结构二叉树(续)

文章目录

须知

💬 欢迎讨论:如果你在学习过程中有任何问题或想法,欢迎在评论区留言,我们一起交流学习。你的支持是我继续创作的动力!

👍 点赞、收藏与分享:觉得这篇文章对你有帮助吗?别忘了点赞、收藏并分享给更多的小伙伴哦!你们的支持是我不断进步的动力!
🚀 分享给更多人:如果你觉得这篇文章对你有帮助,欢迎分享给更多对C++感兴趣的朋友,让我们一起进步!

接上篇:【初阶数据结构篇】链式结构二叉树(二叉链)的实现(感受递归暴力美学)-CSDN博客

 2.6 二叉树查找位置x的节点
  • 分为左右子树查找,依次递推即可
  • 结束条件为空:说明在这一路径上没有找到
  • 进入第二个if,说明找到了直接返回结点指针
2.6.1 示例代码:
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}BTNode* leftFind = BinaryTreeFind(root->left, x);if (leftFind){return leftFind;}BTNode* rightFind = BinaryTreeFind(root->right, x);if (rightFind){return rightFind;}return NULL;
}
2.7 二叉树的销毁 
2.7.1示例代码:
void BinaryTreeDestory(BTNode** root)
{if (*root == NULL){return;}BinaryTreeDestory(&((*root)->left));BinaryTreeDestory(&((*root)->right));free(*root);*root = NULL;
}

图解:

2.8 二叉树的层序遍历

 层序遍历:对于树型结构,层序遍历就是按层从上到下,每层按一定顺序对树的节点进行遍历。我们通过如图所示的二叉树进行说明:对于左边的二叉树,按层划分后可得到右边的分层结构。

简单来说就是从上到下从左往右打印节点中的数据。

实现层序遍历需要借助数据结构队列(先进先出)

先将根节点入队列, 出队列前打印根节点的数据,同时将根节点的左右孩子入队列,重复该过程,直至队列为空。

2.8.1 示例代码:
//层序遍历
//借助数据结构---队列
void LevelOrder(BTNode* root)
{Queue q;QueueInit(&q);QueuePush(&q, root);while (!QueueEmpty(&q)){//取队头,打印BTNode* front = QueueFront(&q);printf("%d ", front->data);QueuePop(&q);//队头节点的左右孩子入队列if (front->left)QueuePush(&q, front->left);if (front->right)QueuePush(&q, front->right);}//队列为空QueueDestroy(&q);
}
2.9 完全二叉树的判断

 取队头,左右节点全入队列,当取出对头为空,跳出循环。

进入第二个循环判断剩下的队列是否有非空节点

有则为非完全二叉树,反之亦然。

2.9.1 示例代码:
//判断二叉树是否为完全二叉树
//---队列
bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front == NULL){break;}QueuePush(&q, front->left);QueuePush(&q, front->right);}//队列不一定为空while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front != NULL){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;
}
3. 二叉树性质选择题

二叉树性质

对任何⼀棵⼆叉树, 如果度为 0 其叶结点个数为 n 0 , 度为 2 的分⽀结点个数为 n 2 ,则有
n 0 = n 2 + 1.

证明:

 

假设⼀个⼆叉树有 a 个度为2的节点, b 个度为1的节点, c 个叶节点,则这个⼆叉树的边数是
2a+b
另⼀⽅⾯,由于共有 a+b+c 个节点,所以边数等于 a+b+c-1
结合上⾯两个公式:
2a+b = a+b+c-1 ,即a=c-1。
3.1 题目1
1. 某⼆叉树共有 399 个结点,其中有 199 个度为 2 的结点,则该⼆叉树中的叶⼦结点数为( )
A 不存在这样的⼆叉树
B 200
C 198
D 199
选B
根据上述二叉树性质
n0=n2+1即n0=199+1=200
3.2 题目2
2. 在具有 2n 个结点的完全⼆叉树中,叶⼦结点个数为( )
A n
B n+1
C n-1
D n/2
完全二叉树只含有0/1个度为1的节点个数。
选A
3.3 题目3
3. ⼀棵完全⼆叉树的结点数位为 531 个,那么这棵树的⾼度为( )
A 11
B 10
C 8
D 12
选B
 3.4 题目4
4. ⼀个具有 767 个结点的完全⼆叉树,其叶⼦结点个数为()
A 383
B 384
C 385
D 386

 

选B 

4 二叉树遍历选择题
4.1 题目1
1. 某完全⼆叉树按层次输出(同⼀层从左到右)的序列为 ABCDEFGH 。该完全⼆叉树的前序序列为(
A ABDHECFG
B ABCDEFGH
C HDBEAFCG
D HDEBFGCA

选A 

4.2 题目2
2. ⼆叉树的先序遍历和中序遍历如下:先序遍历: EFHIGJK; 中序遍历: HFIEJKG. 则⼆叉树根结点为
()
A E
B F
C G
D H

 

根据先序遍历(根左右):

选A 

4.3 题目3
3. 设⼀课⼆叉树的中序遍历序列: badce ,后序遍历序列: bdeca ,则⼆叉树前序遍历序列为 ____
A adbce
B decab
C debac
D abcde

根据先序遍历规则:abcde

选D

4.4 题目4
4. 某⼆叉树的后序遍历序列与中序遍历序列相同,均为 ABCDEF ,则按层次输出(同⼀层从左到右)
的序列
A FEDCBA
B CBAFED
C DEFCBA
D ABCDEF

根据层序遍历规则:FEDCBA

选A 

相信通过这篇文章你对二叉数性质与遍历的有了进一步的了解。如果此篇文章对你学习数据结构(二叉树)有帮助,期待你的三连,你的支持就是我创作的动力!!!

下一篇文章再会!!!

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

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

相关文章

VMWARE ESXI VMFS阵列故障 服务器数据恢复

1:河南用户一台DELL R740 3块2.4T硬盘组的RAID5,早期坏了一个盘没有及时更换,这次又坏了一个,导致整组RAID5处于数据丢失的状态, 2:该服务器装的是VMware ESXI 6.7,用户把3块硬盘寄过来进行数据…

使用docker安装zlmediakit服务(zlm)

zlmediakit安装 zlmediakit安装需要依赖环境和系统配置,所以采用docker的方式来安装不容易出错。 docker pull拉取镜像(最新) docker pull zlmediakit/zlmediakit:master然后先运行起来 sudo docker run -d -p 1935:1935 -p 80:80 -p 8554:554 -p 10000:10000 -p …

uni-app跨域set-cookie

set-cookie的值是作为一个权限控制的 首先,无论什么接口都会返回一个set-cookie,但未登录时,set-cookie是没有任何权限的 其次,登录接口请求时会修改set-cookie,并且在后续其他接口发起请求时,会在请求头…

【论文速读】| PathSeeker:使用基于强化学习的越狱攻击方法探索大语言模型的安全漏洞

基本信息 原文标题: PathSeeker: Exploring LLM Security Vulnerabilities with a Reinforcement Learning-Based Jailbreak Approach 原文作者: Zhihao Lin, Wei Ma, Mingyi Zhou, Yanjie Zhao, Haoyu Wang, Yang Liu, Jun Wang, Li Li 作者单位: Beihang University, Nany…

黑马官网2024最新前端就业课V8.5笔记---HTML篇

Html 定义 HTML 超文本标记语言——HyperText Markup Language。 标签语法 标签成对出现&#xff0c;中间包裹内容<>里面放英文字母&#xff08;标签名&#xff09;结束标签比开始标签多 /拓展 &#xff1a; 双标签&#xff1a;成对出现的标签 单标签&#xff1a;只有开…

NXP Zigbee JN5169 开发环境软件 文档和支持资源打包下载

NXP Zigbe JN5169软件、文档和支持资源下载 从NXP官网下载https://www.nxp.com.cn/pages/jn516x-7x-zigbee-3-0:ZIGBEE-3-0&#xff0c;有点蛋疼网站&#xff0c;要注册会员&#xff0c;所以我打包好所有NXP Zigbe JN5169所需的 软件、文档和支持资源打包好&#xff0c;以供开…

基于matlab的语音识别系统

一&#xff0e;设计任务及要求 1.1设计任务 作为智能计算机研究的主导方向和人机语音通信的关键技术&#xff0c;语音识别技 术一直受到各国科学界的广泛关注。以语音识别开发出的产品应用领域非常广泛&#xff0c;有声控电话交换、语音拨号系统、信息网络查询、家庭服务、宾馆…

使用WebStorm开发Vue3项目

记录一下使用WebStorm开发Vu3项目时的配置 现在WebStorm可以个人免费使用啦&#xff01;&#x1f929; 基本配置 打包工具&#xff1a;Vite 前端框架&#xff1a;ElementPlus 开发语言&#xff1a;Vue3、TypeScript、Sass 代码检查&#xff1a;ESLint、Prettier IDE&#xf…

Ansys HFSS:外壳的屏蔽效果演示

欢迎回来&#xff01;随着电子系统变得越来越复杂和集成&#xff0c;确保适当的屏蔽以减轻电磁干扰 &#xff08;EMI&#xff09; 变得越来越重要。 继续讨论屏蔽效果&#xff0c;我们现在将重点转移到另一个强大的工具上&#xff1a;Ansys HFSS&#xff08;高频结构仿真器&am…

Python基于TensorFlow实现双向循环神经网络GRU加注意力机制分类模型(BiGRU-Attention分类算法)项目实战

说明&#xff1a;这是一个机器学习实战项目&#xff08;附带数据代码文档视频讲解&#xff09;&#xff0c;如需数据代码文档视频讲解可以直接到文章最后关注获取。 1.项目背景 随着深度学习技术的发展&#xff0c;循环神经网络&#xff08;RNN&#xff09;及其变种如门控循环…

【C++】C++的单例模式

二十四、C的单例模式 1、C的单例模式 本小标题不是讨论C的语言特性&#xff0c;而是一种设计模式&#xff0c;用于确保一个类在任何情况下都只有一个实例&#xff0c;并提供一个全局访问点来获取这个实例。即C的单例模式。这种模式常用于资源管理&#xff0c;如‌线程池、‌缓…

单元测试(Junit)

系统—模块—子模块&#xff0c;子模块中不可分割的程序单元的测试&#xff0c;单元的粒度根据实际情况可能是 类或方法等。 面向对象编程中&#xff0c;最小单元就是方法。 单元测试目的是在集成测试和功能测试之前对系统可测试单元进行逐一检查和验证。 单元测试基本原则 …

这个自动化框架吧,解决接口间数据依赖

在实际的测试工作中&#xff0c;在做接口自动化测试时往往会遇到接口间数据依赖问题&#xff0c;即API_03的请求参数来源于API_02的响应数据&#xff0c;API_02的请求参数又来源于API_01的响应数据。 因此通过自动化方式测试API_03接口时&#xff0c;需要预先请求API_02接口&a…

JeecgBoot入门

最近在了解低代码平台&#xff0c;其中关注到gitee上开源项目JeecgBoot&#xff0c;JeecgBoot官方也有比较完整的入门教学文档&#xff0c;这里我们将耕者官方教程学习&#xff0c;并将其记录下来。 一、项目简介 JeecgBoot 是一款基于代码生成器的低代码开发平台拥有零代码能力…

修改HarmonyOS鸿蒙图标和名字,打包后安装到真机,应用图标丢失变成透明,修改名字也不生效,还是默认的labeL解决方案教程

HarmonyOS鸿蒙打包hap 安装应用到桌面没有图标&#xff0c;用hdc安装到真机&#xff0c;打包后应用图标丢失变成透明&#xff0c;名字也还是默认的label的bug&#xff0c;以下是解决方案 以下是修改方案&#xff1a; 1、修改应用名字&#xff1a; 2、修改应用图标&#xff1a…

MYSQL安装(ubuntu系统)

rpm -qa 查询安装软件包 ps axj 查询服务 卸载mysql&#xff08;万不得已&#xff09; ps axj | grep mysql 查看是否存在mysql服务 systemctl stop mysqld 关闭该服务 rpm -qa | grep mysql 查安装mysql安装包 rmp -qa | grep mysql | xargs (yum apt) -y remove进行批量…

比ChatGPT更牛!苹果新AI模型刷新交互体验!能看懂你的手机屏幕!平板和安卓机也都行

家人们&#xff0c;苹果一直在悄悄进步&#xff01; 近期&#xff0c;据小鹿观察&#xff0c;各大科技巨头不仅在提升模型解决复杂问题的能力上竞争激烈&#xff0c;而且还在大语言模型应用于用户界面&#xff08;UI&#xff09;交互方面上暗暗发力&#xff01; 最近&#xf…

InstructIR: High-Quality Image Restoration Following Human Instructions 论文阅读笔记

这是Radu大佬所在的Wrzburg大学的computer vision lab实验室发表在ECCV2024上的一篇论文&#xff0c;代码开源。文章提出了一种文本引导的All-in-One的restoration模型&#xff0c;如下图所示&#xff1a; 这个工作其实跟"InstructPix2Pix: Learning to Follow Image Edit…

解决使用Golang的email库发送qq邮件报错short response,错误类型为textproto.ProtocolError

问题阐述 使用email库发送QQ邮件&#xff0c;采用587端口&#xff1a; package mainimport ("fmt""net/smtp""github.com/jordan-wright/email" )func SendEmail(sendTo string, subject string, body string) (err error) {e : email.NewEmai…

【北京迅为】《STM32MP157开发板嵌入式开发指南》-第七十二章 Debian文件系统

iTOP-STM32MP157开发板采用ST推出的双核cortex-A7单核cortex-M4异构处理器&#xff0c;既可用Linux、又可以用于STM32单片机开发。开发板采用核心板底板结构&#xff0c;主频650M、1G内存、8G存储&#xff0c;核心板采用工业级板对板连接器&#xff0c;高可靠&#xff0c;牢固耐…