【数据结构】树的介绍
文章目录
- 前言
- 树的概念及结构
- 树的概念
- 树的表示
- 树在实际中的运用
- 二叉树的概念及结构
- 二叉树的概念
- 现实中的二叉树
- 特殊的二叉树
- 二叉树的性质
- 二叉树的储存结构
- 顺序存储
- 链式存储
- 写在最后
前言
🚩本章给大家介绍一下树。树的难度相对于前面的数据结构来说,又高了一个台阶,所以我们要先从最基础的开始,也就是本章的一些知识点。
🚩树又分为很多种树,如 二叉树,红黑树,AVL树,B树 等等,这些的难度都相对较大,所以大家对本章树的一些概念以及一些基本性质的理解必不可少。
🚩本章除了对树的介绍,还有基础的二叉树的相关介绍,目的是为了大家能够更好的理解树。
树的概念及结构
树的概念
-
树是一种非线性的数据结构,它是由
n(n >= 0)
个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。- 有一个特殊的结点,称为根结点,根节点没有前驱结点。
- 除根节点外,其余结点被分成
M(M > 0)
个互不相交的集合T1、T2、……、Tm
,其中每一个集合Ti(1 <= i <= m) 又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱,可以有0
个或多个后继。因此,树是递归定义的。
注意:树形结构中,子树之间不能有交集,否则就不是树形结构
例如:
- 根据树的结构,有以下概念:
1. 节点的度: 一个节点含有的子树的个数称为该节点的度; 如上图:
A
的为6
。
2. 叶节点或终端节点: 度为0
的节点称为叶节点; 如上图:B、C、H、I...
等节点为叶节点。
3. 非终端节点或分支节点: 度不为0
的节点; 如上图:D、E、F、G...
等节点为分支节点。
4. 双亲节点或父节点: 若一个节点含有子节点,则这个节点称为其子节点的父节点; 如上图:A
是B
的父节点。
5. 孩子节点或子节点: 一个节点含有的子树的根节点称为该节点的子节点; 如上图:B
是A
的孩子节点。
6. 兄弟节点: 具有相同父节点的节点互称为兄弟节点; 如上图:B、C
是兄弟节点。
7. 树的度: 一棵树中,最大的节点的度称为树的度; 如上图:树的度为6
。
8. 节点的层次: 从根开始定义起,根为第1
层,根的子节点为第2
层,以此类推。
9. 树的高度或深度: 树中节点的最大层次; 如上图:树的高度为4
。
10. 堂兄弟节点: 双亲在同一层的节点互为堂兄弟;如上图:H、I
互为兄弟节点。
11. 节点的祖先: 从根到该节点所经分支上的所有节点;如上图:A
是所有节点的祖先。
12. 子孙: 以某节点为根的子树中任一节点都称为该节点的子孙。如上图:所有节点都是A
的子孙。
13. 森林: 由m(m>0)
棵互不相交的树的集合称为森林。
树的表示
树的结构相对线性表就比较复杂了,要存储表示起来也就比较麻烦了,既要保存值域,也要保存结点和结点之间的关系。实际中树有很多种表示方式如: 双亲表示法,孩子表示法、孩子双亲表示法以及孩子兄弟表示法 等。我们这里就简单的了解其中最常用的 孩子兄弟表示法 。
所谓孩子兄弟表示法,指的是将整棵树用二叉链表存储起来,具体实现方案是:树的左指针指向自己的第一个孩子,右指针指向与自己相邻的兄弟。
该结构的最大优点是:它和二叉树的二叉链表表示完全一样。可利用二叉树的算法来实现对树的操作 。
图示:
其定义的结构如下:
typedef int DataType;
struct Node
{struct Node* _firstChild1; // 第一个孩子结点struct Node* _pNextBrother; // 指向其下一个兄弟结点DataType _data; // 结点中的数据域
};
树在实际中的运用
- 树在实际中运用的最好的一个例子,就是系统的文件目录结构。
Linux树状目录结构:
- 实际上
windows
的目录结构也是一棵树,我们点击一个文件就会出现若干子文件等等,点击子文件又会出现若干个子文件的子文件等等,这也是一个明显的数的储存结构。
二叉树的概念及结构
二叉树的概念
- 一棵二叉树是结点的一个有限集合,该集合:要么为空,要么由一个根节点加上两棵别称为左子树和右子树的二叉树组成。
从上图可以看出:
- 二叉树不存在度大于
2
的结点; - 二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树。
注意:对于任意的二叉树都是由以下几种情况复合而成的:
现实中的二叉树
- 要是能在现实种中看到这种树,那不得好好拜一拜 😃
特殊的二叉树
- 满二叉树:一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为
K
,且结点总数是2 ^ K - 1
,则它就是满二叉树。 - 完全二叉树:完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为
K
的,有n
个结点的二叉树,当且仅当其每一个结点都与深度为K
的满二叉树中编号从1
至n
的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
二叉树的性质
- 若规定根节点的层数为
1
,则一棵非空二叉树的第i层上最多有2 ^ (i - 1)
个结点。 - 若规定根节点的层数为
1
,则深度为h
的二叉树的最大结点数是2 ^ h - 1
。 - 对任何一棵二叉树, 如果度为
0
的叶结点个数为a
, 度为2
的分支结点个数为b
,则有a = b + 1
。 - 若规定根节点的层数为
1
,具有n
个结点的满二叉树的深度h= log(n + 1)
。 - 对于具有
n
个结点的完全二叉树,如果按照从上至下从左至右的数组顺序对所有节点从0
开始编号,则对
于序号为i
的结点有:- 若
i > 0
,i
位置节点的双亲序号:(i - 1) / 2
;i = 0
,i
为根节点编号,无双亲节点; - 若
2i + 1 < n
,左孩子序号:2i + 1
,2i + 1 >= n
否则无左孩子; - 若
2i + 2 < n
,右孩子序号:2i + 2
,2i + 2 >= n
否则无右孩子。
- 若
二叉树的储存结构
二叉树一般可以使用两种结构存储,一种顺序结构,一种链式结构。
顺序存储
- 顺序结构存储就是使用数组来存储,一般使用数组只适合表示完全二叉树,因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储,关于堆我们后面的章节会专门讲解。二叉树顺序存储在物理上是一个数组,在逻辑上是一颗二叉树。
链式存储
- 二叉树的链式存储结构是指,用链表来表示一棵二叉树,即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成,数据域和左右指针域,左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链,当前我们学习中一般都是二叉链,后面的高阶数据结构如红黑树等会用到三叉链。
typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{struct BinTreeNode* _pLeft; // 指向当前节点左孩子struct BinTreeNode* _pRight; // 指向当前节点右孩子BTDataType _data; // 当前节点值域
}// 三叉链
struct BinaryTreeNode
{struct BinTreeNode* _pParent; // 指向当前节点的双亲struct BinTreeNode* _pLeft; // 指向当前节点左孩子struct BinTreeNode* _pRight; // 指向当前节点右孩子BTDataType _data; // 当前节点值域
};
写在最后
💝关于树的介绍就这么多,想深入了解大家可以查阅一些文献。后续我将会以此篇章为基础点,依次给大家带来堆与二叉树的实现。
❤️🔥后续将会持续输出有关数据结构与算法的文章,你们的支持就是我写作的最大动力!
感谢阅读本小白的博客,错误的地方请严厉指出噢~
相关文章:

【数据结构】树的介绍
文章目录前言树的概念及结构树的概念树的表示树在实际中的运用二叉树的概念及结构二叉树的概念现实中的二叉树特殊的二叉树二叉树的性质二叉树的储存结构顺序存储链式存储写在最后前言 🚩本章给大家介绍一下树。树的难度相对于前面的数据结构来说,又高了…...

CoreDNS 性能优化
CoreDNS 作为 Kubernetes 集群的域名解析组件,如果性能不够可能会影响业务,本文介绍几种 CoreDNS 的性能优化手段。合理控制 CoreDNS 副本数考虑以下几种方式:根据集群规模预估 coredns 需要的副本数,直接调整 coredns deployment 的副本数:k…...
前端三剑客常见面试题及其答案
目录 1、什么是 HTML? 2、什么是 CSS? 3、什么是 JavaScript? 4、什么是盒模型? 5、什么是浮动? 6、什么是定位? 7、什么是选择器? 8、什么是事件? 前端的三剑客指的是 HTML…...

【DFS专题】深度优先搜索 “暴搜”优质题单推荐 10道题(C++ | 洛谷 | acwing)
文章目录题单一、模板 [极为重要]全排列DFS组合型DFS指数DFS二、专题烤鸡 (指数BFS)P1088 火星人 【全排列】P1149 火彩棒 [预处理 ]P2036 PERKETP1135 奇怪的电梯 暴力P1036 [NOIP2002 普及组] 选数 (组合)P1596 [USACO10OCT]Lake Counting …...
微信小程序自定义组件生命周期有哪些?
微信小程序自定义组件的生命周期函数分为三类: 创建时执行的生命周期函数、更新时执行的生命周期函数和销毁时执行的生命周期函数。 下面是具体的生命周期函数及其触发时机: 创建时执行的生命周期函数: created:在组件实例刚刚…...

