当前位置: 首页 > news >正文

【数据结构】二叉树:简约和复杂的交织之美

专栏引入:

哈喽大家好,我是野生的编程萌新,首先感谢大家的观看。数据结构的学习者大多有这样的想法:数据结构很重要,一定要学好,但数据结构比较抽象,有些算法理解起来很困难,学的很累。我想让大家知道的是:数据结构非常有趣,很多算法是智慧的结晶,我希望大家在学习数据结构的过程是一种愉悦的心情感受。因此我开创了《数据结构》专栏,在这里我将把数据结构内容以有趣易懂的方式展现给大家。

1.二叉树 

 生活中,我们经常会遇到管理大量数据的情况,比如图书馆书记的分类。而二叉树这种数据结构正是用来解决这种问题的,当我们阅读书时,书中的每个条目都有专门分类和子分类,为了更好的组织这些内容,需要使用一种高效的数据结构来存储和访问信息。下面举个简单的例子来引入二叉树,我们在中学学习生物时知道了植物主要分为:种子植物、苔藓植物等。那它们是如何进行分类的呢?我们看下面这张图片:

通过这种方式,我们可以逐级展开二叉树,更详细的组织植物分类的信息,每个节点都代表一个特定的分类,而子节点则代表该分类的下一级分类。这样我们可以更加轻松的查找和比较不同的植物分类信息。下面我们就来揭开二叉树的神秘面纱。

1.1二叉树的定义

二叉树是n(n>=0)个节点的有限集合,该集合或者为空集合(称为空二叉树),或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成。在下面的图中,左边的就是一棵二叉树,而右边的因为它的F节点有3个子节点,所以它不是二叉树。

1.2二叉树的特点

 二叉树具有以下几个特点:

  1. 每个节点最多有两个子节点,所以二叉树中不存在度大于2的节点。注意不是一定要有两个节点,而是最多有两个节点,没有节点或者只有一个节点也是可以滴。
  2. 左子树和右子树是有顺序的,次序不能颠倒,因此二叉树是有序树。
  3. 即使结构中某节点只有一个子节点,也要区分它是左节点还是右节点。

二叉树具有以下五种基本形态:空二叉树、只有一个根节点、根节点只有左子树、根节点只有右子树、根节点既有左子树又有右子树。

1.3特殊的二叉树 

1.3.1斜树

斜树,顾名思义,斜树一定是斜的,但是向哪里斜还是有讲究的。所有节点都只有左子树的二叉树的叫做左斜树,所有节点都只有右子树的二叉树叫做右斜树,这两者统称为斜树。在上一张图中根节点只有左子树和根节点只有右子树就是左斜树和右斜树的一个简单例子。斜树也有很明显的特点,就是每一层只有一个节点,节点个数和二叉树的深度相同。肯定也有人好奇:这也叫树?这不和线性表一样吗?确实,线性表可以理解成树的一种极其特殊的表现形式。

1.3.2满二叉树

我们通常举例子都是参差不齐的二叉树,那是否存在完美的二叉树呢?我们看下面这张图片:

看来完美的二叉树是存在的。在一棵二叉树中,如果所有分支节点都存在左子树和右子树,并且所有叶子都在一层上,这样的二叉树叫做满二叉树。下面就是一个满二叉树,从样子上看就感觉它很完美:

单是每一个节点都存在左右子树,不能算满二叉树,还必须要所有叶子都在一层上,这样才能做到整棵树的平衡。因此,满二叉树的特点有:

  1. 叶子只能出现在最底层,出现在其他层就不能达到平衡状态。
  2. 除了叶子节点外,每个节点都有两个子节点。即所有非叶子节点的度都为2.
  3. 在同样深度的二叉树中,满二叉树的节点个数最多,叶子数最多。

满二叉树的每一层都是满的,没有任何缺失节点。由于每个节点都具有两个子节点,满二叉树的平衡性很好。这使得在满二叉树上执行搜索、插入和删除等操作的平均时间复杂度非常高效。在满二叉树中,从根节点到任意一个叶子节点的路径长度都相同,是最短的路径。满二叉树常用于堆数据结构。满二叉树在实际应用中比较少见,因为它要求节点数必须是2的幂次方,而真实的数据往往不具备这样的特点。

1.3.3完全二叉树

