【数据结构】树的定义、树的存储结构

简介: 【数据结构】树的定义、树的存储结构

前言


提到存储结构,可以很自然的想到顺序存储结构和链式存储结构两种。


之前介绍的所有的数据结构都是线性存储结构。本章所介绍的树结构是一种非线性存储结构,存储的是具有“一对多”关系的数据元素的集合。


cb46133043df4ca6b5588c4dec725e71.png


图 1(A) 是使用树结构存储的集合 {A,B,C,D,E,F,G,H,I,J,K,L,M} 的示意图。对于数据 A 来说,和数据 B、C、D 有关系;对于数据 B 来说,和 E、F 有关系。这就是“一对多”的关系。

将具有“一对多”关系的集合中的数据元素按照图 1(A)的形式进行存储,整个存储形状在逻辑结构上看,类似于实际生活中倒着的树(图 1(B)倒过来),所以称这种存储结构为“树型”存储结构。

💚❤️💙💚❤️💙💚❤️💙💚❤️💙💚❤️💙💚❤️💙💚❤️💙💚❤️💙💚❤️💙💚❤️💙


🐋树的定义


🌲树的定义


       树(Tree)是 n(n>=0)个结点的有限集。n=0时称为空树。在任意一颗非空树中:


有且仅有一个特定的称为根(root)的结点;

当n>1时,其余结点可分为m(m>0)个互补交互的有限集T1、T2...Tm,其中每一个集合本身又是一棵树,并称为根的子树(SubTree)。


df38fd9b66bb44cbbc3b801a683fe0b7.png


🌲树的特点


n>0时,根节点是唯一的,不可能存在多个根节点。数据结构中的树只有一个根节点。

m>0时,子树的个数没有限制,但他们一定是互不相交的。


🌲结点的分类


结点:树的结点包含一个数据元素和若干指向其子树的分支。

结点的度(Degree):结点拥有的子树。

叶子结点(Leaf)/终端结点:度为0的结点。

分支结点/非终端结点:度不为0的结点。

内部结点:除根节点以外,分支结点也称为内部结点。

树的度:树内各结点的度的最大值。


febfdc26e5fe4082a3f24394ae2a8797.png


🌲结点之间的关系


孩子(Child)和双亲(Parent):结点的子树的根,相应的,该结点称为孩子的双亲。(注意是双亲,不是单亲)


兄弟(sibling):同一个双亲的孩子之间互称兄弟。


结点的祖先:从根结点到该结点所经过分支上的所有结点。


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


无序树和有序树:如果将树中结点的各子树看成从左至右是有次序的,不能互换的,则称该数为有序树,否则为无序树。


森林(fores):m(m>=0)棵互不相较的树的集合。


💚❤️💙💚❤️💙💚❤️💙💚❤️💙💚❤️💙💚❤️💙💚❤️💙💚❤️💙💚❤️💙💚❤️💙


🐋树的存储结构


树的4种链式存放方式:

双亲链表存储结构

孩子链表存储结构

双亲孩子链表存储结构

孩子兄弟链表存储结构

b11533763d234947aca101037dec8b41.png


⚡双亲链表存储结构


以一组地址连续的存储单元存放树中的各个结点,每个结点有两个域:


数据域:用于存放树中该结点的值。


指针域:用于存放该结点的双亲结点在存储结构中的位置。


data(数据域) parent(指针域)

存储结点的数据信息 存储该结点的双亲所在数组中的下标

662ace49b4234d0d87fa981e5ed364b6.png


优点:查找一个指定结点的双亲结点非常容易。


缺点:查找指定结点的孩子结点,需要扫描整个链表。


⚡孩子链表存储结构


以一组地址连续的存储单元来存放树中的各个结点,每一个结点有两个域。


数据域:存放该结点的值


指针域:用于存放该结点的孩子链表的头指针。


孩子链表的孩子结点:


child(数据域) next(指针域)


存储某个结点在表头数组中的下标 存储指向某结点的下一个孩子结点的指针


表头数组的表头结点:


data(数据域) firstchild(头指针域)

存储某个结点的数据信息 存储该结点的孩子链表的头指针

bcff713717a24534b4c0b5b674f8acd8.png


优点:便于实现查找树中指定结点的孩子结点。


缺点:不便于查找指定结点的双亲结点。


⚡双亲孩子链表存储结构


