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

15.树与二叉树基础

目录

一. 树,基本术语

二. 二叉树

(1)二叉树

(2)满二叉树

(3)完全二叉树

三. 二叉树的性质

四. 二叉树的存储结构

(1)顺序存储结构

(2)链式存储结构


树形结构:结点之间有分支,具有层次关系。

一. 树,基本术语

树的定义:树(Tree)是n (n≥0)个结点的有限集。
(1)若n = 0,称为空树;
(2)若n >0,则它满足如下两个条件:

  • 有且仅有一个特定的称为根(Root)的结点;
  • 其余结点可分为m(m≥0)个互不相交的有限集T1,T2,T3,....Tm,其中每一个集合本身又是一棵树,并称为根的子树(SubTree)。

树的一些基本术语在下图中展示:

有序树:树中结点的各子树从左至右有次序(最左边的为第一个孩子)。

无序树:树中结点的各子树无次序。

森林:是m(m≥O)棵互不相交的树的集合。

森林与树的关系:把树的根结点删除树就变成了森林。一棵树可以看成是一个特殊的森林。给森林中的各子树加上一个双亲结点,森林就变成了树。

二. 二叉树

(1)二叉树

为何要重点研究每结点最多只有两个“叉”的树?

  • 二叉树的结构最简单,规律性最强;
  • 可以证明,所有树都能转为唯一对应的二叉树,不失一般性。

普通树(多叉树)若不转化为二叉树,则运算很难实现。二叉树在树结构的应用中起着非常重要的作用,因为对二叉的许多操作算法简单,而任何树都可以与二叉树相互转换,这样就解决了。

二叉树:二叉树是n(n≥0)个结点的有限集,它或者是空集(n = 0),或者由一个根结点及两棵互不相交的,分别称作这个根的左子树和右子树的二叉树组成。
二叉树的特点:

  • 每个结点最多有俩孩子(二叉树中不存在度大于2的结点)。
  • 子树有左右之分,其次序不能颠倒。
  • 二叉树可以是空集合,根订以有空的左子树或空的右子树。

注意:二叉树不是树的特殊情况,也不是有序树,而是两个不同的概念。

  • 二叉树结点的子树要区分左子树和右子树,即使只有一棵子树也行区分,说明它是左子树,还是右子树。
  • 树当结点只有一个孩子时,就无须区分它是左还是右的次序。因此二者是不同的。这是二叉树与树的最主要的差别。

也就是二叉树每个结点位置或者说次序都是固定的,可以是空,但是不可以说它没有位置,而树的结点位置是相对于别的结点来说的,没有别的结点时,它就无所谓左右了。

二叉树的五种基本形态如下:

下面我们介绍满二叉树和完全二叉树,这两种特殊的二叉树在顺序存储结构下可以复原。

(2)满二叉树

一棵深度为k且有2^k-1个结点的二叉树称为满二叉树。

特点:1.每一层上的结点数都是最大结数(即每层都满);2.叶子节点全部在最底层; 3.满二叉树在同样深度的二叉树中,结点数,叶子结点数都是最多的。

对满二叉树结点位置进行编号:从根结点开始,自上而下,自左而右。每一结点位置都有元素。

(3)完全二叉树

深度为k的具有n个结点的二叉树,当且仅当其每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应时,称之为完全二叉树。

也可以从满二叉树看完全二叉树:在满二叉树中,从最后一个结点开始,连续去掉任意个结点,即是一棵完全二叉树。一定是连续的去掉! 

特点:1.叶子结点只可能分布在层次最大的两层上;2.对任一结点,如果其右子树的最大层次为i,则其左子树的最大层次必为i或i+1。

三. 二叉树的性质

性质1:二叉树的第i层上最多有2^{i-1}个结点(i>=1),最少有1个结点;

性质2:深度为k的二叉树至多有2^k-1个结点,最少有k个结点;

性质3:对任何一个二叉树T,如果叶子结点数为n0,度为2的结点数为n2,则有:n_0=n_2+1

