【数据结构】二叉树:简约和复杂的交织之美
专栏引入:
哈喽大家好,我是野生的编程萌新,首先感谢大家的观看。数据结构的学习者大多有这样的想法:数据结构很重要,一定要学好,但数据结构比较抽象,有些算法理解起来很困难,学的很累。我想让大家知道的是:数据结构非常有趣,很多算法是智慧的结晶,我希望大家在学习数据结构的过程是一种愉悦的心情感受。因此我开创了《数据结构》专栏,在这里我将把数据结构内容以有趣易懂的方式展现给大家。
1.二叉树
生活中,我们经常会遇到管理大量数据的情况,比如图书馆书记的分类。而二叉树这种数据结构正是用来解决这种问题的,当我们阅读书时,书中的每个条目都有专门分类和子分类,为了更好的组织这些内容,需要使用一种高效的数据结构来存储和访问信息。下面举个简单的例子来引入二叉树,我们在中学学习生物时知道了植物主要分为:种子植物、苔藓植物等。那它们是如何进行分类的呢?我们看下面这张图片:
通过这种方式,我们可以逐级展开二叉树,更详细的组织植物分类的信息,每个节点都代表一个特定的分类,而子节点则代表该分类的下一级分类。这样我们可以更加轻松的查找和比较不同的植物分类信息。下面我们就来揭开二叉树的神秘面纱。
1.1二叉树的定义
二叉树是n(n>=0)个节点的有限集合,该集合或者为空集合(称为空二叉树),或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成。在下面的图中,左边的就是一棵二叉树,而右边的因为它的F节点有3个子节点,所以它不是二叉树。
1.2二叉树的特点
二叉树具有以下几个特点:
- 每个节点最多有两个子节点,所以二叉树中不存在度大于2的节点。注意不是一定要有两个节点,而是最多有两个节点,没有节点或者只有一个节点也是可以滴。
- 左子树和右子树是有顺序的,次序不能颠倒,因此二叉树是有序树。
- 即使结构中某节点只有一个子节点,也要区分它是左节点还是右节点。
二叉树具有以下五种基本形态:空二叉树、只有一个根节点、根节点只有左子树、根节点只有右子树、根节点既有左子树又有右子树。
1.3特殊的二叉树
1.3.1斜树
斜树,顾名思义,斜树一定是斜的,但是向哪里斜还是有讲究的。所有节点都只有左子树的二叉树的叫做左斜树,所有节点都只有右子树的二叉树叫做右斜树,这两者统称为斜树。在上一张图中根节点只有左子树和根节点只有右子树就是左斜树和右斜树的一个简单例子。斜树也有很明显的特点,就是每一层只有一个节点,节点个数和二叉树的深度相同。肯定也有人好奇:这也叫树?这不和线性表一样吗?确实,线性表可以理解成树的一种极其特殊的表现形式。
1.3.2满二叉树
我们通常举例子都是参差不齐的二叉树,那是否存在完美的二叉树呢?我们看下面这张图片:
看来完美的二叉树是存在的。在一棵二叉树中,如果所有分支节点都存在左子树和右子树,并且所有叶子都在一层上,这样的二叉树叫做满二叉树。下面就是一个满二叉树,从样子上看就感觉它很完美:
单是每一个节点都存在左右子树,不能算满二叉树,还必须要所有叶子都在一层上,这样才能做到整棵树的平衡。因此,满二叉树的特点有:
- 叶子只能出现在最底层,出现在其他层就不能达到平衡状态。
- 除了叶子节点外,每个节点都有两个子节点。即所有非叶子节点的度都为2.
- 在同样深度的二叉树中,满二叉树的节点个数最多,叶子数最多。
满二叉树的每一层都是满的,没有任何缺失节点。由于每个节点都具有两个子节点,满二叉树的平衡性很好。这使得在满二叉树上执行搜索、插入和删除等操作的平均时间复杂度非常高效。在满二叉树中,从根节点到任意一个叶子节点的路径长度都相同,是最短的路径。满二叉树常用于堆数据结构。满二叉树在实际应用中比较少见,因为它要求节点数必须是2的幂次方,而真实的数据往往不具备这样的特点。
1.3.3完全二叉树
对一棵具有n个节点的二叉树进行层序编号,如果编号为i(1≤i≤n)的节点与同样深度的满二叉树中的编号为i的节点在二叉树中的位置完全相同,则这棵二叉树称为完全二叉树。如下图:
在理解时,我们要注意区分满二叉树和完全二叉树。首先,从字面上区分,“完全”和“满”的区别,满二叉树一定是一棵完全二叉树,完全二叉树不一定是满的。其次,完全二叉树的所有节点和同样深度的满二叉树,它们按层序编号相同的节点,是一一对应的,这个关键词是按层序编号。像下面的二叉树中,因为5节点没有右子树,只有左子树,使得按层序编号的第11个编号空档了,它不是完全二叉树:
只有下面图中的树,尽管它不是满二叉树,但编号是连续的,所以它是完全二叉树:
这里我们就可以总结出完全二叉树的一些特点:
- 叶子节点只能出现在最后两层。
- 最下层的叶子节点一定是集中在左部连续位置。
- 倒数第二层,如果有叶子节点,一定都在右部连续位置。
- 如果节点的度为1,则该节点只有左孩子,及不存在右子树的情况。
- 同样节点数的二叉树,完全二叉树的深度最小。
通过上面的理解,我们也知道了一个判断二叉树是否是完全二叉树的方法:那就是看树的示意图,给每个节点按照满二叉树的结构逐层顺序编号,如果编号出现空挡,就说明不是完全二叉树,反之就是。完全二叉树在实际应用中较为常见,它具有以下的优点:
- 节点的存储更加高效:由于完全二叉树的特点,可以使用数组来存储节点。这样可以大大节省存储空间,因为不需要为每个节点额外存储左右子节点的指针。
- 访问效率更高:由于节点的存储更加高效,可以使用数组的索引来访问节点。这样可以实现随机访问,访问的时间复杂度是O(1)。而在其他类型的二叉树中,如果要找到某个节点,需要从根节点出发进行遍历,访问的时间复杂度较高。
1.4二叉树的性质
1.4.1二叉树的性质1
在二叉树的第i层至多有个节点(i≥1)。这个性质很容易理解,我们观察一下满二叉树:
第一层是根节点,只有一个,所以=1。第二层有两个,
=2。第三层有四个,
=4。第四层有八个,
=8。通过数据归纳法的论证,我们可以很轻松的得出在二叉树的第i层上至多有
个节点(i≥1)的结论。这个性质的重要性在于它给出了二叉树的每一层上节点数量的上限。通过这个性质,我们可以更好地理解和分析二叉树的结构。同时,这个性质也为二叉树的遍历、搜索等操作提供了重要的依据和限制。
1.4.2二叉树的性质2
深度为k的二叉树至多有个节点(k≥1)。这里一定要注意,是
后再减1,而不是
。如果不注意的话很容易和性质1搞混。深度为k也就是有k层的二叉树,我们接着以上面那个满二叉树为例来看:如果只有一层,至多有
个节点。如果只有两层,至多有
个节点。如果只有三层,至多有
个节点。如果只有四层,至多有
个节点通过数据归纳法,我们可以得出:二叉树的深度为k层,此二叉树至多有
个节点。
1.4.3二叉树的性质3
对于任何一棵二叉树,如果其终端节点数为,度为2的节点数为
,则
。这是一个非常重要的性质,首先我们从二叉树的构建过程一步一步来理解它:
首先,我们先看只有一个根节点的时候,度为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
答案:C2.在具有 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=||+1(这里的 |x| 表示不大于x的最大整数)。由满二叉树的定义我们可以知道,深度为h的满二叉树的节点数n一定为
,因为这是最多的节点个数。那么对于n=
倒推可以得到满二叉树的深度为h=
,完全二叉树我们前面也提到过,它是一棵具有n个节点的二叉树,如果按照层序编号后与同样深度的满二叉树中编号节点在二叉树中的位置完全相同,那他就是完全二叉树,也就是说,它的叶子节点只会出现在最下面两层,它的节点数一定小于等于同等深度的满二叉树的节点数
,但一定多于
,即满足
,由于节点数n是整数,
意味着
,
意味着
,所以
,不等式两边取对数,得到
,而h作为深度也是整数,因此h=|
|+1。
相关文章:
【数据结构】二叉树:简约和复杂的交织之美
专栏引入: 哈喽大家好,我是野生的编程萌新,首先感谢大家的观看。数据结构的学习者大多有这样的想法:数据结构很重要,一定要学好,但数据结构比较抽象,有些算法理解起来很困难,学的很累…...