对一棵具有n个节点的二叉树进行层序编号,如果编号为i(1≤i≤n)的节点与同样深度的满二叉树中的编号为i的节点在二叉树中的位置完全相同,则这棵二叉树称为完全二叉树。如下图:

在理解时,我们要注意区分满二叉树和完全二叉树。首先,从字面上区分,“完全”和“满”的区别,满二叉树一定是一棵完全二叉树,完全二叉树不一定是满的。其次,完全二叉树的所有节点和同样深度的满二叉树,它们按层序编号相同的节点,是一一对应的,这个关键词是按层序编号。像下面的二叉树中,因为5节点没有右子树,只有左子树,使得按层序编号的第11个编号空档了,它不是完全二叉树:

 只有下面图中的树,尽管它不是满二叉树,但编号是连续的,所以它是完全二叉树:

这里我们就可以总结出完全二叉树的一些特点:

  1. 叶子节点只能出现在最后两层。
  2. 最下层的叶子节点一定是集中在左部连续位置。
  3. 倒数第二层,如果有叶子节点,一定都在右部连续位置。
  4. 如果节点的度为1,则该节点只有左孩子,及不存在右子树的情况。
  5. 同样节点数的二叉树,完全二叉树的深度最小。

通过上面的理解,我们也知道了一个判断二叉树是否是完全二叉树的方法:那就是看树的示意图,给每个节点按照满二叉树的结构逐层顺序编号,如果编号出现空挡,就说明不是完全二叉树,反之就是。完全二叉树在实际应用中较为常见,它具有以下的优点:

  1. 节点的存储更加高效:由于完全二叉树的特点,可以使用数组来存储节点。这样可以大大节省存储空间,因为不需要为每个节点额外存储左右子节点的指针。
  2. 访问效率更高:由于节点的存储更加高效,可以使用数组的索引来访问节点。这样可以实现随机访问,访问的时间复杂度是O(1)。而在其他类型的二叉树中,如果要找到某个节点,需要从根节点出发进行遍历,访问的时间复杂度较高。

1.4二叉树的性质 

1.4.1二叉树的性质1

在二叉树的第i层至多有2^{i-1}个节点(i≥1)。这个性质很容易理解,我们观察一下满二叉树:

第一层是根节点,只有一个,所以2^{0}=1。第二层有两个,2^{1}=2。第三层有四个,2^{2}=4。第四层有八个,2^{3}=8。通过数据归纳法的论证,我们可以很轻松的得出在二叉树的第i层上至多有2^{i-1}个节点(i≥1)的结论。这个性质的重要性在于它给出了二叉树的每一层上节点数量的上限。通过这个性质,我们可以更好地理解和分析二叉树的结构。同时,这个性质也为二叉树的遍历、搜索等操作提供了重要的依据和限制。

1.4.2二叉树的性质2

深度为k的二叉树至多有2^{k}-1个节点(k≥1)。这里一定要注意,是2^{k}后再减1,而不是2^{k-1}。如果不注意的话很容易和性质1搞混。深度为k也就是有k层的二叉树,我们接着以上面那个满二叉树为例来看:如果只有一层,至多有2^{1}-1=1个节点。如果只有两层,至多有2^{2}-1=1+2个节点。如果只有三层,至多有2^{3}-1=1+2+4个节点。如果只有四层,至多有2^{4}-1=1+2+4+8个节点通过数据归纳法,我们可以得出:二叉树的深度为k层,此二叉树至多有2^{k}-1个节点。

1.4.3二叉树的性质3

对于任何一棵二叉树,如果其终端节点数为n_{0},度为2的节点数为n_{2},则n_{0}=n_{2}+1这是一个非常重要的性质,首先我们从二叉树的构建过程一步一步来理解它:

首先,我们先看只有一个根节点的时候,度为0的节点个数n0=1,度为2的节点的个数为n2=0。我们设度为1的节点的个数为n1,接着,我们给根节点加一个节点,这时候一定会减少一个度为0的节点(一个度为0的节点变为度为1的节点),然后再加一个度为0的节点(新增的节点因为没有子节点,所以增加一个度为0的节点),度为0的节点个数变化之后和之前的个数一样,所以n0仍为1,n2仍为0。然后,我们再加一个节点,这时候会减少一个度为1的节点,然后增加一个度为0的节点和一个度为2的节点 (度为1的节点变来)。通过这个规律我们可以发现度为0的节点比度为2的节点多1个,即n0=n2+1。

