【数据结构】树、森林与二叉树的转换
树、森林与二叉树的转换
导读
大家好，很高兴又和大家见面啦！！！
在上一篇内容中我们介绍了树的三种常用存储结构：
- 顺序存储结构：
- 双亲表示法：使用顺序表记录孩子结点，新增伪指针域记录双亲编号
- 孩子表示法：使用顺序表记录双亲结点，使用链表记录孩子编号
- 链式存储结构：
- 孩子兄弟表示法：以左指针指向孩子第一个孩子结点，右指针指向第一个兄弟结点
树的这三种存储结构可以用于所有的树和森林，例如二叉树同样可以使用这三种存储结构；
但是对于特殊树的存储结构，则不适用于其它的树或者森林。如二叉树的顺序存储结构，是用于存储满二叉树与完全二叉树，对于一般的树则不能通过二叉树的顺序存储结构来表示结点之间的关系。
树的孩子兄弟表示法，与二叉树一样，都是通过左右指针来表示结点之间的关系。因此借助孩子兄弟表示法，我们可以实现树、森林与二叉树的相互转换。
那我们应该如何进行树、森林与二叉树的相互转换呢？在今天的内容中，我们将会一起探讨，下面我们就开始今天的内容吧！！！
一、树与森林
在现实生活中的树是多年生木本植物，具有以下特征：
- 主干：单一明显的主干，支撑整体结构。 - 分枝：从主干分出侧枝，形成层次化结构。 - 根系：地下部分形成根系，吸收养分并固定植物。 - 高度：通常高于其他植物（如灌木、草本）。 - 生命周期：多年生长，经历发芽、生长、衰老等阶段。
树的作用主要是进行光合作用、为生物提供栖息地、调节气候等。
森林则是以乔木（树木）为主体，结合灌木、草本植物、苔藓、地衣等生物群落，以及与它们相互作用的非生物环境（如土壤、气候、水等）共同构成的生态系统。其通常覆盖较大面积，具有多层次结构和显著的生态功能。
在计算机的世界中，树指的是一种递归的数据结构，树中的元素之间存在一对多的关系，除了根结点外，所有结点都有且只有唯一前驱。
那计算机世界中的森林又是什么呢？是不是和生活中的森林一样由多个元素构成呢？下面我们就来认识以下计算机世界中的森林；
1.1 定义
森林（Forest） 是由零棵或更多棵互不相交的树（Tree）组成的集合。
和生活中的森林不同，计算机世界中的森林只有一类元素——树，且森林中的树互不相交。
在计算机的世界中，空树也是一棵树，那也就是说，一棵树同时也是由该树与一棵空树组成的森林。
从这里我们可以看到，计算机中的森林与现实生活中的森林还是有很大区别的：
- 现实中的森林是一个生态系统，其中不仅有树，还有其它的元素共同构成；
- 计算机中的森林则是一个集合，这个集合内只要存在不相交的两棵树即可。因此在计算机的世界中，一棵树就是一个森林。
明确了森林的定义后，下面我们就来看一下森林的存储结构；
1.2 森林的存储结构
在树中，常用的存储结构有3种：
- 双亲表示法
- 孩子表示法
- 孩子兄弟表示法
这三种存储结构在森林中同样适用，下面我们就来看一下森林中这三种存储结构应该如何实现；
1.2.1 双亲表示法
在双亲表示法中，我们需要存储孩子结点的信息以及双亲的位置信息，因此森林中各棵树的根结点所对应的双亲信息均为-1，如下所示：
双亲表示法对应的C语言代码如下所示：
代码语言：javascript代码运行次数：0运行复制//森林的双亲表示法
//树的结点结构
typedef struct PNode {
ElemType data;//孩子信息
int parent;//双亲位置信息
}PNode;
//双亲森林的结构
typedef struct PForest {
PNode* forest;//森林
int max_size;//森林最大长度
int n;//森林结点数量
}PForest;有没有发现森林的双亲表示法实际上和树的双亲表示法一致。下面我们就来看一下森林的孩子表示法；
1.2.2 孩子表示法
在孩子表示法中，我们通过顺序表记录双亲的结点信息，用链表记录孩子的位置信息，如下所示：
与双亲表示法一样，森林的孩子表示法无非就是将父结点的孩子信息进行了更改，对应的C语言代码如下所示：
代码语言：javascript代码运行次数：0运行复制//孩子表示法
//孩子链表结点
typedef struct CNode {
int child_pi;//孩子位置信息
struct CNode* nextchild;//下一个孩子指针
}CNode;
//双亲顺序表结点
typedef struct ParentNode {
ElemType data;//双亲信息
CNode* child;//孩子链表
int n;//孩子结点数量
}PN;
//孩子森林结构
typedef struct CForest {
PN* list;//双亲顺序表
int max_size;//动态顺序表最大长度
int n;//森林结点数量
}CForest;从这两种存储结构我们不难发现，森林的存储结构与树的存储结构是一致的，只不过是称呼不同。下面我们继续来看森林的孩子兄弟表示法；
1.2.3 孩子兄弟表示法
在森林中，每棵树都不相交，因此我们可以认为各棵树的根结点为兄弟结点，那么根结点的信息我们可以通过第一棵树的根结点的右兄弟指针去依次记录；而孩子结点的信息我们则是依旧通过左孩子指针去记录：
其C语言代码如下所示：
代码语言：javascript代码运行次数：0运行复制//孩子兄弟表示法
typedef struct ForestNode {
ElemType data;//数据域
struct ForestNode* lchild;//左孩子
struct ForestNode* rbrother;//右兄弟
}FN, * F;森林的孩子兄弟表示法与树的一致，这里我们就不再赘述。接下来我们继续来看如何借助孩子兄弟表示法完成树、森林与二叉树的转换；
二、树与二叉树的相互转换
从前面的介绍来看，我们对森林的操作与对树的操作是一致的。既然这样，那接下来我们就通过树与二叉树的转换来学习森林与二叉树的转换；
2.1 树转换为二叉树
对于一棵树而言，由于它的结点的度可能不一致，那么我们想要将其转化为二叉树，只需要借助孩子兄弟表示法通过左指针指向左孩子，通过右指针指向右兄弟，即可完成转换：
有朋友可能会说，这好像也不是二叉树啊！！！看起来也不像啊！！！
别着急，下面我们将转换后的树做一个变形，咱们再看看变形后的树的形态：
现在再来看树的形态，是不是和二叉树一致了！！！
因此当我们要将任意一棵树转化为二叉树时，我们只需要通过孩子兄弟表示法进行树的存储，即可完成转换。
2.2 二叉树还原为树
这里需要注意，我们这里说的二叉树还原指的是通过孩子兄弟表示法进行存储的二叉树，而不是通过二叉树存储结构进行存储的二叉树。
所谓的二叉树存储结构指的是二叉树的存储结构：
代码语言：javascript代码运行次数：0运行复制//二叉树存储结构
typedef struct BiTreeNode {
ElemType data;//数据域
struct BiTreeNode* lchild, * rchild;//左右孩子指针
}BTN, * BT;如果是以该存储结构进行存储的树，那我们不需要进行还原。如果要说明原因的话，那就是结点的左右指针指向的两个结点的辈分不同：
- 二叉树存储结构的二叉树中，左孩子的右侧为它的右兄弟
- 孩子兄弟结构的二叉树中，左孩子的右侧为它的双亲结点的兄弟，即它的叔叔
用文字解释可能不太清楚，下面我们直接看图：
上图中，颜色相同的结点互为兄弟，颜色不同的结点，层序在上层的为下层结点的双亲。结点之间的关系，图中也有文字说明，这里我就不再赘述。
下面我们就来看一下如何对孩子兄弟表示法的二叉树进行还原：
相信大家应该能够理解整个还原过程的基本原理了，整个还原的过程就是根据指针的指向完成：
- 左孩子指针指向的结点，还原为该结点的孩子
- 右指针指向的结点，还原为该结点的兄弟
上图展示的是根据每一个结点进行还原的过程，当然大家也可以有自己的还原方式，只要还原的核心逻辑不变，无论怎么还原都是可以的。
三、森林与二叉树的相互转换
首先我们先说结论：
- 森林与二叉树的相互转换与树的转换相同
那是不是完全一样呢？很显然不是，森林与树的区别，就是在对根结点的处理：
- 树的根结点的右指针是指向空
- 森林的根结点的右指针是指向下一棵树的根结点
因此当我们处理好了根结点，那其它结点的处理就是和树的处理一致。
下面我们就来简单的了解一下森林与二叉树在转化的过程中对根结点的处理方式：
3.1 森林转换二叉树
当我们通过孩子兄弟表示法来存储森林时，从第一棵树开始，每棵树的根结点的右指针都会指向下一棵树的根结点：
下面我们就来看一下二叉树如何还原为森林；
3.2 二叉树还原森林
当我们要将二叉树还原为森林时，如果树非空，那我们主要进行的就是2步操作：
- 断开根结点右链，获取两棵二叉树：
- 由根结点及其左子树构成的二叉树
- 由根结点的右指针指向的二叉树
- 根据左孩子与右兄弟的逻辑将左子树还原为树
右指针指向的二叉树按照上述步骤继续进行还原，直到最后一棵树被还原，即最后一个根结点的右指针指向为空，那我们就完成了所有的二叉树的还原；
结语
在今天的内容中我们介绍了树、森林与二叉树之间的转换，其核心逻辑为：
- 通过孩子兄弟存储结构完成树与森林转换为二叉树
当我们要将二叉树还原为树和森林时，其核心逻辑为：
- 左指针指向的结点为孩子结点
- 右指针指向的结点为兄弟节点
整个转换过程并不复杂，我们只需要理解了整个转换的核心逻辑即可。
今天的内容到这里就全部结束了，在下一篇内容中我们将介绍《树与森林的遍历》，大家记得关注哦！
如果大家喜欢博主的内容，可以点赞、收藏加评论支持一下博主，当然也可以将博主的内容转发给你身边需要的朋友。最后感谢各位朋友的支持，咱们下一篇再见！！！
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2025-03-17，如有侵权请联系 cloudcommunity@tencent 删除数据结构计算机指针存储二叉树
发布评论