信号稳定,性能卓越!德思特礁鲨系列MiMo天线正式发布!
作者介绍 礁鲨系列天线,以其独特的外观设计和强大的性能,成为德思特Panorama智能天线家族的最新成员。这款天线不仅稳定提供5G、WIFI和GNSS信号,更能在各类复杂环境中展现出卓越的性能。它的设计灵感来源于海洋中的礁鲨,象征着力量…...
编程学习技巧——实战
目录 学习思路待续、更新中 学习思路 实战大小项目 翻阅官网手册——学习技术,调试问题 待续、更新中 1 顿号、: 先使用ctrl. ,再使用一遍切回 2 下标: 21 2~1~ 3 上标: 2 0 2^{0} 20 $2^{0}$ 4 竖线 | : | ; | 5 空格: &emsp ; 6 换行: &nbs…...

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

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

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

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

MySQL(二)-基础操作
一、约束 有时候,数据库中数据是有约束的,比如 性别列,你不能填一些奇奇怪怪的数据~ 如果靠人为的来对数据进行检索约束的话,肯定是不行的,人肯定会犯错~因此就需要让计算机对插入的数据进行约束要求! 约…...

vue3学习使用笔记
1.学习参考资料 vue3菜鸟教程:https://www.runoob.com/vue3/vue3-tutorial.html 官方网站:https://cn.vuejs.org/ 中文文档: https://cn.vuejs.org/guide/introduction.html Webpack 入门教程:https://www.runoob.com/w3cnote/webpack-tutor…...
微信小程序怎么进行页面传参
微信小程序页面传参的方式有多种,每种方式都有其特定的使用场景和优势。以下是几种常见的页面传参方式,以及它们的具体使用方法和示例: URL参数传值 原理:通过在跳转链接中附加参数,在目标页面的onLoad函数中获取参数…...

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

