【数据结构必会基础】关于树,你所必须知道的亿些概念

news/2024/3/29 23:33:02/文章来源:https://blog.csdn.net/qq_63992711/article/details/129201047

目录

1.什么是树

1.1浅显的理解树

1.2 数据结构中树的概念

2.树的各种结构概念

2.1 节点的度

2.2 根节点/叶节点/分支节点

2.3 父节点/子节点

2.4祖先节点/子孙节点

 2.5兄弟节点

2.6树的度

2.7节点的层次

2.8森林

 3. 如何用代码表示一棵树

3.1链式结构

3.1.1 树节点的定义方式1(指针数组)

3.1.2 树节点的定义方式2(左孩子右兄弟表示法)

3.2数组结构

3.2.1 每个节点存父亲下标

3.2.2 完全二叉树的数组表示法


1.什么是树

1.1浅显的理解树

树,其实就是我们现实中的树(注意看有好多分支),但是现在这棵是一个数据结构

在数据结构当中,我们设计结构的目的是为了存储数据,我们所说的树亦是一个能存数据的树。或者更准确的说,是一个一个的数据按照树型结构组织在了一起。那这是一种什么样的数据结构呢?

之前了解到的数据结构,如顺序表,链表等,他们都是线性的存储结构,即一个数据连接着下一个数据,在逻辑上上是呈现线性的。而树这种数据结构则不同,所有数据组织在一起的方式并不是一条单纯的直线了,而是一个树形

1.2 数据结构中树的概念

树是一种非线性的数据结构,它由一个一个的有限数量的节点组织形成,本质上就是节点的集合。在实际coding当中,一棵树是一个倒挂的树,即root树根是在最上层叶子最底层

所以实际上我们数据结构中的树是一棵倒挂的树最上面

当中,有一个特殊的节点,就是根节点,除了空树,每一棵树都有根节点,根节点是唯一的,根节点之上没有其他的节点。

每一棵树,都可以这样划分  根的子树1,子树2,子树3 ........ 子树n(n是看根有多少棵直接子树)。 

 每一棵子树,也都是一棵树。也可以分为子树的根,子树根 的 子树1,子树2......子树n。

 按照这个思路,一棵树由根 + 所有的的每一颗子树组成划分的;根的每一棵子树,也都是按 根 + 所有的每一颗子树构建的;所有的子树的子树,也都是按 根 + 所有的的每一颗子树 方式组织的;所有的子树的子树的子树(此处省去一万字)。。。。。。

所以树本质上都是通过递归定义的。

2.树的各种结构概念

2.1 节点的度

节点的度,就是一个节点的子树的个数,或者说,就是一个节点有几个分叉。

如上面 1节点,它的度就是3(有3个子树/分叉 2 3 4);2节点,它的度是2(有2个子树/分叉 5 6);7节点,它的度是1(只有一个子树/分叉)。

2.2 根节点/叶节点/分支节点

根节点:就是最开始的一个节点(如图的 1节点),它是唯一的。从根开始找,这棵树的所有节点都可以遍历找到。所以只要找到了一棵树的根,这棵树就算是被我们所“掌控”

叶子节点度为0的节点,即往下没有子树/分支的节点。即我这个节点的下面没有任何东西了(空),我这个节点就是叶子节点。(如图中的 5 9 10 8,是上图中树的叶子节点)。

分支节点:这是叶子节点的对立,即度不为0的节点,只要不是叶子节点,那你就是分支节点。

2.3 父节点/子节点

父节点:就是一个节点的父亲。就是一个节点上面的那一个节点,如在下图当中,5的父节点是2,10的父节点是7,3的父亲节点是1.。

