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

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

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

相关文章

单片机UART一对多:同时读取多个传感器基于modbus协议

文章目录 背景MODBUS协议介绍UART接口改一对多参考链接 背景 很多传感器现在都做成了串口模块,如激光测距传感器TOF050,在开发时使用串口功能模块不仅大大加快了我们的开发进度,还能降低功能模块直接的耦合度,专业是功能交给专业…

PMP证书的正确打开方式 get✓

在职场竞争日益激烈的今天,拥有一项专业认证成为了许多人提升自身竞争力的必备条件。而作为项目管理领域的顶级认证,PMP证书备受关注。不过,很多人对于PMP证书的费用颇有顾虑。那么,PMP证书有什么补贴政策呢?下面就为大…

数据库——Redis 常见数据结构以及使用场景分析

文章目录 1. string2. list3. hash4. set5. sorted set 你可以自己本机安装 redis 或者通过 redis 官网提供的在线 redis 环境。 1. string 介绍 :string 数据结构是简单的 key-value 类型。虽然 Redis 是用 C 语言写的,但是 Redis 并没有使用 C 的字符串…

基于JAVA SpringBoot和UniAPP的宠物服务预约小程序

随着社会的发展和人们生活水平的提高,特别是近年来,宠物快速进入人们的家中,成为人们生活中重要的娱乐内容之一,过去宠物只是贵族的娱乐,至今宠物在中国作为一种生活方式得到了广泛的认可,随着人们精神文明…

vue若依导出word文件,简单的实现

首先前端导包,注意exportDocx的导包位置要修改成你自己的 import {exportDocx} from /utils/docUtil/docutil.js; import {addDays} from date-fns; import {listGongyi} from "/api/system/detail";然后新建一个测试按钮 <el-col :span"1.5"><…

<c++开发>通信工具 -之-SOME/IP移植部署 第一篇文章

&#xff1c;c开发&#xff1e;通信工具 -之-SOME/IP移植ubuntu部署 第一篇文章 一 前言 SOME/IP (Scalable service-Oriented MiddlewarE over IP) 是一种通信协议&#xff0c;主要用于嵌入式系统和车载网络中的服务导向通信。SOME/IP是AUTOSAR&#xff08;AUTomotive Open …

Docker安装ES+kibana8.9.1

参考&#xff1a;基于Docker安装Elasticsearch【保姆级教程、内含图解】_docker elasticsearch_Acloasia的博客-CSDN博客 创建网络 docker network create es-net 基于Docker安装Elasticsearch 拉取镜像 docker pull elasticsearch:8.9.1 挂载文件 mkdir -p /usr/local/e…

如何最简单、通俗地理解什么是机器学习?

那就究竟什么是学习呢?诺贝尔经济学奖和图灵奖双料得主、卡耐基梅隆大学的赫伯特 西蒙 (Herbert Simon) 教授是这样定义的&#xff1a;“学习是系统通过经验提升性能的过程”。可以看到&#xff0c;学习是一个过程&#xff0c;并且这里有3个关键词&#xff0c;即经验、提升和…

SQL执行顺序

注意&#xff1a; 本文案例采用 PostgreSQL 作为案例&#xff0c;与 MySQL 语法有些许不同。 目录 1. SQL 完整查询语句2. SQL 执行顺序3. 案例 1. SQL 完整查询语句 SELECT [ALL | DISTINCT] {* | table.* | [table.field1[as alias1][,table.field2[as alias2]][,...]]} FRO…

stm32 无刷电机 V/F控制(无刷电机变频控制)以及与foc(矢量控制)的区别

无刷电机有三种控制方式&#xff0c;方波控制&#xff0c;foc控制以及变频控制&#xff0c;前两章我们讲解了方波和foc的控制方法&#xff0c;今天我们一起来讲一讲什么是无刷电机的变频控制&#xff08;VF&#xff09;以及变频控制的优势是什么。 实验用的硬件还是KY_Motor的无…