Linux就该这么学(六)
一、从“/”开始 Linux 系统中的文件和目录名称是严格区分大小写的。例如,root、rOOt、rooT 均代表不同的目录,并且文件名称中不得包含斜杠(/)。Linux 系统中的文件存储结构如下图所示。 在 Linux 系统中,最常见的目录…...

目标检测算法——YOLOv5/v7/v8改进结合涨点Trick之Wise-IoU(超越CIOU/SIOU)
超越CIOU/SIOU | Wise-IoU助力YOLO强势涨点!!! 论文题目:Wise-IoU: Bounding Box Regression Loss with Dynamic Focusing Mechanism 论文链接:https://arxiv.org/abs/2301.10051 近年来的研究大多假设训练数据中的…...

【蓝桥杯选拔赛真题39】python输出数字组合 青少年组蓝桥杯python 选拔赛STEMA比赛真题解析
目录 python输出数字组合 一、题目要求 1、编程实现 2、输入输出...

网络安全工程师做什么?
网络安全很复杂。数字化转型、远程工作和不断变化的威胁形势需要不同的工具和不同的技能组合。 系统必须到位以保护端点、身份和无边界网络边界。负责处理这种复杂安全基础设施的工作角色是网络安全工程师。 简而言之,网络安全工程师是负责设计和实施组织安全系…...

总结:K8S运维常用命令
一、部署./kubectl apply -f biz-healing-pod.yaml 二、查看部署的资源1、podkubectl get pod -A:获取所有pod没有IP?用-o wide参数看详细信息:./kubectl get pod -n deepflow -o wide2、service查看hubble-manager命名空间下有哪些service/d…...

你是真的“C”——进行动态内存分配库函数的使用详解
你是真的“C”——申请动态空间库函数的使用详解😎前言🙌一、为什么需要动态内存分配?💞free 函数😘malloc 库函数😘calloc 库函数😘realloc 库函数😘总结撒花💞…...

Python|蓝桥杯进阶第五卷——数论
欢迎交流学习~~ 专栏: 蓝桥杯Python组刷题日寄 蓝桥杯进阶系列: 🏆 Python | 蓝桥杯进阶第一卷——字符串 🔎 Python | 蓝桥杯进阶第二卷——贪心 💝 Python | 蓝桥杯进阶第三卷——动态规划 ✈️ Python | 蓝桥杯进阶…...
用Python实现单例模式
什么是单例模式单例模式是指在内存中只会创建且仅创建一次对象的设计模式。在程序中多次使用同一个对象且作用相同时,为了防止频繁地创建对象使得内存飙升,单例模式可以让程序仅在内存中创建一个对象,让所有需要调用的地方都共享这一单例对象…...

交叉编译说明:工具链安装和环境变量配置
目录 一 简单了解交叉编译 ① 什么是交叉编译 ② 为什么需要交叉编译 ③ 宿主机和目标机 二 搭建交叉编译工作环境 ① 安装工具链 ② 配置环境变量 ● 配置临时环境变量 ● 配置永久环境变量 三 交叉编译宿主机和目标机 ● 宿主机编译生成的可执行文件下载到目…...

文件上传的多种利用方式
文件上传的多种利用方式 文件上传漏洞除了可以通过绕过检测进行webshell的上传之外,还有多种其它的漏洞可以进行测试。 XSS漏洞 文件名造成的XSS 当上传任何文件时,文件名肯定是会反显示在网页上,可以使用 XSS Payload做文件名尝试将其上传到…...
盘一盘C++的类型描述符(二)
先序文章请看 盘一盘C的类型描述符(一) 稍微组合一下的复杂类型 数组指针类型的数组类型 数组的指针类型我们已经了解了,那么,以这种类型作为元素的数组类型怎么搞? using type int (*)[3]; // 元素类型是数组指针…...