这里需要着重强调:就像在现实当中任何一个人都只有一个爹,任何一个节点,也都只有一个父节点。(除根节点,根节点没有父亲

要找到任何一个节点,只能通过父亲节点找到父节点,也只能由他的唯一的父亲节点找到,所以其实在树中,要找到任何一个节点都只有唯一的一条路径。

相对于父节点,那父的儿子就是子节点,即父亲往下可以直接找到的节点。就像现实当中,一个爹,都可以有多个儿子,也可以有一个儿子,也可能没有儿子,在树当中,任何一个节点,只要在我这个节点的下面能直接找到的节点,那这就是子节点。

如1的子节点,就是2 3 4节点;2的子节点,就是5 6节点;4的子节点,就只有 8节点。

2.4祖先节点/子孙节点

祖先节点:从根到该节点所经分支上的所有节点,都是祖先节点。类比现实,你爹是你的祖先,你爷爷是你的祖先,你太爷爷是你的祖先……你的太太太太太太太爷爷都是你的祖先。(当然这里我们也可以知道,根节点一定是所有节点的祖先节点

如6节点的祖先节点是2 1节点;如9节点的祖先节点是6 2 1节点;如8节点的祖先是4 1节点。

子孙节点:祖先是从根节点找到该节点路径上的所有点,而子孙,其实就是我这个节点能被某个节点所找到!!!即只要我这个节点只要能往下找到你,我就是祖先,你就是子孙。如2节点作为祖先节点,那5 6 9这三个节点就都是子孙节点。

 2.5兄弟节点

兄弟节点:(必须是亲兄弟!!!)有同一个的父节点,我们才是兄弟节点!!!

如下图当中5和6才是兄弟节点6和7就不是兄弟节点7和8就不是兄弟节点

2.6树的度

一棵树中,所有节点的最大度,称之为树的度。就是所有的节点的度中,挑出其中最大的节点度。PS:最大的节点度,不一定是根节点的度,我们要求的是有最多分支的节点。

 如这棵树,它的度就是3:即7这个节点的度,是所有节点当中度最大的(3,其余节点的度都是2或1或0),所以这棵树的度就是3。

2.7节点的层次

根开始定义起,根为第1层,根的子节点为第2层。节点的层次也叫树的高度/深度。

当然也有些地方根是第0层,根的子节点为第1层,即上图分为0 1 2 3层,这样也说的过去。

不过我们还是推荐 1 2 3 4 (如上图画的那样),这样方便理解:

空树是没有根节点,如果我们算根节点为第1层这样空树的高度我们就可以换定义为0了,更加符合我们的观感!

2.8森林

有N(N>0)棵树,即至少一棵 互不相交的树 的集合称为森林。

并查集这个数据结构就是森林(就是有多棵树嘛)。

 3. 如何用代码表示一棵树

刚才我们只是从抽象图上表征了树,那落实到代码当中,一棵树如何用代码来表示呢?我们可以用链式结构来表示一棵树,也可以用数组结构来表示一棵树。

3.1链式结构

要用链式结构来实现树,我们就要首先定义出来一个节点类,因为我们一定是把一个一个的节点链起来组成的一棵树(当然节点与节点之间的链接,我们是通过指针来实现的。节点是组成树的基础。那如何定义节点类呢?

3.1.1 树节点的定义方式1(指针数组)

我们节点TreeNode要存一个数据data,这个毋庸置疑,然后就是要存储指针,即链接到子节点的链子。那这样就有一个问题,我每个节点的子节点的数量是不一定的,要使用的链子(指针)数量也是不一定的,所以我们要存储多个节点指针。

一种方法是让每个节点存储一个指针数组,这个指针数组可以是一个定长的

struct TreeNode
{int data;struct TreeNode* *pSonNode[N];
};

但是这种情况是存在缺陷的,如果你知道了这个树的度(即一个节点,最大所能有的分叉数量),或者你规定这个树是固定有多少个叉的,那这个N是可以确定的,可是如果没有给这个度,那N存多大就很难确定了:如果N给大了,那就会造成很多的空间浪费如果N给小了,有可能导致有的节点,所能链接到的节点数量受限。

所以我们通常是存一个可以动态增长的数组指针,按需给相应大小数量的指针

struct TreeNode
{int data;vector<struct TreeNode*> pTreeSon;
};

上面的方法,在指定了这是几叉树 / 该树的度确定,这两种情况下,在节点中直接存储指向孩子的指针,这的确是一种很好的表示树的方法。但是现实中,树的情况是很复杂的,对于度不确定的这种树,我们不推崇上面这个方法,我们有一个也是很好的方法---左孩子右兄弟表示法。

3.1.2 树节点的定义方式2(左孩子右兄弟表示法)

struct TreeNode
{int data;struct TreeNode* Left_FirstChild;struct TreeNode* Right_NextBrother;
};

每一个节点,只存,链接到 最左的孩子(即我的第一个孩子)的指针,以及链接到 右边的兄弟(即我旁边的那个亲兄弟节点)的指针

举个例子:如下图,2节点,我只存储两个指针:我的Left_FirstChild为指向最左边的即第一个孩子5,我的Right_NextBrother为指向我右边的即旁边的亲兄弟3。

再如下图的6节点:我的Left_FirstChild,指向的是第一个孩子9。而我Right_NextBrother,旁边右边的第一个亲兄弟,是空!这里注意哦,兄弟指代的是亲兄弟哦!你只能说6和7是兄弟的关系。反正我7节点的右边是没有亲兄弟的,所以Right_NextBrother存NULL

那这样存为什么能够表示整棵树呢? 画个图你就明白了:比如我们要用这个左孩子右兄弟法表示下面这棵树:

那么如果我们用左孩子右兄弟法,组织节点,组织成这棵树:

你可以看到,这种方法其实是把每一个节点都建立了被链接关系,即我总是能通过某条路径找到这个节点,我们可以根据左孩子右兄弟法这些安插的链子,找到所有节点

只要可以找到/遍历到任何节点,那这就是一种成功的表示树的方法

例如要找H节点,我们可以通过A的左孩子找到B,然后通过B的右兄弟找到C,然后通过C的左孩子找到H节点;

再例如要找到G节点,我们可以通过A的左孩子找到B,然后通过B的左孩子找到E,然后通过E的右兄弟找到F,然后通过F的右兄弟找到G节点。.

这种方法,相比第一种方法,对于任意树的构建,是没有空间浪费的,而且可以全部遍历找到,非常优!!!

3.2数组结构

没错,我们用一个数组,也可以组织表示一棵树哦!(后面写并查集的时候,一个数组甚至能够表示一个森林,也就是多棵树)是不是很神奇!?下面我们具体看一下如何实现。

3.2.1 每个节点存父亲下标

我们每个节点,即每个节点的数据存储在一个数组的一个格子当中,这样每一个数据就都有了一个存储下标index,然后这个数组每个格子不止存数据还存储着该数据节点的父亲的所在下标(根节点没有父亲,存-1)。这种方法也可以表示整棵树,也即可以遍历到/找到任意的一个节点。何出此言?

struct TreeNode
{int data;    //节点存储的数据int parent_i;//我这个节点的父亲的在数组的下标
};

如果我们要找到任意一个节点,可以选择遍历这个数组,从而找到这个节点;然后如何找到这个从根到这个节点的路径呢?其实我们可以通过这个数组每个格子里面存储的父亲的下标一直往父亲跳,一直跳到根即可,记录每个跳到的节点,其实这就是从根到该节点的路

径。

如上面这棵树,我们用数组存储父亲下标法,就是这样组织出这棵树的:

 

3.2.2 完全二叉树的数组表示法

完全二叉树由于其特殊性,在数组中存储表示可以也是非常方便的,而且也会有很多的性质使用,这个我们会放在后面一篇博客,关于数据结构堆的实现上具体讲解(想了解的话就关注我吧~),这种方法来表示完全二叉树也是非常优秀,非常的劲爆!!!

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

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

相关文章

Gitea Windows环境下服务搭建

前言&#xff1a;这篇文章没有去分析各大平台的优劣势&#xff0c;仅教学大家搭建一个属于自己的git代码管理器&#xff0c;主要作用在局域网内&#xff0c;办公电脑搭建一个简单的Gitea代码管理器。数据库使用SQLite3&#xff0c;环境是windows10。如果不是这个环境的话&#…

@Import注解的原理

此注解是springboot自动注入的关键注解&#xff0c;所以拿出来单独分析一下。 启动类的run方法跟进去最终找到refresh方法&#xff1b; 这里直接看这个org.springframework.context.support.AbstractApplicationContext#refresh方法即可&#xff0c;它下面有一个方法 invoke…

Node下载阿里OSS存储文件【不知目录结构】

前言&#xff1a;前端传模型ID&#xff0c;后台根据ID去阿里OSS存储下载对应文件&#xff08;不知文件内部层级结构&#xff0c;且OSS只能单个文件下载&#xff09;&#xff0c;打包成zip字节流形式返回给前端下载。 需求分析&#xff1a; 生成OSS文件关系树Node做文件下载存…

kafka(一) 的架构,各概念

Kafka架构 Kafak 总体架构图中包含多个概念&#xff1a; &#xff08;1&#xff09;ZooKeeper&#xff1a;Zookeeper负责保存broker集群元数据&#xff0c;并对控制器进行选举等操作。 &#xff08;2&#xff09;Producer&#xff1a; 生产者负责创建消息&#xff0c;将消息发…

【神经网络】LSTM为什么能缓解梯度消失

1.LSTM的结构 我们先来看一下LSTM的计算公式&#xff1a; 1.遗忘门&#xff1a; 2.输入门&#xff1a; 3.细胞状态 4.输出门 2.LSTM的梯度路径 根据LSTM的计算公式&#xff0c;可以得出LSTM的cell state与、、都存在计算关系&#xff0c;而、、的计算公式又全部都与有关&#x…

RPC异步化原理

深入RPC&#xff0c;更好使用RPC&#xff0c;须从RPC框架整体性能考虑问题。得知道如何提升RPC框架的性能、稳定性、安全性、吞吐量及如何在分布式下快速定位问题。RPC框架如何压榨单机吞吐量&#xff1f; 1 前言 TPS一直上不去&#xff0c;压测时CPU压到40%&#xff5e;50%就…

bug的创建和等级

1.如何合理的创建一个bug 创建bug的要素 &#xff1a;问题的版本&#xff0c;发现问题的环境&#xff0c;发现问题的步骤&#xff0c;预取结果&#xff0c;实际结果。 eg&#xff1a; 1.问题的版本&#xff1a;谷歌浏览器108版本 2.发现问题的环境&#xff1a;windows11家庭版…

CHAPTER 2 CentOS的日志系统(日志工具)

日志工具2.1 rsyslogd(syslogd)2.1.1 介绍2.1.2 语法2.1.3 配置文件syslog.conf2.1.4 syslog.conf的配置规则2.1.5 示例2.2 logrotate2.2.1 介绍2.2.2 配置文件2.2.3 示例一2.2.4 示例二2.3 dmesg2.3.1 命令简介2.3.2 使用示例2.4 关于重启/死机的日志2.4.1 last2.4.2 日志查看…

HTML#5表单标签

一. 表单标签介绍表单: 在网页中主要负责数据采集功能,使用<form>标签定义表单表单项: 不同类型的input元素, 下拉列表, 文本域<form> 定义表单<input> 定义表单项,通过typr属性控制输入形式<label> 为表单项定义标注<select> 定义下拉列表<o…

工程机械焊接件焊接结构件三维扫描检测外观质量控制-CASAIM三维扫描检测仪

焊接已发展为制造业中的一种重要的加工方法&#xff0c;广泛应用于航空、航天、冶金、石油、汽车制造以及国防等领域。工程机械焊接件品种繁多、几何形状复杂&#xff0c;焊接件质量的好坏将直接影响到产品的使用寿命长短。对焊缝表面尺寸测量及评定表面焊缝缺陷时&#xff0c;…

叠氮试剂79598-53-1,6-Azidohexanoic Acid,6-叠氮基己酸,末端羧酸可与伯胺基反应

●中文名&#xff1a;6-叠氮基己酸●英文名&#xff1a;6-Azidohexanoic Acid&#xff0c;6-Azidohexanoic COOH●外观以及性质&#xff1a;西安凯新生物科技有限公司供应的6-Azidohexanoic Acid浅黄色或者无色油状&#xff0c;叠氮化物可使用铜催化的Click化学与末端炔烃共轭&…

一文了解 requestAnimationFrame

requestAnimationFrame 的基本使用 requestAnimationFrame 是什么 window.requestAnimationFrame() 告诉浏览器——你希望执行一个动画&#xff0c;并且要求浏览器在下次重绘之前调用指定的回调函数更新动画。该方法需要传入一个回调函数作为参数&#xff0c;该回调函数会在浏…

腾讯前端二面常考vue面试题(附答案)

虚拟DOM真的比真实DOM性能好吗 首次渲染大量DOM时&#xff0c;由于多了一层虚拟DOM的计算&#xff0c;会比innerHTML插入慢。正如它能保证性能下限&#xff0c;在真实DOM操作的时候进行针对性的优化时&#xff0c;还是更快的。 MVVM的优缺点? 优点: 分离视图&#xff08;V…

MK60DX256VLQ10(256KB)MK60DN256VLQ10 Kinetis K60 MCU FLASH

MK60DX256VLQ10(256KB)MK60DN256VLQ10 Kinetis K60 MCU 32BIT 256KB FLASH 144LQFP【说明】Kinetis K6x MCU系列是一个可扩展的组合&#xff0c;具有不同级别的集成&#xff0c;提供丰富的模拟、通信、定时和控制外设套件&#xff0c;以适应广泛的需求。应用楼宇自动化控制器人…

数仓基础与hive入门

目录1、数仓数据仓库主流开发语言--SQL2、Apache Hive入门2.1 hive定义2.2 为什么使用Hive2.3 Hive和Hadoop关系2.4 场景设计&#xff1a;如何模拟实现Hive功能2.5 Apache Hive架构、组件3、Apache Hive安装部署3.1 metastore配置方式4、Hive SQL语言&#xff1a;DDL建库、建表…

【谷歌grc】recaptcha browser-error 错误

grc 谷歌人机验证错误 https://www.google.com/recaptcha/api/siteverif 返回错误信息 browser-error [{"success": false,"error-codes": ["browser-error"] }]之前都是调通能用的&#xff0c;突然之间就不能用了&#xff0c;查了半天也没有找…

蓝库云|什么是供应链管理?SCM对制造业的重要性

企业在产品的销售经营上&#xff0c;往往不会考量到供应链管理(SCM)的流程规划&#xff0c;但现今的商业环境与以往不同&#xff0c;高度竞争与客户不断提升的期望&#xff0c;藉由做好供应链管理(SCM)&#xff0c;才能更准时的提供优质产品与优良服务&#xff0c;增强企业竞争…

Qt 小项目 图片浏览系统

目录 引言 实现功能&#xff1a; 效果&#xff1a; 实现图片浏览所用知识: 实现流程&#xff1a; 实现环境和UI设计 具体实现 引言 本系统支持&#xff0c;自动播放&#xff0c;左右拖动切换&#xff0c;点击列表切换&#xff0c;点击按钮切换&#xff1b;是一个标准的…

职场性别报告,男女薪酬仍有差距,男性平均薪酬比女性高29.7%

性别是否影响职业&#xff1f;女性求职比男性更加困难&#xff1f;男性薪酬比女性更有优势&#xff1f;人们一说到警察、建筑师通常会想到高大魁梧的男性形象&#xff0c;一说到幼师、护士往往想到的都是温柔的女性形象&#xff0c;职业好似与性别挂钩&#xff1b;女性求职通常…

vue脚手架多页自动化生成实践

前言 在前端开发过程中&#xff0c;常常面对多种业务场景。到目前为止&#xff0c;前端对于不同场景的处理通常会采用不同的渲染方案来组合处理&#xff0c;常见的渲染方案包括&#xff1a;CSR(Client Side Rendering)、SSR(Server Side Rendering)、SSG(Static Site Generati…