证明:设总边数为B,结点数为n,显然有:B=n-1,这是由于除了根结点以外,每个结点有且只有一个前驱。

同时,因为结点的度只能为0,1,2,记他们的个数分别是n_0,n_1,n_2,所以有:n=n_0+n_1+n_2B=n_1+2n_2

联立以上三式就可得到:n_0=n_2+1,证毕。

性质4:具有n个结点的完全二叉树的深度是\left \lfloor log_2n \right \rfloor+1,其中\left \lfloor x \right \rfloor表示不超过x的最大整数。

证明:深度为k的完全二叉树,结点个数的范围是:2^{k-1}\leqslant n\leqslant 2^k-1

性质5:对一个具有n个结点的完全二叉树,对一个编号为i的结点:

(1)i>1时,此结点的双亲结点是\left \lfloor i/2 \right \rfloor

(2)此结点的左孩子结点编号是2i,右孩子结点编号是2i+1(如果左右孩子存在);

四. 二叉树的存储结构

(1)顺序存储结构

实现:按满二叉树的结点层次编号,依次存放二叉树中的数据元素。

//二叉树的顺序存储
# define MAXSIZE 100
typedef TElemType SqBiTree[MAXSIZE];
SqBiTree bt;

定义二叉树的顺序存储结构如上所示,使用了一个数组 SqBiTree 来表示二叉树。SqBiTree 是一个 typedef 定义的类型别名,它是一个大小为 MAXSIZE 的数组,数组元素的类型是 TElemTypeTElemType 可以根据具体的需求来定义,表示二叉树节点的数据类型。在这段代码中没有给出 TElemType 的具体定义,需要根据实际情况来确定。通过这段代码,我们可以使用数组 bt 来表示一个二叉树,数组的大小为 MAXSIZE,数组中的元素存储了二叉树的节点数据。这种顺序存储结构的好处是可以快速访问二叉树的任意节点,但是需要提前确定二叉树的最大节点数。

例:根据数组还原二叉树

特点:结点间关系蕴含在数组位置中,浪费空间,适用于满二叉树和完全二叉树。

(2)链式存储结构

二叉树结点的特点:每个结点有左孩子,或者右孩子,所以二叉树的链式结点包含数据域和两个指针域:

typedef struct BiNode{TElemType data;struct BiNode *lchild,*rchild; //左右孩子指针
}BiNode,*BiTree;

有时为了寻找祖先结点,还会增设一个指针*parent,这样结点就有四部分:

lchilddataparentrchild

相关文章:

15.树与二叉树基础

目录 一. 树,基本术语 二. 二叉树 (1)二叉树 (2)满二叉树 (3)完全二叉树 三. 二叉树的性质 四. 二叉树的存储结构 (1)顺序存储结构 (2)链…...

neo4j 图数据库 springboot

一.安装 neo4j社区版在liunx安装部署 https://blog.csdn.net/u013946356/article/details/81736232 二.知识图数据导入 参考:https://notemi.cn/neo4j-import-csv-file-data.html http://openkg.cn/dataset/ch4masterpieces 放在对应的import文件夹下面 导入数据 LOAD C…...

Linux下的系统编程——makefile入门(四)

前言: 或许很多Winodws的程序员都不知道这个东西,因为那些Windows的IDE都为你做了这个工作,但我觉得要作一个好的和professional的程序员,makefile还是要懂。这就好像现在有这么多的HTML的编辑器,但如果你想成为一个专…...

Mybatis的综合案例-学生信息查询系统 用于校验是否真正学习掌握了动态SQL

Mybatis的综合案例-学生信息查询系统 需求一:当用户输入的学生姓名不为空,则只根据学生信息进行查询; 当用户输入的学生姓名为空,且专业不为空,那么就根据学生专业进行学生的查询 需求二:查询所有id值小于5的学生信息…...

力扣:70. 爬楼梯(Python3)

题目: 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢? 来源:力扣(LeetCode) 链接:力扣(LeetCode)官网 - 全球极客…...

陕西广电 HG6341C FiberHome烽火 光猫获取超级密码 改桥接模式 提升网速

