【数据结构】树的存储结构

admin管理员组

文章数量:1446757

【数据结构】树的存储结构

树的存储结构

导读

大家好，很高兴又和大家见面啦！！！

在前面的内容中，我们已经学习了树的基本概念以及二叉树的相关知识点。

从今天的内容开始，我们将会进入树的下一个部分——树与森林。

在今天的内容中，我们会详细探讨树的存储结构。

树的存储方式有很多，既可以采用顺序存储结构，又可采用链式存储结构。

但是无论采用哪种存储方式，都要求能唯一地反映树中各结点之间的逻辑关系。通过今天的内容，我们会学会树的三种常用的存储结构：

• 双亲表示法
• 孩子表示法
• 孩子兄弟表示法

下面我们就开始今天的内容吧！！！

一、二叉树的顺序存储

在二叉树的顺序存储中，当我们按照从上到下、从左到右的顺序去存储一棵二叉树时，我们会发现孩子与双亲的数组下标是有一定的联系的：

• 当根结点从0下标处进行存储，则下标为 i 的结点，其左孩子下标为 2×i+1 ，右孩子下标为 2×i+2 ；
• 当根结点从1下标处进行存储，则下标为 i 的结点，其左孩子下标为 2×i ，右孩子下标为 2×i+1 ；

那如果是一棵普通的树，我们可不可以像二叉树一样使用顺序存储的方式来确认孩子与双亲的关系呢？

要回答这个问题，我们就需要先弄清树与二叉树之间的关系。

二、树与二叉树的关系

从逻辑结构来看，树与二叉树都是一种递归的树形结构，同时也是一种分层结构，具有以下特点：

• 树的根结点没有前驱，除了根结点以外的所有结点有且只有一个前驱
• 树中的所有结点都可以有零个或多个后继

但是二叉树作为一种特殊的树，它的所有结点的后继只有可能是 0~2 个，而在树中，每个结点的后继都是没有限制的。

在二叉树中，正因为后继结点数量的限制，当我们以满二叉树的形式去进行顺序存储时，我们就可以通过结点下标的关系来找到结点的双亲与孩子；

而在一棵树中，由于结点的后继数量不确定，因此我们无法通过下标的关系来找到结点的双亲与孩子；

那如果我们想要通过顺序存储的形式来存储一棵树，我们应该如何处理，才能反映树中各结点之间的逻辑关系呢？

三、树的顺序存储

在二叉树中当我们按照完成二叉树的层序编号对树中的结点进行存储时，此时下标为 i 的结点的孩子结点下标为：

• 左孩子：2 × i
• 右孩子：2 × i + 1

当我们要获取结点 i 的双亲结点，我们可以通过 i / 2 向下取整的方式获取其双亲结点的下标。

能够这样操作的前提，正是因为二叉树的特殊性。而对于一棵普通的树来说，按照顺序存储的方式，我们则是无法通过下标之间的关系来反映结点之间的关系。

为了能够通过顺序存储，准确的找到下标为 i 的结点的双亲结点所对应的下标，我们不妨再通过一块额外的空间来存放其双亲结点的下标。

这种采用顺序存储的方式来存储每一个结点，同时在每个结点中增设一个伪指针，只是其双亲结点在数组中的位置的存储结构就是二叉树的双亲表示法。

3.1 双亲表示法

在顺序存储中，为了能够更好的找到每个结点的双亲的所在，我们会在每个结点中增设一个双亲域，用于表示其双亲的所在位置，如下所示：

【数据结构】树的存储结构_结点_02

用C语言表示该结点结构，如下所示：

代码语言：javascript代码运行次数：0运行复制

typedef int ElemType;
typedef struct ParentNode {
	ElemType data;//数据域
	int parent;//双亲域
}PN;

双亲表示法作为树的顺序存储结构，在实际使用的过程中是通过申请一块连续的存储空间来存放各个结点，因此我们需要在顺序表中记录当前表中的结点个数：

代码语言：javascript代码运行次数：0运行复制

#define MAXSIZE 10
//树的存储结构
typedef struct ParentTree {
	PN list[MAXSIZE];//顺序表
	int n;//结点树
}PTree;

这里我采用的是静态顺序表的方式实现，当然我们也可以采用动态顺序表的方式实现：

代码语言：javascript代码运行次数：0运行复制

//树的存储结构
typedef struct ParentTree {
	PN* list;//动态顺序表
	int max_size;//动态顺序表的最大长度
	int n;//结点数—>当前动态顺序表的长度
}PTree;