【集合学习HashMap】HashMap集合详细分析

HashMap集合详细分析 一、HashMap简介 HashMap 主要用来存放键值对&#xff08;key-value的形式&#xff09;&#xff0c;它基于哈希表的 Map 接口实现&#xff0c;是常用的 Java 集合之一&#xff0c;是非线程安全的。 HashMap 可以存储 null 的 key 和 value&#xff0c;但 …

Kali Linux 2023.3 发布

Offective Security 发布了 Kali Linux 2023.3&#xff0c;这是其渗透测试和数字取证平台的最新版本。 Kali Linux 2023.3 中的新工具 除了对当前工具的更新之外&#xff0c;新版本的 Kali 通常还会引入新的工具。 这次&#xff0c;他们是&#xff1a; Calico – 云原生网络…

NGINX的速率限制(限流)

NGINX 的速率限制&#xff08;限流&#xff09; NGINX最有用但经常被误解和配置错误的功能之一是限流。它允许您限制用户在给定时间段内可以发出的HTTP请求量。 限流可以用于安全目的&#xff0c;例如减慢暴力破解密码的攻击。它可以通过限制请求速率为真实用户的典型值来帮助…

动物体外受精手术VR模拟仿真培训系统保证学生及标本的安全

奶牛是养殖业主要的资源&#xff0c;因此保证奶牛的健康对养殖业的成功和可持续发展具有重要已用&#xff0c;奶牛有一些常见易发病&#xff0c;一旦处理不当&#xff0c;对奶牛业都会造成较大的经济损失&#xff0c;传统的奶牛手术培训实操难度大、风险高且花费大&#xff0c;…

打家劫舍00

题目链接 打家劫舍 题目描述 注意点 如果两间相邻的房屋在同一晚上被小偷闯入&#xff0c;系统会自动报警0 < nums[i] < 400 解答思路 最初想的是使用深度优先遍历&#xff0c;到达任意一个位置时&#xff0c;小偷想要偷窃最高金额&#xff0c;一定要选择后面第2个房…

WEB APIs day5

一、window对象 BOM属于window对象 1.BOM&#xff08;浏览器对象模型&#xff09; bom里面包含着dom,只不过bom我们平时用得比较少&#xff0c;我们经常使用的是dom操作&#xff0c;因为我们页面中的这些标签都是在dom中取的&#xff0c;所以我们操作dom多一点。 window对象…

[Go版]算法通关村第十三关青铜——数字数学问题之统计问题、溢出问题、进制问题

这里写自定义目录标题 数字统计专题题目&#xff1a;数组元素积的符号思路分析&#xff1a;无需真计算&#xff0c;只需判断负数个数是奇是偶复杂度&#xff1a;时间复杂度 O ( n ) O(n) O(n)、空间复杂度 O ( 1 ) O(1) O(1)Go代码 题目&#xff1a;阶乘尾数0的个数思路分析&am…

CPU、MCU、MPU、SOC、SOCPC、概念解释之在嵌入式领域常听到的名词含义

CPU、MCU、MPU、SOC等几个在嵌入式领域学习过程中会涉及到的几个名词。我们来学习一下&#xff0c;资料从网上搜集的&#xff0c;有错的地方可以指出。。。 CPU、MCU、MPU、SOC、SOCPC、 1. CPU2. MPU3.MCUMPU和MCU的区别&#xff1a;4.SOC5. SoPC 1. CPU CPU&#xff0c;即中…

iis站点备份以及端口号查找

文件地址 %windir%\system32\inetsrv\config

iOS 17 及 Xcode 15.0 Beta7 问题记录

1、iOS 17 真机调试问题 iOS 17之后&#xff0c;真机调试Beta版本必须使用Beta版本的Xcode来调试&#xff0c;用以前复制DeviceSupport 方式无法调试&#xff0c;新的Beta版本Xcode中&#xff0c;已经不包含 iOS 17目录。如下图&#xff1a; 解决方案&#xff1a; 1&#x…