二叉树的介绍及其顺序结构的实现

Hello, 亲爱的小伙伴们,你们的作者菌又回来了,之前我们学习了链表、顺序表、栈等常见的数据结构,今天我们将紧跟之前的脚步,继续学习二叉树。

好,咱们废话不多说,开始我们今天的正题。

1.树

1.1树的概念和结构

树是一种非线性的数据结构,他是由n(n >0)个有限的节点组成的一个具有层次结构的集合。

树是因为他的外形看起来像是一颗倒挂的树,也就是根朝上,叶子朝下。

有一个特殊的节点———根节点,根节点没有前驱节点。

除根节点外,其余的节点都被分成了M(M>0)个互不相交的集合,其中每一个集又是和树结构相似的子树,每颗子树的根节点有且只有一颗根节点,可以有无数个子节点,因此树是由递归定义的!

在树型结构中,子树不能有交集,否则就不是树的结构。

比如以下的非树形结构:

 子树是不相交的。

除了根节点外,每个节点有且只有一个父节点。

一颗有N个节点的树有N-1个边。

1.2树的相关术语

 父节点/双亲结点:若有一个节点含有子节点,则这个节点成为子节点的父节点;如上图中的B的父节点为A.

子节点/孩子节点:一个节点含有的子树的根节点,如上图中·:B是A的孩子节点。

节点的度:一个节点有几个孩子节点,他的度就是多少,比如:A的度是2;F的度是2

树的度:树的度指的就是最大节点的度。

分支节点:度不为0的节点。

兄弟节点:具有相同父节点的节点成为兄弟节点,比如E、F节点就是兄弟节点。

节点的层次:从跟开始定义起,跟为第1层,根节点的子节点为第2层,以此类推。

树的高度和深度:树中节点的最大层次。比如上面的树的最大层次就是4,所以这棵树的深度就是4.

子孙:以某节点为根的子树中任意节点都可以称为该节点的子孙。

森林:多颗不相干的树的集合就是森林。

1.3树的表示

孩子兄弟表示法:

树的结构相较于线性表就要复杂的多,要存储起来也比较麻烦,既要保存值又要保存节点与节点之间的关系,实际上树的表示方式有很多种,比如:双亲表示法、孩子表示法、孩子双亲表示法、以及孩子兄弟表示法等,这里我们就简单的看看孩子兄弟表示法:

struct TreeNode
{
struct Node* child; // 左边开始的第⼀个孩⼦结点
struct Node* brother; // 指向其右边的下⼀个兄弟结点
int data; // 结点中的数据域
}

1.4树形结构的应用场景 

文件系统是计算机存储和文件管理的一种方式,他利用树形结构来组织和管理文件和文件夹,在文文件夹中,树的结构被广泛的应用,他通过父节点和子节点之间的关系来展示不同层级的文件和文件夹之间的关系。

 2.二叉树

2.1概念与结构

在树的结构中。我们常见的就是二叉树,一颗二叉树的节点的设计一个有限的集合,该集合是由根节点加上两颗别称为左子树和右子树的集合所构成的。

从上面的图我们能得出一些相关的信息:
1.二叉树不存在度大于2的节点。

2.二叉树的子树又左右之分,次序不能颠倒,因此二叉树是有序树。

注意:对于任何的二叉树都是由以下的情况复合而成的:

 

 2.2特殊的二叉树

一颗二叉树,如果每一层的节点数都达到了最大值,则这棵树就是满二叉树。也就是说,如果这颗树的层数是k。且节点的总数是2^k - 1,则他就是满二叉树。

完全二叉树是效率非常高的数据结构,完全二叉树是由满二叉树的概念引述而来的。对于深度为k的,有n个节点的二叉树吗,当且仅当其每一个节点都与深度为k的满二叉树中的编号从1到n的节点一一对应就可称其为二叉树,要注意:满二叉树是一种特殊的完全二叉树.

2.3二叉树的存储结构

二叉树一般可以使用两种储存结构,一种是顺序结构,一种是链式结构 

2.3.1顺序结构