慎投,Frontiers这本期刊显示on hold中
什么是“On Hold”? 该期刊因为质量问题正在被进行重新评估;在重新评估过程中,不会检索新发表的文章。该期刊因为质量问题正在被进行重新评估;在重新评估过程中,不会检索新发表的文章。根据选择标准,在最严…...
Winform控件开发(21)——ProgressBar(史上最全)
一、属性 1、Name 用于获取控件对象 2、Anchor 锚定控件对于父控件的位置 3、BackColor 背景色 4、ContextMenuStrip 关联的上下文菜单 5、Cursor 鼠标移动到控件上显示的光标 6、Dock 停靠在父控件的位置 7、Enabled 是否启动该控件,false时事件都不能触发 8、…...

校招失败后,在外包公司熬了 2 年终于进了字节跳动,竭尽全力....
其实两年前校招的时候就往字节投了一次简历,结果很明显凉了,随后这个理想就被暂时放下了,但是这个种子一直埋在心里这两年除了工作以外,也会坚持写博客,也因此结识了很多优秀的小伙伴,从他们身上学到了特别…...

UniApp + SpringBoot 实现接入支付宝支付功能和退款功能
一、支付宝开放平台设置 注册支付宝支付功能需要个体工商户或企业才可以!需要有营业执照才能去申请哦! 1、登录到控制台 进入支付宝开放平台 控制台 2、开发设置 3、产品绑定APP支付 如果没有绑定APP支付就会报商家订单参数异常,请重新发起…...
逻辑回归:给不确定性划界的分类大师
想象你是一名医生。面对患者的检查报告(肿瘤大小、血液指标),你需要做出一个**决定性判断**:恶性还是良性?这种“非黑即白”的抉择,正是**逻辑回归(Logistic Regression)** 的战场&a…...
Frozen-Flask :将 Flask 应用“冻结”为静态文件
Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是:将一个 Flask Web 应用生成成纯静态 HTML 文件,从而可以部署到静态网站托管服务上,如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码
目录 一、👨🎓网站题目 二、✍️网站描述 三、📚网站介绍 四、🌐网站效果 五、🪓 代码实现 🧱HTML 六、🥇 如何让学习不再盲目 七、🎁更多干货 一、👨…...
【Go语言基础【13】】函数、闭包、方法
文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数(函数作为参数、返回值) 三、匿名函数与闭包1. 匿名函数(Lambda函…...

RSS 2025|从说明书学习复杂机器人操作任务:NUS邵林团队提出全新机器人装配技能学习框架Manual2Skill
视觉语言模型(Vision-Language Models, VLMs),为真实环境中的机器人操作任务提供了极具潜力的解决方案。 尽管 VLMs 取得了显著进展,机器人仍难以胜任复杂的长时程任务(如家具装配),主要受限于人…...
Python 训练营打卡 Day 47
注意力热力图可视化 在day 46代码的基础上,对比不同卷积层热力图可视化的结果 import torch import torch.nn as nn import torch.optim as optim from torchvision import datasets, transforms from torch.utils.data import DataLoader import matplotlib.pypl…...

数据结构:泰勒展开式:霍纳法则(Horner‘s Rule)
目录 🔍 若用递归计算每一项,会发生什么? Horners Rule(霍纳法则) 第一步:我们从最原始的泰勒公式出发 第二步:从形式上重新观察展开式 🌟 第三步:引出霍纳法则&…...

理想汽车5月交付40856辆,同比增长16.7%
6月1日,理想汽车官方宣布,5月交付新车40856辆,同比增长16.7%。截至2025年5月31日,理想汽车历史累计交付量为1301531辆。 官方表示,理想L系列智能焕新版在5月正式发布,全系产品力有显著的提升,每…...

运动控制--BLDC电机
一、电机的分类 按照供电电源 1.直流电机 1.1 有刷直流电机(BDC) 通过电刷与换向器实现电流方向切换,典型应用于电动工具、玩具等 1.2 无刷直流电机(BLDC) 电子换向替代机械电刷,具有高可靠性,常用于无人机、高端家电…...
结合PDE反应扩散方程与物理信息神经网络(PINN)进行稀疏数据预测的技术方案
以下是一个结合PDE反应扩散方程与物理信息神经网络(PINN)进行稀疏数据预测的技术方案,包含完整数学推导、PyTorch/TensorFlow双框架实现代码及对比实验分析。 基于PINN的反应扩散方程稀疏数据预测与大规模数据泛化能力研究 1. 问题定义与数学模型 1.1 反应扩散方程 考虑标…...