两种方式的实现都是可行的，具体的实现就根据个人的喜好了。

双亲表示法实际上就是有两个数据域的顺序表：

• 真正的数据域——用于存放数据
• 伪数据域——用于存放双亲结点下标

在顺序表中，下标又相当于是指向顺序表的指针，因此我们也可以称双亲域为伪指针域。

现在问题来了，既然双亲表示法可以找到每个结点的双亲，那如果我想找到每个结点的孩子呢？那我们还能不能采用顺序存储的方式来实现呢？

答案是可行的，这就是我们下面要介绍的孩子表示法。

3.2 孩子表示法

孩子表示法是将每个结点的孩子结点视为一个线性表，且以单链表作为存储结构。

一棵树中如果有n个结点，就会有n个孩子链表（叶结点的孩子链表为空表）。

而指向孩子链表的n个头指针又组成一个线性表，为了便于查找结点，我们同样可以采用顺序存储的方式来存储每个结点的信息，如下所示：

【数据结构】树的存储结构_二叉树_03

该存储结构对应的C语言实现如下：

代码语言：javascript代码运行次数：0运行复制

//孩子表示法
typedef struct ChildNode {
	int child_pi;//孩子的结点编号
	struct ChildNode* nextchild;//指向下一个孩子的指针
}CN;
//双亲结点
typedef struct PNode {
	ElemType data;//数据域
	CN* child;//指向孩子的指针域
}PN;
//树的存储结构
typedef struct ChildTree {
	PN* list;//顺序表
	int max_size;//动态顺序表最大长度
	int len;//动态顺序表当前长度
}CTree;

3.3 小结

不知道大家有没有发现，不管是双亲表示法还是孩子表示法，实际上都是将双亲与孩子分开存储：

• 双亲表示法：以孩子作为索引，双亲作为索引值，从孩子出发找双亲；
• 孩子表示法：以双亲作为索引，孩子作为索引值，从双亲出发找孩子；

由于其侧重点不同，这也就导致了两种表示方法的功能不相同：

• 在双亲表示法中，由于孩子作为索引，因此我们能够很快的找到双亲，但是如果要找孩子的话，我们则需要遍历整个顺序表；
• 在孩子表示法中，由于双亲作为索引，因此我们能够很快的找到孩子，但是如果要找双亲的话，我们则需遍历整个顺序表；

四、孩子兄弟表示法

介绍完了顺序存储，下面我们就来看一下树的链式存储结构——孩子兄弟表示法。

孩子兄弟表示法爷称为二叉树表示法，即以二叉链表作为树的存储结构。

孩子兄弟表示法是每个结点包括三部分：

• 数据域：存放结点数据
• 左孩子指针：指向左侧第一个孩子
• 右兄弟指针：指向右侧第一个兄弟

其结点结构如下所示：

【数据结构】树的存储结构_二叉树_04

该表示法的结点结构与二叉树的结点结构一致：

代码语言：javascript代码运行次数：0运行复制

//孩子兄弟表示法
typedef struct CBNode {
	ElemType data;//数据域
	struct CBNode* lchild;//左孩子指针
	struct CBNode* rbrother;//右兄弟指针
}CBN;

与二叉树不同的是，二叉树的左右指针分别指向的是左右孩子，而树的孩子兄弟表示法中的左右指针分别指向的是第一个左孩子和第一个右兄弟。

孩子兄弟表示法比较灵活，其最大的优点是可以方便地实现二叉树的转换操作。

结语

在今天的内容中我们介绍了树的三种中常用的存储结构：

• 双亲表示法
• 孩子表示法
• 孩子兄弟表示法

这三种存储结构对于任意一棵树或者森林来说都是可以使用的。比如二叉树同样可以采用上述的三种存储结构来表示结点之间的关系。

但是要注意的是，对于特殊的树的存储结构，我们是无法运用到所有的树或森林中的。这主要是因为特殊的树的存储结构具有唯一性。就比如二叉树的顺序存储，数组的下标不仅可以表示结点编号，还可以指示结点之间的关系。

今天的内容到这里就全部结束了，在下一篇内容中我们将介绍《树、森林与二叉树的转换》，大家记得关注哦！如果大家喜欢博主的内容，可以点赞、收藏加评论支持一下博主，当然也可以将博主的内容转发给你身边需要的朋友。最后感谢各位朋友的支持，咱们下一篇再见！！！

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2025-03-16，如有侵权请联系 cloudcommunity@tencent 删除前往查看数据结构数据指针存储二叉树

本文标签： 数据结构树的存储结构