顺序结构存储就是使用数组作为底层结构,一般数组适用于表示完全二叉树,因为不是完全二叉树就有空间的浪费,完全二叉树更适合使用顺序结构存储。

 3.实现顺序结构二叉树

一般对堆使用使用顺序结构的数组来存储数组,堆是一种特殊的二叉树,具有二叉树的特性同时,还具备其他的特性。

3.1堆的结构和概念

如果有一个关键码的集合K = {k_{0},k_{1},k_{2},k_{3},.....k_{n -1}},他把所有的元素按照完全二叉树的存储结构存储起来,在一个一维数组中,并满足^{_{}}k_{i} <= k_{2*i + 1}k_{i}>= k_{2*i + 1}k_{i}<= k_{2*i+2})i = 0、1、2、3.....,则称之为小堆(或大堆)。将根节点最大的堆叫做最大堆或者是大根堆,根节点最小的堆叫做小堆和小根堆。

堆具有以下的性质:

堆中某个节点的值总是不大于或不小于其父节点的值。

堆是一颗完全二叉树 

• 对于具有 n 个结点的完全⼆叉树,如果按照从上⾄下从左⾄右的数组顺序对所有结点从
0 开始编号,则对于序号为 i 的结点有:
1. 若 i>0 , i 位置结点的双亲序号: (i-1)/2 ; i=0 , i 为根结点编号,⽆双亲结点
2. 若 2i+1<n ,左孩⼦序号: 2i+1 , 2i+1>=n 否则⽆左孩⼦

3. 若 2i+2<n ,右孩⼦序号: 2i+2 , 2i+2>=n 否则⽆右孩⼦

 3.2堆的实现

首先我们还是要先创建三个文件,来实现堆:

3.2.1堆的定义

底层的结构·是数组,所以对结构的定义就和顺序表的定义差不多

typedef int HpDataType;
typedef struct Heap
{HpDataType *arr;int size;//记录有效元素的个数int capacity;//记录申请的空间容量
}Hp;

3.2.2堆的初始化(HpInit)和销毁(HpDestroy)

由于底层结构就是由数组构成的,所以在初始化上,顺序表和堆十分的相似:

1.HpInit

定义:

//堆的初始化
void HpInit(Hp* php);

实现:

/堆的初始化
void HpInit(Hp* php)
{assert(php);php->capacity = php->size = 0;php->arr = NULL;
}

2.HpDstroy

定义:

//堆的销毁
void HpDstroy(Hp* php);

实现:

void HpDstroy(Hp* php)
{assert(php);free(php->arr);php->arr = NULL;php->capacity = php->size = 0;
}

由于底层结构的相似性,我们在实现堆的从初始化和销毁时,就和顺序表的初始化和销毁相似。

测试:

初始化时,s.arr = NULL; s.capacity = s.size = 0;

3.2.3 堆数据的插入(HpPush)(入堆)

堆数据的插入和顺序表的数据插入也有相似之处:

定义:

//堆的数据插入
void HpPush(Hp* php, HpDataType x);

实现:


void HpPush(Hp* php, HpDataType x)
{assert(php);//判断空间是否足够if (php->capacity == php->size){//扩容int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HpDataType* ptmp = (HpDataType*)realloc(php->arr, sizeof(HpDataType) * newcapacity);if (ptmp == NULL){perror("realloc Fail!!");exit(1);}php->arr = ptmp;php->capacity = newcapacity;}php->arr[php->size++] = x;AdjustUp(php->arr, php-> size - 1);//向上调整算法}

和顺序表的数据插入相似,我们都要先确保空间的充足,才能进行插入操作!!

重要的是,我们需要理解向上调整算法的含义:

3.2.3.1向上调整算法(AdjustUp)

向上调整算法:将新的数据插入到数组的尾部,在进行向上的调整,直到满足堆的结构!!

先将元素插到堆的末尾,即最后一个孩子之后

插入之后如果堆的性质遭到破坏,将新插入的节点顺着其双亲往上调整到合适得位置就好额!!

 代码实现:

void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}void AdjustUp(HpDataType* arr, int child)
{int parent = (child - 1) / 2;while (child > 0)//当child节点为0是,该节点已经到达这颗树的顶端,无需再调整!!{if (arr[child] > arr[parent])//这里采用 < 最后就能建成小堆;采用>就能建成大堆{Swap(&arr[child], &arr[parent]);child = parent;parent = (child - 1 )/ 2;}else{break;}}
}

