数据结构--二叉树收尾

目录

1.二叉树的销毁

2.层序遍历

2.1深度优先搜索

2.1.1满(完全)二叉树引入

2.1.2什么是广度优先搜索

2.2广度优先搜索

2.2.1基本思路

2.2.2代码解析

3.完全二叉树的判断

3.1思路分析

3.2原理剖析

3.3代码分析

4.逆推二叉树结构


1.二叉树的销毁

//二叉树的销毁
void treedestory(btnode* root)
{if (root == NULL){return;}treedestory(root->left);treedestory(root->right);free(root);
}

这个就是二叉树的结尾工作,二叉树的销毁,我们判断这个root节点,如果是空的,就可以直接返回,说明这个二叉树上面是没有节点的,我们不需要销毁了;

否则我们就需要使用递归的方法,把这个root的左节点和右节点依次进行删除销毁处理,最后把这个节点释放掉;

2.层序遍历

2.1深度优先搜索

2.1.1满(完全)二叉树引入

对于上面的这个简单的二叉树,首先我们要知道这个二叉树不是一个完全二叉树,我们要分清楚这个满二叉树和完全二叉树(后面我们会有介绍,我们会有相应的代码去判断这个已知的二叉树是不是一个完全二叉树),这个满二叉树就是很好判断的,就是这个完全二叉树不容易辨别,我们后面会详细介绍;

2.1.2什么是广度优先搜索

广度优先搜索,简称就是DFS这个D就是depth,在英文里面就是广度深度的意思,F是first的第一个字母,S就是search,英文释义就是搜索的意思;

对于上面展示的这个二叉树,我们需要注意的就是这个广度就是一条路走到黑,不到黑就不会回头,我们的这个遍历顺序就是abebfbg以此类推,我上面写的顺序一个字母出现两次只是方便大家的理解,实际上这个真实的遍历,肯定不会出现两次的,就是广度优先遍历就会一条路一直向下走,走到E之后发现没有下一个节点了,他才会回头,因为这个是到达B之后开始分叉的,这个时候他就会重新回到B选择F的这一条路径,走到F之后就会发现这个又走不下去了,这个时候就会继续掉头,以此类推进行下去;

2.2广度优先搜索

2.2.1基本思路

这个就是按照一行一行的顺序进行遍历的,这个顺序是很清晰的,一般不会出现问题,而且这个思路也是很清晰的,我们在这个层序遍历的过程中会打印输出这个遍历的结果,实际上就是一层一层的读取的结果;