NetApp财季报告亮点:全闪存阵列需求强劲,云计算收入增长放缓但AI领域前景乐观
在最新的财季报告中,NetApp的收入因全闪存阵列的强劲需求而显著增长。截至2024年4月26日的2024财年第四季度,NetApp的收入连续第三个季度上升,达到了16.7亿美元,较前一年同期增长6%,超出公司指导中值。净利润为2.91亿美…...
javascript读取本地目录
在JavaScript中,直接读取本地目录的能力受到浏览器安全限制,因为出于隐私和安全考虑,浏览器的JavaScript环境通常不允许直接访问用户的文件系统。然而,随着Web技术的发展,一些现代浏览器引入了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、什么是混淆矩阵?
一、混淆矩阵的定义 混淆矩阵是一种用于评估分类模型性能的评估指标。当模型对数据进行预测并将数据分配到预定义的类别时,混淆矩阵提供了一种直观的方式来总结这些预测与数据实际类别之间的对应关系。具体来说,它是一个表格。 二、分类模型性能评估一级…...
基于SpringBoot3和JDK17,集成H2数据库和jpa
基于SpringBoot3和JDK17,集成H2数据库和jpa 学会用H2数据库,为了快速写出需要处理数据关系的demo。 文章目录 基于SpringBoot3和JDK17,集成H2数据库和jpa工程配置pom.xml文件application.properties文件 练习H2数据库的操作h2数据库的建表自…...

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

Kotlin使用Dagger2但无法生成对应类 Unresolved reference: DaggerMyComponent
最近在使用Dagger2时,遇到这个错误,app/build/generated/source/没有生成对应类,没有生成如下类,网上看了许多博客替换版本,添加dagger2的其他依赖均未成功,最终看到一篇大佬的文章才终于得以解决 解决&am…...
Vue组件通讯⽗组件中通过 provide 来提供变量,然后在⼦组件中通过 inject 来注⼊变量例子
在Vue中,provide 和 inject 主要用于依赖注入,允许祖先组件向其所有子孙组件提供一个依赖,而不论组件层次有多深。这在开发高阶插件/组件库时特别有用。 以下是一个简单的例子,演示了如何在父组件中使用 provide 提供变量&#x…...

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

【Axure高保真原型】引导弹窗
今天和大家中分享引导弹窗的原型模板,载入页面后,会显示引导弹窗,适用于引导用户使用页面,点击完成后,会显示下一个引导弹窗,直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...
PHP和Node.js哪个更爽?
先说结论,rust完胜。 php:laravel,swoole,webman,最开始在苏宁的时候写了几年php,当时觉得php真的是世界上最好的语言,因为当初活在舒适圈里,不愿意跳出来,就好比当初活在…...

CMake基础:构建流程详解
目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

HarmonyOS运动开发:如何用mpchart绘制运动配速图表
##鸿蒙核心技术##运动开发##Sensor Service Kit(传感器服务)# 前言 在运动类应用中,运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据,如配速、距离、卡路里消耗等,用户可以更清晰…...
代码随想录刷题day30
1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...
JS手写代码篇----使用Promise封装AJAX请求
15、使用Promise封装AJAX请求 promise就有reject和resolve了,就不必写成功和失败的回调函数了 const BASEURL ./手写ajax/test.jsonfunction promiseAjax() {return new Promise((resolve, reject) > {const xhr new XMLHttpRequest();xhr.open("get&quo…...
第八部分:阶段项目 6:构建 React 前端应用
现在,是时候将你学到的 React 基础知识付诸实践,构建一个简单的前端应用来模拟与后端 API 的交互了。在这个阶段,你可以先使用模拟数据,或者如果你的后端 API(阶段项目 5)已经搭建好,可以直接连…...
Monorepo架构: Nx Cloud 扩展能力与缓存加速
借助 Nx Cloud 实现项目协同与加速构建 1 ) 缓存工作原理分析 在了解了本地缓存和远程缓存之后,我们来探究缓存是如何工作的。以计算文件的哈希串为例,若后续运行任务时文件哈希串未变,系统会直接使用对应的输出和制品文件。 2 …...

uni-app学习笔记三十五--扩展组件的安装和使用
由于内置组件不能满足日常开发需要,uniapp官方也提供了众多的扩展组件供我们使用。由于不是内置组件,需要安装才能使用。 一、安装扩展插件 安装方法: 1.访问uniapp官方文档组件部分:组件使用的入门教程 | uni-app官网 点击左侧…...
怎么开发一个网络协议模块(C语言框架)之(六) ——通用对象池总结(核心)
+---------------------------+ | operEntryTbl[] | ← 操作对象池 (对象数组) +---------------------------+ | 0 | 1 | 2 | ... | N-1 | +---------------------------+↓ 初始化时全部加入 +------------------------+ +-------------------------+ | …...