代码测试:

我们建成的是大堆吗?

我们画图来验证一下:

 

 从这里我们就能看出,建成大堆成功!!

3.2.4堆中数据的删除(HpPop)(出堆)

注意:出堆,与出队列的定义相似,出堆是将堆头的数据删去!!

定义:

//堆中数据的删除!!
void HpPop(Hp* php);

实现:
我们可以怎样来删去堆头的数据呢?

也许,我们可以让堆头的数据与堆尾的数据相交换,删除堆尾的数据容易,且不会改变原来的数据结构。

所以我们又会涉及到一种在堆中的向下调整算法:

3.2.4.1向下调整算法(AdjustDown)

注意:向下调整算法有一个前提:左右子树必须为一个堆!! 

1.将堆顶元素与最后一个元素交换 

2.删除堆中的最后一个元素

3.将堆顶的元素向下调整直到满足堆的特性为止!

 

 代码实现:

void AdjustDown(int* arr, int parent, int n)
{int child = parent  * 2 + 1;if (arr[child] < arr[child + 1]){child++;}while (child < n)//注意:child最大时为 n-1,注意不能越界!!{if (arr[child] > arr[parent]){Swap(&arr[parent], &arr[child]);parent = child;child = 2 * parent + 1;}elsebreak;}
}

所以完整的代码我们就可以写成:

void AdjustDown(int* arr, int parent, int n)
{int child = parent * 2 + 1;if (arr[child] < arr[child + 1])//找出左右孩子节点中数值较大那个{child++;}while (child < n){if (arr[child] > arr[parent])//如果孩子节点的值比父节点大,就进行交换{Swap(&arr[parent], &arr[child]);parent = child;child = 2 * parent + 1;}elsebreak;}
}
//堆中数据的删除!!
void HpPop(Hp* php)
{assert(php && php->size);//最后一个元素与第一个元素相交换Swap(&php->arr[0], &php->arr[php->size - 1]);php->size--;//开始向下调整AdjustDown(php->arr, 0, php->size);
}

代码测试:

我们来比对一下删除元素前后的效果:

 

 可以看到交换后依然符合大堆的性质!!!

3.2.5取堆顶元素和堆的判空操作(HpTop && HpIsEmty)

在实现堆的部分性质时,我们很容易就会联想到,我们曾经学习过的数据结构,如:栈、队列和顺序表单链表等。

这里的取堆顶元素就和栈的性质相似,堆的数据也不能进行随机访问,所以,想要进行堆数据的打印,就要进行数据的以此访问和打印,所以我们需要结合判空、取堆顶元素和去堆顶元素来实现堆数据的打印。

判空和取堆顶数据的定义:
 

//取堆顶元素
HpDataType HpTop(Hp* php);
//判空
bool HpIsEmpty(Hp* php);

这里的两个函数实现和之前的操作相似,我们这里就不多叙述,代码也十分的简单,感兴趣的朋友也可以去看看我以前的文章:
 

HpDataType HpTop(Hp* php)
{assert(php && php->size);return php->arr[0];
}
bool HpIsEmpty(Hp* php)
{assert(php);return php->size == 0;
}

所以最后我们就可以将堆中的数据打印出来:

这样我们就实现了堆数据的打印了!! 

结语

二叉树的顺序结构我们就学习到这里,感谢大家的阅读,如果你有不懂得问题也欢迎大家来评论区理性讨论,咱们下期再见,拜拜!!

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

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

vue3框架Arco Design输入邮箱选择后缀

使用&#xff1a; <a-form-item field"apply_user_email" label"邮箱&#xff1a;" ><email v-model"apply_user_email" class"inputborder topinputw"></email> </a-form-item>import email from /componen…