光猫默认的路由模式实测在100M宽带下只能跑到60M左右,只有改成桥接模式才能跑满,不损失性能。但是改桥接需要给运营商打电话,有的时候不想麻烦他们,这时获取超级密码进行更改就是一个不错的选择了 分析 之前写了一篇HGU B2 光猫的…...

无涯教程-PHP - 移除的扩展

以下扩展已从PHP 7开始删除- eregmssqlmysqlsybase_ct 以下SAPI已从PHP 7开始删除- aolserverapacheapache_hooksapache2filtercaudiumcontinuityisapimilternsapiphttpdpi3webroxenthttpdtuxwebjames PHP - 移除的扩展 - 无涯教程网无涯教程网提供以下扩展已从PHP 7开始删除…...

笔记:transformer系列

1、和其他网络的比较 自注意力机制适合处理长文本,并行度好,在GPU上,CNN和Self-attention性能差不多,在TPU(Tensor Processing Uni)效果更好。 总结: 自注意力池化层将当做key,value,query来…...

Mysql socket连接测试

配置如下: socket /data/mysql/data/mysql.sock //套接字文件 在数据库没有任何连接的情况下,可以看到3306端口和socket端口都在监听 [mysqlt3-dtpoc-dtpoc-web04 bin]$ netstat -an | grep -i 3306 tcp 0 0 0.0.0.0:3306 0.…...

探究分布式操作系统的本质

探究分布式操作系统的本质 有一位网友问,分布式操作系统的本质是什么,今天就来说说这个话题。 首先,我们需要明确什么是分布式操作系统。 从大范围来理解,分布式操作系统是传统单机操作系统的延伸,可以看作是在多台独…...

opencv-dnn

# utils_words.txt 标签文件 import osimage_types (".jpg", ".jpeg", ".png", ".bmp", ".tif", ".tiff")def list_images(basePath, containsNone):# return the set of files that are validreturn list_file…...

如何选择合适的开源许可证?

🌷🍁 博主猫头虎 带您 Go to New World.✨🍁 🦄 博客首页——猫头虎的博客🎐 🐳《面试题大全专栏》 文章图文并茂🦕生动形象🦖简单易学!欢迎大家来踩踩~🌺 &a…...

【前端】深入解析CSS:选择器、显示模式、背景属性和特征剖析

目录 一、前言二、CSS的复合选择器1、后代选择器①、语法②、注意事项 2、子选择器①、语法②、注意事项 3、并集选择器①、语法②、注意事项 4、链接伪类选择器①、语法②、注意事项 三、CSS元素显示模式转换1、转换为块元素display:block2、转换为行内元素display:inline3、转…...

算法训练营第三十四天(8.23)| 动态规划Part04:01背包