void treelevelorder(btnode* root)
{quene q;queneinit(&q);if (root){quenepush(&q, root);}while (!queneempty(&q)){//取出来队列里面的第一个元素btnode* front = quenefront(&q);//队列元素出栈quenepop(&q);printf("%d ", front->data);if (front->left){quenepush(&q, front->left);}if (front->right){quenepush(&q, front->right);}}//队列的销毁quenedestory(&q);
}
2.2.2代码解析

treelevelorder就是这个层序遍历函数的简写,这个名字并不是乱取的,level有这个水平的意思,也有层级的意思,order这个就很容易理解了,就是遍历的意思,我们之前介绍的前序遍历,中序遍历,后序遍历都是使用的这个单词;

这个里面因为是使用的C语言实现的,我们首先需要构建一个对列出来,为什么要构建一个队列,因为我们这个广度优先搜索的代码就是使用的队列的相关思想,我们让一个二叉树里面的元素一个一个的进去,就是用的quenepush函数,然后再让这个quenefront函数取出来这个队列里面的第一个元素,这个元素节点的数值最后打印出来,设置循环和递归依次进行,最后得到的这个打印的结果就是所有的层序遍历的结果;

这个quenepop之后还可以找到这个对应的数值吗,这个是刚开始学的时候不少初学者的疑问,实际上这个是不会冲突的,因为这个pop的是我们自己构建的队列,我们的这个队列每一个元素都是一个指针,指向的就是这个二叉树里面的每一个节点,我们把这个队列里面的节点给释放掉了,这个二叉树里面的元素师依然可以被取出来的;

3.完全二叉树的判断

3.1思路分析

这个如何去判断一个二叉树是不是一个完全二叉树,我们使用的方法就是上面介绍的层序遍历,空的节点也需要进入队列,我们这个基本思路还是使用的队列的入队列和出队列的方法去进行判断;

那下面的第一个二叉树进行举例,显示让1这个节点进入队列,然后1节点出来,24节点进入(这个节点的两个子节点进入),然后2出来,2的两个子节点36进入,接下来就是4出来他的两个子节点(都是空的,但是上面写了,空的也是需要入队列的),接下俩就是3出队列,两个空节点入队列,接下里就是6这个节点出队列,他的两个子节点入队列,接下来就是4的子节点入队列,这个时候已经是空的了,且这个4的子节点后面没有非空的节点,我们这个时候就可以去判定这个二叉树就是一个完全二叉树;

同理我们去分析一下第二个二叉树,我们已经知道这个不是一个完全二叉树,先1进入队列,然后1出队列,24进入队列,然后2出队列,3和空进入队列,然后就是4出队列56进入队列,接下来就是3出队列,空空进入队列,接下来就是空出队列,但是这个空节点的后面还有两个节点没有出队列,这个时候就可以断定这个二叉树不是一个完全二叉树了;

3.2原理剖析

不直达大家有没有这个疑问,到底什么是真正的完全二叉树,到底有多少人真正的理解了这个完全二叉树的定义,虽然这个并不像离散数学那样对于这个二叉树的定义那么严合格的考察,但是我们还是应该了解的;

老师在讲述的时候,直接告诉我们下面的第二个图片不是完全二叉树,我当时就心存疑惑,到底什么是真正的完全二叉树,为什么第二个不是完全二叉树;

下面的这个就是我在网络上面找到的一个比较满意的回答,就是通过编号和满二叉树的编号进行比较,就可以确定这个二叉树是不是一个完全二叉树;如果明白了面的这个原理,我们就可以很清楚的辨别出来上面的图片里面的第二个二叉树不是一个完全二叉树

3.3代码分析

下面的这个代码是完全按照上面的这个思路去实现的,我们先创建一个队列,然后去进行初始化,为什么这个里面会有两个while循环;

我们只需要那上面的一个案例测试一下即可,就选择上面的第二个案例吧,第二个不是完全二叉树

我们的1进入这个循环,1出来之后这个24节点进入,2出来之后3和空进入,4出来之后56进入,3出来之后这个空空进入,这个时候轮到空节点了,这个时候跳出了第一个while循环,但是这个时候的56节点已经进入了这个队列,我们执行第二个循环的时候,是可以进去的这个时候有节点,所以会进入if语句,返回false;

相反,对于这个完全二叉树而言,就像第一个二叉树,我们就可以跳出这个循环,第二个循环他是不会进入的,因为这个时候队列里面已经没有数据了,我们这个时候就会直接返回true,表明这个二叉树就是一个完全二叉树,第二个while循环就是为非完全二叉树准备的;

bool treecomplete(btnode* root)
{quene q;queneinit(&q);while (!queneempty(&q)){//取出队列里面的第一个元素btnode* front = quenefront(&q);//出队列quenepop(&q);if (front == NULL){break;}quenepush(&q, front->left);quenepush(&q, front->right);}while (!queneempty(&q)){btnode* front = quenefront(&q);quenepop(&q);if (front == NULL){quenedestory(&q);return false;}}quenedestory(&q);return true;
}

4.逆推二叉树结构

我们在这个离散数学里面也有这个类似的题目,但是当时在这个离散数学里面是有这个对应的符号,我们可以有相应的方法,在数据结构里面没有其他的符号,我们只能自己去推理;

通常情况下给的就是前序遍历和中序遍历,让我们去写这个后序遍历,我们要根据这个前序遍历和中序遍历把这个二叉树的结构给推理出来,然后再去写出这个对应的后序遍历结果;

我们方法就是采用的分割法,先是把这个中序结果给分隔开,根据这个前序遍历,我们就可以确定这个1就是树根,我们就把这个中序结果从1分隔开,然后结合这个前序遍历结果依次进行分析;

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

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

相关文章

惠海H5112A降压恒流芯片IC 60V72V80V100V转24V36V48V多路共阳输出景观LED点光源

H5112A是一款外围电路简单的多功能平均电流型LED恒流驱动器,适用于5-90V电压范围的非隔离式大功率恒流LED驱动领域。芯片采用了平均电流模式控制,输出电流精度在士3%;输出电流对输入输出电压以及电感不敏感;芯片内部集成了环路补偿,外围电路更…

网络编程-TCP 协议的三次握手和四次挥手做了什么

TCP 协议概述 1. TCP 协议简介 TCP(Transmission Control Protocol,传输控制协议)是一种面向连接的、可靠的、基于字节流的传输层通信协议。 TCP 协议提供可靠的通信服务,通过校验和、序列号、确认应答、重传等机制保证数据传输…

自动化测试高级控件交互方法:TouchAction、触屏操作、点按,双击,滑动,手势解锁!

在自动化测试领域中,TouchAction 是一种非常强大的工具,它允许我们模拟用户在设备屏幕上的各种触摸事件。这种模拟不仅限于简单的点击操作,还包括滑动、长按、多点触控等复杂的手势。 点按与双击 点按和双击是触屏设备上最基本的操作之一。…

【AMD/Xilinx】FPGA远程烧录调试工具安装及使用

问题描述 在学习工作中,本人遇到了连接FPGA的服务器电脑没有Vivado或Vivado版本较低,导致没办法查看ila的情况。在这种情况下一方面重新安装Vivado需要占用大量存储空间,另一方面使用远程桌面软件连接服务器电脑的画质较为模糊,影…

走进数组的奇妙之旅

引言: 在前几篇文章中,我们深入探讨了函数的奥秘。在讲述函数知识的过程中,我们邂逅了一个新的概念,你或许还记得在演示 strcpy函数时,出现的这行代码:char1[20]{0};。当时,你是否感到好奇&…

PHP萌宠之家微信小程序系统源码

🐾萌宠之家微信小程序🐾 —— 铲屎官们的温馨小窝✨ 🏠【一键开启萌宠乐园】🏠 亲们,是不是每次刷手机都忍不住想看看那些软萌可爱的毛孩子?现在,有了“萌宠之家”微信小程序,你的…

通信流程:https【SSL/TLS】,git仓库【https/SSH】,蓝牙【面对面快传/AirDrop】

目录 HTTPS HTTP(80端口) SSL/TLS协议(传输层,443端口) 密文传输:SSL的后续版本TLS TLS1.2握手 1.摘要算法(散列函数 Hash Function):验证信息的完整性,不可逆 第三方认证 引…

数据结构之初始二叉树(2)

找往期文章包括但不限于本期文章中不懂的知识点: 个人主页:我要学编程(ಥ_ಥ)-CSDN博客 所属专栏:数据结构(Java版) 二叉树的前置知识(概念、性质、、遍历) 通过上篇文章的学习,我们…

iOS——MRC与ARC以及自动释放池深入底层学习

MRC与ARC再回顾 在前面,我们简单学了MRC与ARC。MRC指手动内存管理,需要开发者使用retain、release等手动管理对象的引用计数,确保对象在必要时被释放。ARC指自动内存管理,由编译器自动管理对象的引用计数,开发者不需要…

如何用EXCEL自动解方程/方程组?利用 矩阵乘法X=A-*B,X=mmult(minverse(A), B)

目录 问题的由来 1 数据 → 模拟分析 → 单变量求解 1.1 找一个单元格填入公式 1.2 功能入口 1.3 选择单变量求解,分别填入内容 1.4 求解 1.5 这个感觉用处不大 2 重点介绍,用EXCEL进行矩阵运算解方程的操作 2.1 运用EXCEL进行矩阵运算&…

Sentinel-1 Level 1数据处理的详细算法定义(四)

《Sentinel-1 Level 1数据处理的详细算法定义》文档定义和描述了Sentinel-1实现的Level 1处理算法和方程,以便生成Level 1产品。这些算法适用于Sentinel-1的Stripmap、Interferometric Wide-swath (IW)、Extra-wide-swath (EW)和Wave模式。 今天介绍的内容如下: Sentinel-1 L…

操作系统内核源码杂谈篇:临界区

临界资源,是指同一时刻只能由一个线程(linux下为进程)访问的资源,而临界区就是为了确保临界资源访问是单一数据流。 临界区的代码执行,也就是进行原子操作,不会被打断。 先分析RTOS的运行架构&#xff0c…

人工智能算法工程师(高级)课程1-单类目标识别之人脸检测识别技术MTCNN模型介绍与代码详解

大家好,我是微学AI,今天给大家介绍一下人工智能算法工程师(高级)课程1-单类目标识别之人脸检测识别技术MTCNN模型介绍与代码详解。本文深入探讨了基于PyTorch的人脸检测与识别技术,详细介绍了MTCNN模型、Siamese network以及center loss、sof…

qml 实现一个listview

主要通过qml实现listvie功能&#xff0c;主要包括右键菜单&#xff0c;滚动条&#xff0c;拖动改变内容等&#xff0c;c 与 qml之间的变量和函数的调用。 main.cpp #include <QQuickItem> #include <QQmlContext> #include "testlistmodel.h" int main…

Java里的引用详解

1.体验方法引用 方法引用的出现原因 在使用Lambda表达式的时候&#xff0c;我们实际上传递进去的代码就是一种解决方案&#xff1a;拿参数做操作 那么考虑一种情况&#xff1a;如果我们在Lambda中所指定的操作方案&#xff0c;已经有地方存在相同方案&#xff0c;那是否还有必要…

PHP房产中介租房卖房平台微信小程序系统源码

​&#x1f3e0;【租房卖房新选择】揭秘房产中介小程序&#xff0c;一键搞定置业大事&#xff01;&#x1f3e1; &#x1f50d;【开篇&#xff1a;告别繁琐&#xff0c;拥抱便捷】&#x1f50d; 还在为找房子跑断腿&#xff1f;为卖房发愁吗&#xff1f;今天给大家安利一个超…

JavaScript 获取 url(get)参数

https://andi.cn/page/621584.html

pytorch学习(八)Dataset加载分类数据集

我们之前用torchvision加载了pytorch的网络数据集&#xff0c;现在我们用Dataset加载自己的数据集&#xff0c;并且使用DataLoader做成训练数据集。 图像是从网上下载的&#xff0c;网址是 点这里&#xff0c;标签是图像文件夹名字。下载完成后作为自己的数据集。 1.加载自己…

PyTorch 深度学习实践-循环神经网络基础篇

视频指路 参考博客笔记 参考笔记二 文章目录 上课笔记基于RNNCell实现总代码 基于RNN实现总代码 含嵌入层的RNN网络嵌入层的作用含嵌入层的RNN网络架构总代码 其他RNN扩展基本注意力机制自注意力机制&#xff08;Self-Attention&#xff09;自注意力计算多头注意力机制&#xf…

RPC与服务的注册发现

文章目录 1. 什么是远程过程调用(RPC)?2. RPC的流程3. RPC实践4. RPC与REST的区别4.1 RPC与REST的相似之处4.2 RPC与REST的架构原则4.3 RPC与REST的主要区别 5. RPC与服务发现5.1 以zookeeper为服务注册中心5.2 以etcd为服务注册中心 6. 小结参考 1. 什么是远程过程调用(RPC)?…