同时我们也可以发现树节点的总数为n=n0+n1+n2。通过下图的例子,节点总数为10,它是由A、B、C、D度为2的节点,F、G、H、I、J度为0的叶子节点和E这个度为1的节点组成的。总和为4+1+5=10。

因为这个性质很重要,刷题时会经常出现考察这个性质的题,我从网上找了两个试题来帮助大家对这个性质加深印象:

1.某二叉树共有 399 个结点,其中有 199 个度为 2 的结点,则该二叉树中的叶子结点数为

 ( )
   A 不存在这样的二叉树

   B 200
   C 198
   D 199
答案:C

2.在具有 2n 个结点的完全二叉树中,叶子结点个数为( )

  A n
  B n+1
  C n-1
  D n/2

答案:A

解析:根据题意,我们可以知道:n0+n1+n2=2n,n0=n2+1,所以n0+n1+n0-1=2n,即                   2n0+n1-1=2n我们在接着分析这棵树是一个完全二叉树,所以度为1的节点个数为0或             1,因为n0、n1、n2的值为整数,所以我们可以得出n1为1,然后解开这个方程就知               道n0的值为n,即叶子节点个数为n。

1.4.4二叉树的性质4 

具有n个节点的完全二叉树的深度h=|\log_{2}n|+1(这里的 |x| 表示不大于x的最大整数)。由满二叉树的定义我们可以知道,深度为h的满二叉树的节点数n一定为2^{h}-1,因为这是最多的节点个数。那么对于n=2^{h}-1倒推可以得到满二叉树的深度为h=\log (n+1),完全二叉树我们前面也提到过,它是一棵具有n个节点的二叉树,如果按照层序编号后与同样深度的满二叉树中编号节点在二叉树中的位置完全相同,那他就是完全二叉树,也就是说,它的叶子节点只会出现在最下面两层,它的节点数一定小于等于同等深度的满二叉树的节点数2^{h}-1,但一定多于2^{h-1}-1,即满足2^{h-1}-1<h\leqslant 2^{h}-1,由于节点数n是整数,n\leq 2^{h}-1意味着n< 2^{h}n>2 ^{h-1}-1意味着n\geq 2^{k-1},所以2^{h-1}\leq n< 2^{h},不等式两边取对数,得到h-1\leq \log_{2}n< h,而h作为深度也是整数,因此h=|\log_{2}n|+1。

相关文章:

【数据结构】二叉树:简约和复杂的交织之美

专栏引入&#xff1a; 哈喽大家好&#xff0c;我是野生的编程萌新&#xff0c;首先感谢大家的观看。数据结构的学习者大多有这样的想法&#xff1a;数据结构很重要&#xff0c;一定要学好&#xff0c;但数据结构比较抽象&#xff0c;有些算法理解起来很困难&#xff0c;学的很累…...

信号稳定,性能卓越!德思特礁鲨系列MiMo天线正式发布!

作者介绍 礁鲨系列天线&#xff0c;以其独特的外观设计和强大的性能&#xff0c;成为德思特Panorama智能天线家族的最新成员。这款天线不仅稳定提供5G、WIFI和GNSS信号&#xff0c;更能在各类复杂环境中展现出卓越的性能。它的设计灵感来源于海洋中的礁鲨&#xff0c;象征着力量…...

编程学习技巧——实战

目录 学习思路待续、更新中 学习思路 实战大小项目 翻阅官网手册——学习技术,调试问题 待续、更新中 1 顿号、: 先使用ctrl. &#xff0c;再使用一遍切回 2 下标: 21 2~1~ 3 上标: 2 0 2^{0} 20 $2^{0}$ 4 竖线 | : &#124 ; | 5 空格: &emsp ; 6 换行: &nbs…...

GPU学习(1)

一、为什么要GPU 我们先看一个基本的神经网络计算 YF(x)AxB 这就是一次乘法一次加法 &#xff0c;也叫FMA&#xff0c;(fused multiply-add) 如果矩阵乘&#xff0c;就是上面的那个式子扩展一下&#xff0c;所以又用了这张老图 比如你要多执行好几个yAxB&#xff0c;可能比较简…...

TQSDRPI开发板教程:UDP收发测试