目录 Leecode 1049.最后一块石头的重量II Leecode 494.目标和 Leecode 474.一和零 Leecode 1049.最后一块石头的重量II 题目地址:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 题目类型:01背包 class Solution { public:int…...

【python】tkinter使用多进程打包成exe后multiprocessing无法关闭对应进程

这是由于multiprocessing模块在Windows操作系统下使用fork方法创建子进程时会导致打包成exe后无法正常运行的问题。 可以尝试使用freeze_support函数来解决这个问题。freeze_support函数是在Windows操作系统下用于支持multiprocessing模块的函数。 下面是一个示例代码&#x…...

Redis工具类(缓存操作,Object转换成JSON数据)

依赖spring-data-redis-2.4.1.jar Component Data public class RedisUtils {Autowiredprivate RedisTemplate<String, Object> redisTemplate;Resource(name "stringRedisTemplate")private ValueOperations<String, String> valueOperations;/*** 默…...

Linux 下 Java Socket 编程报 java.net.Exception:Permission denied (权限不足)

本人用Linux部署springboot项目时遇见这个错误&#xff0c;原因很简单&#xff0c;就是端口号没有选对。 在linux系统中&#xff0c;端口号再1024以下的需要root权限&#xff0c;只要把端口改成大于1024的就可以了&#xff0c;但避开一些软件的默认端口&#xff0c;如Tomcat的8…...

IDEA项目实践——VUE介绍与案例分析

系列文章目录 IDEA项目实践——JavaWeb简介以及Servlet编程实战 IDEA项目实践——Spring集成mybatis、spring当中的事务 IDEA项目实践——Spring当中的切面AOP IDEWA项目实践——mybatis的一些基本原理以及案例 IDEA项目实践——Spring框架简介&#xff0c;以及IOC注解 I…...

vue-canvas基本使用和注意事项-动画闪烁效果-自适应适配不同分辨率问题

前言 canvas画布是html的新特性&#xff0c;熟悉画布我们可以完成很多拖拽&#xff0c;标注&#xff0c;动画的功能 使用canvas实现一个小例子很容易&#xff0c;但是真正在项目中使用时&#xff0c;我们需要注意的地方有很多 canvas基本原理就是它基于渲染方法&#xff0c;根…...

Jmeter 如何才能做好接口测试?

现在对测试人员的要求越来越高&#xff0c;不仅仅要做好功能测试&#xff0c;对接口测试的需求也越来越多&#xff01; 所以也越来越多的同学问&#xff0c;怎样才能做好接口测试&#xff1f; 要真正的做好接口测试&#xff0c;并且弄懂如何测试接口&#xff0c;需要从如下几…...

国防科技大学计算机基础课程笔记02信息编码

1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制&#xff0c;因此这个了16进制的数据既可以翻译成为这个机器码&#xff0c;也可以翻译成为这个国标码&#xff0c;所以这个时候很容易会出现这个歧义的情况&#xff1b; 因此&#xff0c;我们的这个国…...

CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型

CVPR 2025 | MIMO&#xff1a;支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题&#xff1a;MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者&#xff1a;Yanyuan Chen, Dexuan Xu, Yu Hu…...

练习(含atoi的模拟实现,自定义类型等练习)

一、结构体大小的计算及位段 &#xff08;结构体大小计算及位段 详解请看&#xff1a;自定义类型&#xff1a;结构体进阶-CSDN博客&#xff09; 1.在32位系统环境&#xff0c;编译选项为4字节对齐&#xff0c;那么sizeof(A)和sizeof(B)是多少&#xff1f; #pragma pack(4)st…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)

CSI-2 协议详细解析 (一&#xff09; 1. CSI-2层定义&#xff08;CSI-2 Layer Definitions&#xff09; 分层结构 &#xff1a;CSI-2协议分为6层&#xff1a; 物理层&#xff08;PHY Layer&#xff09; &#xff1a; 定义电气特性、时钟机制和传输介质&#xff08;导线&#…...

页面渲染流程与性能优化

页面渲染流程与性能优化详解&#xff08;完整版&#xff09; 一、现代浏览器渲染流程&#xff08;详细说明&#xff09; 1. 构建DOM树 浏览器接收到HTML文档后&#xff0c;会逐步解析并构建DOM&#xff08;Document Object Model&#xff09;树。具体过程如下&#xff1a; (…...

【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)

升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点&#xff0c;但无自动故障转移能力&#xff0c;Master宕机后需人工切换&#xff0c;期间消息可能无法读取。Slave仅存储数据&#xff0c;无法主动升级为Master响应请求&#xff…...

SpringCloudGateway 自定义局部过滤器

场景&#xff1a; 将所有请求转化为同一路径请求&#xff08;方便穿网配置&#xff09;在请求头内标识原来路径&#xff0c;然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

Angular微前端架构:Module Federation + ngx-build-plus (Webpack)

以下是一个完整的 Angular 微前端示例&#xff0c;其中使用的是 Module Federation 和 npx-build-plus 实现了主应用&#xff08;Shell&#xff09;与子应用&#xff08;Remote&#xff09;的集成。 &#x1f6e0;️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...

iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈

在日常iOS开发过程中&#xff0c;性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期&#xff0c;开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发&#xff0c;但背后往往隐藏着系统资源调度不当…...