与孩子链表存储结构类似,以一组地址连续的存储单元来存放树中的各个结点,每一个结点有三个域


数据域:存放该结点的值


父指针域:用于存放双亲结点在数组中的位置


子指针域:用于存放该结点的孩子链表的头指针。


e3a1af0b7435472d95278ee052d640d4.png


⚡孩子兄弟链表存储结构


孩子兄弟链表存放,又称为“左子/右兄”二叉链式存储结构。


左指针:指向该结点的第一个孩子


右指针:指向该结点的右邻兄弟


data(数据域) firstchild(指针域) rightsib(指针域)

存储结点的数据信息 存储该结点的第一个孩子的存储地址 存储该结点的右兄弟结点的存储地址

9b57fb1db8824839b545e1b9ba7744bd.png

目录
打赏
0
0
0
0
12
分享
相关文章
|
4月前
|
算法系列之数据结构-Huffman树
Huffman树(哈夫曼树)又称最优二叉树,是一种带权路径长度最短的二叉树,常用于信息传输、数据压缩等方面。它的构造基于字符出现的频率,通过将频率较低的字符组合在一起,最终形成一棵树。在Huffman树中,每个叶节点代表一个字符,而每个字符的编码则是从根节点到叶节点的路径所对应的二进制序列。
119 3
 算法系列之数据结构-Huffman树
【数据结构进阶】AVL树深度剖析 + 实现(附源码)
在深入探讨了AVL树的原理和实现后,我们不难发现,这种数据结构不仅优雅地解决了传统二叉搜索树可能面临的性能退化问题,还通过其独特的平衡机制,确保了在任何情况下都能提供稳定且高效的查找、插入和删除操作。
283 19
|
6月前
|
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
【数据结构——树】哈夫曼树(头歌实践教学平台习题)【合集】目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果:任务描述 本关任务:编写一个程序构建哈夫曼树和生成哈夫曼编码。 相关知识 为了完成本关任务,你需要掌握: 1.如何构建哈夫曼树, 2.如何生成哈夫曼编码。 测试说明 平台会对你编写的代码进行测试: 测试输入: 1192677541518462450242195190181174157138124123 (用户分别输入所列单词的频度) 预
158 14
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
|
6月前
|
【C++数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数(简单示例,手动构建) TreeNode*create
154 12
|
6月前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
140 10
|
6月前
|
【C++数据结构——图】图的邻接矩阵和邻接表的存储(头歌实践教学平台习题)【合集】
本任务要求编写程序实现图的邻接矩阵和邻接表的存储。需掌握带权有向图、图的邻接矩阵及邻接表的概念。邻接矩阵用于表示顶点间的连接关系,邻接表则通过链表结构存储图信息。测试输入为图的顶点数、边数及邻接矩阵,预期输出为Prim算法求解结果。通关代码提供了完整的C++实现,包括输入、构建和打印邻接矩阵与邻接表的功能。
227 10
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
205 2
|
8月前
|
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
183 58
栈区的非法访问导致的死循环(x64)
这段内容主要分析了一段C语言代码在VS2022中形成死循环的原因,涉及栈区内存布局和数组越界问题。代码中`arr[15]`越界访问,修改了变量`i`的值,导致`for`循环条件始终为真,形成死循环。原因是VS2022栈区从低地址到高地址分配内存,`arr`数组与`i`相邻,`arr[15]`恰好覆盖`i`的地址。而在VS2019中,栈区先分配高地址再分配低地址,因此相同代码表现不同。这说明编译器对栈区内存分配顺序的实现差异会导致程序行为不一致,需避免数组越界以确保代码健壮性。
21 0
栈区的非法访问导致的死循环(x64)
232.用栈实现队列,225. 用队列实现栈
在232题中,通过两个栈(`stIn`和`stOut`)模拟队列的先入先出(FIFO)行为。`push`操作将元素压入`stIn`,`pop`和`peek`操作则通过将`stIn`的元素转移到`stOut`来实现队列的顺序访问。 225题则是利用单个队列(`que`)模拟栈的后入先出(LIFO)特性。通过多次调整队列头部元素的位置,确保弹出顺序符合栈的要求。`top`操作直接返回队列尾部元素,`empty`判断队列是否为空。 两题均仅使用基础数据结构操作,展示了栈与队列之间的转换逻辑。
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问