项目资源分享 链接&#xff1a;https://pan.baidu.com/s/1gWNSA9czrGwUYJXdeuOwgQ 提取码&#xff1a;tfo0 LWIP自环教程&#xff1a;https://blog.csdn.net/mcupro/article/details/139350727?spm1001.2014.3001.5501 在lwip自环的基础上修改代码实现UDP的收发测试。新建一…...

opencv进阶 ——(九)图像处理之人脸修复祛马赛克算法CodeFormer

算法简介 CodeFormer是一种基于AI技术深度学习的人脸复原模型&#xff0c;由南洋理工大学和商汤科技联合研究中心联合开发&#xff0c;它能够接收模糊或马赛克图像作为输入&#xff0c;并生成更清晰的原始图像。算法源码地址&#xff1a;https://github.com/sczhou/CodeFormer…...

虚拟机改IP地址

使用场景&#xff1a;当你从另一台电脑复制一个VMware虚拟机过来&#xff0c;就是遇到一个问题&#xff0c;虚拟的IP地址不一样&#xff08;比如&#xff0c;一个是192.168.1.3&#xff0c;另一个是192.168.2.4&#xff0c;由于‘1’和‘2’不同&#xff0c;不是同一网段&#…...

MySQL(二)-基础操作

一、约束 有时候&#xff0c;数据库中数据是有约束的&#xff0c;比如 性别列&#xff0c;你不能填一些奇奇怪怪的数据~ 如果靠人为的来对数据进行检索约束的话&#xff0c;肯定是不行的&#xff0c;人肯定会犯错~因此就需要让计算机对插入的数据进行约束要求&#xff01; 约…...

vue3学习使用笔记

1.学习参考资料 vue3菜鸟教程&#xff1a;https://www.runoob.com/vue3/vue3-tutorial.html 官方网站&#xff1a;https://cn.vuejs.org/ 中文文档: https://cn.vuejs.org/guide/introduction.html Webpack 入门教程&#xff1a;https://www.runoob.com/w3cnote/webpack-tutor…...

微信小程序怎么进行页面传参

微信小程序页面传参的方式有多种&#xff0c;每种方式都有其特定的使用场景和优势。以下是几种常见的页面传参方式&#xff0c;以及它们的具体使用方法和示例&#xff1a; URL参数传值 原理&#xff1a;通过在跳转链接中附加参数&#xff0c;在目标页面的onLoad函数中获取参数…...

隆道出席河南ClO社区十周年庆典,助推采购和供应链数字化发展

5月26日&#xff0c;“河南ClO社区十周年庆典”活动在郑州举办&#xff0c;北京隆道网络科技有限公司总裁助理姚锐出席本次活动&#xff0c;并发表主题演讲《数字化采购与供应链&#xff1a;隆道的探索与实践》&#xff0c;分享隆道公司在采购和供应链数字化转型方面的研究成果…...

NetApp财季报告亮点:全闪存阵列需求强劲,云计算收入增长放缓但AI领域前景乐观

在最新的财季报告中&#xff0c;NetApp的收入因全闪存阵列的强劲需求而显著增长。截至2024年4月26日的2024财年第四季度&#xff0c;NetApp的收入连续第三个季度上升&#xff0c;达到了16.7亿美元&#xff0c;较前一年同期增长6%&#xff0c;超出公司指导中值。净利润为2.91亿美…...

javascript读取本地目录

在JavaScript中&#xff0c;直接读取本地目录的能力受到浏览器安全限制&#xff0c;因为出于隐私和安全考虑&#xff0c;浏览器的JavaScript环境通常不允许直接访问用户的文件系统。然而&#xff0c;随着Web技术的发展&#xff0c;一些现代浏览器引入了File System API或Web Fi…...

Java基础八股

Java基础八股 Java语言Java语言有什么特点Java与C区别Java如何实现跨平台JVMvsJDKvsJRE标识符和关键字的区别是什么自增自减运算符移位运算符continue,break,return的区别是什么final,finally,finalize的区别final关键字的作用时什么 变量 Java语言 Java语言有什么特点 Java是…...

【机器学习300问】102、什么是混淆矩阵?

一、混淆矩阵的定义 混淆矩阵是一种用于评估分类模型性能的评估指标。当模型对数据进行预测并将数据分配到预定义的类别时&#xff0c;混淆矩阵提供了一种直观的方式来总结这些预测与数据实际类别之间的对应关系。具体来说&#xff0c;它是一个表格。 二、分类模型性能评估一级…...

