当前课程知识点:数据结构 > 第6章 树和二叉树 > 6.6 树的存储 > 6.6树的存储
同学们大家好
我是云南大学信息学院教师孔兵
这节课我们讨论树的存储
数据结构的存储涉及数据元素的存储和关系的表示
树结构的存储我们会介绍三种办法
请同学注意不同方法中如何存储元素,如何描述关系
第一种称为双亲表示法
在前面的课程中,我们讨论过
树中除根结点外,每个结点有一个唯一前驱或者说双亲
它们和每个结点之间是前驱和后继的关系
是一个有序对,图中用一个分支表示两者的关系
双亲表示法就是利用唯一双亲这个特征
实现树的存储
我们结合一个例子来进行说明
图2是一棵树的逻辑结构
图1是这棵树双亲表示法的存储结构
观察图1,双亲表示法是顺序存储结构
利用一个一维数组来实现树的存储。
数组中每个单元是一个结构体,结构体中包含两个成员
一个成员data,用来存储数据元素本身
另外一个成员pArent,是一个指示器
本身是一个整型数
指示器的作用就是指明元素双亲在数组中的存储位置
树结构中总共有10个元素
我们分配数组nodes的0~9号单元存储这10个元素
元素存在成员data中
完成数据元素的存储
随后是描述关系
通过在双亲指示器中存储元素双亲在数组nodes中的位置来描述关系
0号单元的元素R是整棵树的根
对应的双亲指示器中存储-1
表示它没有双亲。1号单元是A
双亲指示器中0,表明A的双亲是存在0号单元的元素R
描述了R和A是前驱和后继的关系
用指前驱的方法描述了R到A这个分支
其它的分支也用同样方法处理
这样就把树中数据元素之间的关系描述出来了
实现了树的存储结构
我们简单看一下,双亲表示法的存储结构定义
首先定义了一个常量
表示一维数组的大小是100
随后,定义数组当中每个数据元素的类型
是一个结构体,包含两个成员
DAte存储数据元素,PArent描述双亲在数组中的位置
结构体取类型名PTNode
第二个结构体是树的存储结构定义
有3个成员,nodes是一维数组
数组元素类型是PTNode
大小是100,就是上一张幻灯片中的数组
另外两个整型成员,r给出树根在数组中的位置
n是树中元素的个数
第二种树的存储结构称为孩子表示法
双亲表示法是用指前驱的方式描述关系
那么孩子表示法就是用指后继的方式来描述关系
孩子表示法有两种考虑
一种是在二叉链表的基础上做扩充
二叉链表结点中有两个指针指向左右孩子
树中结点有多个孩子
可以按照树的度设置每个结点的指针数
如child1到childd
如果树中结点之间的度差别比较大的话
空间的浪费可能比较大
第二种考虑是,根据每个元素可能有多个孩子的情况
用一个结点描述一个孩子
多个描述孩子的结点组成一个单链表
下面结合例子做一个说明
图2是要存储的树,图1是孩子表示法存储的图示
首先仍然是把树中元素存储在一维数组nodes中
每个数组单元是一个结构体
有两个成员,data存数据元素
firstchild是一个指针,指向单链表中描述第一个孩子的结点
树中10个数据元素存在数组0~9号单元的data中
观察一下图中的0号单元,data存有元素A
从逻辑结构上看,结点A有两个孩子D和E
0号单元的firstchild指针指向包括两个结点的单链表
单链表中每个结点包含两个成员
整型数child表示孩子的位置,next指针链接单链表
第1个结点child中是3
说明A有一个孩子存在数组nodes的3号单元
就是数据元素D,第2个结点中是5
A另一个孩子存在数组nodes的5号单元
是E。同学们可以看到,树中元素有几个孩子
其对应的单链表中就有几个结点
指明孩子是存在数组的那个位置
如果没有孩子,比如叶子
它对应的firstchild指针为空
图中还有整型遍历r
用它记录树根在数组中的位置
示例中r=4,表示树根存在4号单元,树根是R
下面我们看一下这种方法存储结构的定义
孩子表示法存储结构的定义稍微复杂一些
分为三个部分,首先是对孩子单链表中结点的定义
定义为一个结构体,有两个成员
整型child用来指明孩子在数组中的存储单元
指针next用来形成孩子结点的链表
指针next用来形成孩子结点的链表
给这个结构体起了类型名ctnode
定义了一个指向结构体的指针类型的名字ChildPrt
第二部分是对一维数组当中每个数组单元类型的定义
也是一个结构体,包含两个成员
data用来存储数据元素本身
firstchild是ChildPrt类型的指针
指向单链表中描述第一个孩子的结点
结构体类型定义为CTBox
第三部分是对一维数组的定义
也是一个结构体,包含三个成员
一维数组nodes,数组元素类型是第二部分定义的CTBox
大小是MAX_TREE_SIZE
另外两个成员是整型数
n给出树中结点的个树
r指明树中根结点在数组当中的位置
图这一章中,这种存储方式会用来存储图结构
我们后面再来讨论
第三种树结构的存储方法
也是最重要的一种方法是孩子兄弟表示法
就形态上来说,孩子兄弟表示法是也是一种二叉链表的表示方法
这点和前面二叉树的二叉链表,形态上是差不多
孩子兄弟表示法中每个结点也是被定义为一个结构体
有三个成员,data存储树中元素
另外两个成员是两个指向自身的指针
firstchild,顾名思义
它指向当前结点的第1个孩子
nextsibling,是指向当前结点的下一个兄弟
兄弟的概念前面介绍过,同一双亲的孩子,称为兄弟
看一个具体的例子
图2是一棵树
孩子兄弟表示法中
我们仍然是为树中每个元素分配一个链表结点存储它
这棵树要分配10结点
每个链表结点的三个成员
左边是firstchild指向当前结点的第1个孩子
右边是nextsibling指向当前结点的下一个兄弟
从根R这个结点开始,对于R来说
它没有兄弟,兄弟指针为空
R的第1个孩子是A,那么孩子指针就指向结点A
A结点,第1个孩子是D
A结点的孩子指针就指向结点D,D是一个叶子
没有孩子,孩子指针为空,但是D有一个兄弟E
它们都是A的孩子,D结点的兄弟指针就指向结点E
E没有孩子,也没有下一个兄弟了,两个指针都为空
回过来看A结点,下一个兄弟是B,A的兄弟指针指向B
B没有孩子,有下一个兄弟C
B的兄弟指针指向C
其它的结点也是用这样的方式来描述元素之间的关系
按照孩子兄弟表示法
任何形态的树都可以这样来实现其存储
用一种统一的方法实现了树的存储
也就是说,用孩子兄弟表示法解决了树结构存储比较复杂性的问题
在孩子兄弟表示法中
树中有的元素之间前驱和后继的关系
没有被直接用指针描述,但隐含描述了
例如R和C的关系,C是R的第3个孩子
可以从R找到第1个孩子A,.然后从A的兄弟指针找到B
在从B的兄弟指针找到C
后续,对这个情况
我们在相应的算法中有适当的处理
同学们,这节课就讲到这
下次再见
-1.算法概念导入
-2.数据结构课程介绍
-0.1变量、类型和表达式
-0.2 函数
--0.2 函数
-0.3 指针和单链表
-0.4 数组、指向函数的指针
-1.1什么是数据结构
--测试题
-1.2基本概念和术语
--测试题
-1.3数据结构的描述
--测试题
-1.4抽象数据类型的定义和实现
--测试题
-1.5算法和算法分析概念
--测试题
-1.6算法分析示例
--测试题
-2.1 线性表的类型定义
--测试题
-2.2线性表的顺序表示和实现
--测试题
-2.3 线性链表
--2.3 线性链表
--测试题
-2.4 静态链表
--2.4 静态链表
--测试题
-2.5 循环链表和双向链表
--测试题
-3.1 栈
--3.1栈
--测试题
-3.2 栈的实现
--3.2 栈的实现
--测试题
-3.3 栈的应用
--3.3 栈的应用
-3.4 栈与递归的实现
--测试题
-3.5 队列和链队列
--测试题
-3.6 循环队列
--3.6 循环队列
--测试题
-4.1 串
--4.1 串
--测试题
-5.1 数组定义和表示
--测试题
-5.2矩阵的压缩存储
--测试题
-6.1 树的定义和基本术语
-6.2 二叉树和二叉树的性质
--测试题
-6.3 二叉树的存储结构
--测试题
-6.4 遍历二叉树
--测试题
-6.5 线索二叉树
--测试题
-6.6 树的存储
--6.6树的存储
-6.7 树的转换和遍历
--测试题
-6.8 赫夫曼树
--6.8 赫夫曼树
-6.9 赫夫曼编码
--测试题
-7.1 图的定义和术语
--测试题
-7.2 图的存储结构
--测试题
-7.3 图的遍历
--测试题
-7.4 最小生成树
--测试题
-7.5 有向无环图
--测试题
-7.6 最短路径
--测试题
-8.1 查找基本概念和顺序查找
--测试题
-8.2 有序表的查找
--测试题
-8.3 二叉排序树
--测试题
-8.4 平衡二叉树
--测试题
-8.5 哈希表
--测试题
-9.1插入排序
--测试题
-9.2 希尔排序
--9.2 希尔排序
--测试题
-9.3 快速排序
--9.3 快速排序
--测试题
-9.4 选择排序
--9.4 选择排序
--测试题
-9.5 堆排序
--9.5 堆排序
--测试题
-9.6 归并排序
--9.6 归并排序
--测试题
-9.7 基数排序
--9.7 基数排序
--测试题
-9.8 排序方法总结