Java语言程序设计基础篇_编程练习题***15.35/15.34 (动画:自回避随机漫步)

***15.34 (模拟&#xff1a;自回避随机漫步) 在一个网格中的自回避漫步是指从一个点到另一点的过程中&#xff0c;不重复两次访问一个点。自回避漫步已经广泛应用在物理、化学和数学学科中。它们可以用来模拟像溶剂和聚合物这样的链状物。编写一个程序&#xff0c;显示一个从中…

Educational Codeforces Round 168 (Rated for Div. 2)

据说这场比赛非常简单&#xff0c;但本蒟蒻却认为比以往还要难(;༎ຶД༎ຶ) A.Strong Password 输入样例&#xff1a; 4 a aaa abb password输出样例&#xff1a; wa aada abcb pastsword思路&#xff1a; 我们只需在原来字符串中连续的两个字符之间插入一个不同的字符&…

React 学习——自定义Hook实现,使用规则

使用规则&#xff1a; 只能在组件中或者其他自定义Hook函数中调用只能在组件的顶层调用&#xff0c;不能嵌套在 if、for、其他函数中 import { useState } from "react"// 封装函数 function useToggle(){const [show,setShow] useState(true);const toggle ()&…

机器学习算法——常规算法,在同的业务场景也需要使用不同的算法(二)

&#x1f468;‍&#x1f4bb;个人主页&#xff1a;开发者-曼亿点 &#x1f468;‍&#x1f4bb; hallo 欢迎 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! &#x1f468;‍&#x1f4bb; 本文由 曼亿点 原创 &#x1f468;‍&#x1f4bb; 收录于专栏&#xff1a…

火山引擎VeDI数据技术分享:两个步骤,为Parquet降本提效

更多技术交流、求职机会&#xff0c;欢迎关注字节跳动数据平台微信公众号&#xff0c;回复【1】进入官方交流群 作者&#xff1a;王恩策、徐庆 火山引擎 LAS 团队 火山引擎数智平台 VeDI 是火山引擎推出的新一代企业数据智能平台&#xff0c;基于字节跳动数据平台多年的“数据…

迪文屏使用记录

项目中要使用到迪文屏&#xff0c;奈何该屏资料太琐碎&#xff0c;找的人头皮发麻&#xff0c;遂进行相关整理。 屏幕&#xff1a;2.4寸电容屏 型号&#xff1a;DWG32240C024_03WTC 软件&#xff1a;DGUS_V7.647 1.竖屏横显 打开软件左下方的配置文件生成工具&#…

前端如何实现更换项目主题色的功能?

1、场景 有一个换主题色的功能&#xff0c;如下图&#xff1a; 切换颜色后&#xff0c;将对页面所有部分的色值进行重新设置&#xff0c;符合最新的主题色。 2、实现思路 因为色值比较灵活&#xff0c;可以任意选取&#xff0c;所以最好的实现方式是&#xff0c;根据设置的…

解读权限信息

1. 权限信息 在查看工作目录的内容时&#xff0c;经常看到如下格式的信息&#xff1a; 第一列&#xff1a;文件/文件夹的权限&#xff08;或者叫权限控制信息&#xff09;&#xff1b; 第二列&#xff1a;文件/文件夹的所属用户&#xff1b; 第三列&#xff1a;文件/文件夹…

苹果密码解锁工具已注册专业版_不限制电脑

Aiseesoft iPhone Unlocker&#xff1a;轻松解锁iPhone。功能强大&#xff1a;一键移除4位、6位密码、Touch ID和Face ID。隐私保护&#xff1a;创建密码&#xff0c;安全无忧。数据提醒&#xff1a;解锁时&#xff0c;注意数据和设置将被清除。Apple ID 解锁&#xff1a;快速删…

Redis 与 Scrapy:无缝集成的分布式爬虫技术

1. 分布式爬虫的概念 分布式爬虫系统通过将任务分配给多个爬虫节点&#xff0c;利用集群的计算能力来提高数据抓取的效率。这种方式不仅可以提高爬取速度&#xff0c;还可以在单个节点发生故障时&#xff0c;通过其他节点继续完成任务&#xff0c;从而提高系统的稳定性和可靠性…

信息系统的分类_20240731

1:信息系统的分类 1.1:业务处理系统(TPS) 又称为电子数据处理系统.TPS是服务于组织管理层次中最低层、最基础的信息系统 功能:数据输入、数据处理(批处里、OLTP)1.2:管理信息系统(MIS) 是由业务处理系统发展而来的,是在TPS基础上引进大量管理方法对企业整体信息进行处理 MI…

C#知识|文件与目录操作:目录的操作

哈喽,你好啊,我是雷工! 前边学习了文件的删除、复制、移动,接下来学习目录的操作。 以下为学习笔记。 01 效果演示 1.1、显示指定目录下的所有文件 在左侧的文本框中显示出F:\F004-C#目录下的所有文件, 演示效果: 1.2、显示指定目录下的所有子文件 在左侧的文本框中显…

【机器学习西瓜书学习笔记——模型评估与选择】

机器学习西瓜书学习笔记【第二章】 第二章 模型评估与选择2.1训练误差和测试误差错误率误差 欠拟合和过拟合2.2评估方法留出法交叉验证法自助法 2.3性能度量查准率、查全率与F1查准率查全率F1 P-R曲线ROC与AUCROCAUC 代价敏感错误率与代价曲线代价曲线 2.4比较检验假设检验&…

三品软件与合作伙伴提供管家式服务 推动企业研发管理创新

近日&#xff0c;三品软件携手核心合作伙伴&#xff0c;秉承着为本地客户提供全方位的管家式服务。坚持采用“管理咨询IT整体规划PLM本地交付”的服务模式&#xff0c;凭借卓越的服务质量和专业度&#xff0c;赢得了客户的高度信任和好评&#xff0c;并成功签约多个PLM项目。 …

SAP PowerDesigner@官网下载

背景 略 问题 略 解决 用户可以通过访问SAP支持网站的首页&#xff08;‌https://support.sap.com/home.html&#xff09;‌&#xff0c;‌然后导航到“Software Downloads”&#xff08;‌软件下载&#xff09;‌部分来访问SAP软件的下载入口。‌在这里&#xff0c;‌用户可…

第一章:为了女神小芳!【配套课时:SQL注入攻击原理 实战演练】

目录 一、原理 二、步骤 1、测试是否存在注入点 2、判断字段数 3、判断回显位置 4、判断数据库和版本 5、判断表名 6、判断字段名 7、获取表的数据 一、原理 SQL数值型注入 二、步骤 点击查看出现id&#xff0c;这里可能存在注入点 1、测试是否存在注入点 http://p…

UVC驱动分析(一)

UVC驱动分析 UVC驱动简介Linux video框架分层UVC驱动注册UVC驱动注册入口函数UVC设备探测初始化UVC描述符解析V4L2设备注册UVC控制参数初始化UVC video驱动注册UVC 状态初始化 UVC驱动简介 UVC全称为USB Video Class&#xff0c;即&#xff1a;USB视频类&#xff0c;是一种为U…

向量数据库性能测试工具(VectorDBBench.com)性价比排名

排名 向量数据库(不同硬件配置) 价格/性能比 QP$(每百万次查询所花费的价格)中型数据集, OpenAI 无标量过滤 QP$(每百万次查询所花费的价格)中型数据集, OpenAI 低标量过滤 QP$(每百万次查询所花费的价格)中型数据集, OpenAI 高标量过滤 QP$(每百万次查询所花费的价…

25考研数据结构复习·7.1/7.2查找的基本概念-顺序查找和折半查找

查找的基本概念 基本概念 查找查找表关键字&#xff08;唯一标识&#xff09;对查找表的常见操作 查找符合条件的数据元素——静态查找表插入、删除某个元素——且也要进行操作a的&#xff08;动态查找表&#xff09;评价指标 查找长度——需要比较的关键字次数 平均查找长度…