基于SpringBoot3和JDK17,集成H2数据库和jpa

基于SpringBoot3和JDK17&#xff0c;集成H2数据库和jpa 学会用H2数据库&#xff0c;为了快速写出需要处理数据关系的demo。 文章目录 基于SpringBoot3和JDK17&#xff0c;集成H2数据库和jpa工程配置pom.xml文件application.properties文件 练习H2数据库的操作h2数据库的建表自…...

《逆水寒》手游周年庆,热度不减反增引发热议

易采游戏网5月31日最新消息&#xff1a;随着数字娱乐时代的飞速发展&#xff0c;手游市场的竞争愈发激烈。在这样的大背景下&#xff0c;《逆水寒》手游以其独特的古风武侠世界和深度的社交体验&#xff0c;自上线以来便吸引了无数玩家的目光。如今&#xff0c;这款游戏迎来了它…...

Kotlin使用Dagger2但无法生成对应类 Unresolved reference: DaggerMyComponent

最近在使用Dagger2时&#xff0c;遇到这个错误&#xff0c;app/build/generated/source/没有生成对应类&#xff0c;没有生成如下类&#xff0c;网上看了许多博客替换版本&#xff0c;添加dagger2的其他依赖均未成功&#xff0c;最终看到一篇大佬的文章才终于得以解决 解决&am…...

Vue组件通讯⽗组件中通过 provide 来提供变量,然后在⼦组件中通过 inject 来注⼊变量例子

在Vue中&#xff0c;provide 和 inject 主要用于依赖注入&#xff0c;允许祖先组件向其所有子孙组件提供一个依赖&#xff0c;而不论组件层次有多深。这在开发高阶插件/组件库时特别有用。 以下是一个简单的例子&#xff0c;演示了如何在父组件中使用 provide 提供变量&#x…...

教你搞一个比较简单的计时和进度条装饰器

教你搞一个比较简单的计时和进度条装饰器 什么是装饰器为啥要用装饰器呢&#xff1f;上代码&#xff01;如何使用装饰器效果 什么是装饰器 装饰器的英文是&#xff1a;Decorator。装修的英文是&#xff1a;Decoration。顾名思义就是我们要用装饰器在函数func()上搞点儿事儿&am…...

接口测试中缓存处理策略

在接口测试中&#xff0c;缓存处理策略是一个关键环节&#xff0c;直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性&#xff0c;避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明&#xff1a; 一、缓存处理的核…...

阿里云ACP云计算备考笔记 (5)——弹性伸缩

目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...

QMC5883L的驱动

简介 本篇文章的代码已经上传到了github上面&#xff0c;开源代码 作为一个电子罗盘模块&#xff0c;我们可以通过I2C从中获取偏航角yaw&#xff0c;相对于六轴陀螺仪的yaw&#xff0c;qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...

UE5 学习系列(三)创建和移动物体

这篇博客是该系列的第三篇&#xff0c;是在之前两篇博客的基础上展开&#xff0c;主要介绍如何在操作界面中创建和拖动物体&#xff0c;这篇博客跟随的视频链接如下&#xff1a; B 站视频&#xff1a;s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...

镜像里切换为普通用户

如果你登录远程虚拟机默认就是 root 用户&#xff0c;但你不希望用 root 权限运行 ns-3&#xff08;这是对的&#xff0c;ns3 工具会拒绝 root&#xff09;&#xff0c;你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案&#xff1a;创建非 roo…...

Neo4j 集群管理:原理、技术与最佳实践深度解析

Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...

Ascend NPU上适配Step-Audio模型

1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统&#xff0c;支持多语言对话&#xff08;如 中文&#xff0c;英文&#xff0c;日语&#xff09;&#xff0c;语音情感&#xff08;如 开心&#xff0c;悲伤&#xff09;&#x…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码&#xff0c;CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短&#xff0c;所以CPU会不断地切换线程执行&#xff0c;从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

Reasoning over Uncertain Text by Generative Large Language Models

https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...

Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)

Aspose.PDF 限制绕过方案&#xff1a;Java 字节码技术实战分享&#xff08;仅供学习&#xff09; 一、Aspose.PDF 简介二、说明&#xff08;⚠️仅供学习与研究使用&#xff09;三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...