数据结构与算法之树的孩子双亲存储结构的讲解

淡淡的烟草味﹌ 2022-06-06 07:47 207阅读 0赞

注意看这个知识点需要有的树数据结构的基本知识，本文不贴实际代码只是讲解孩子双亲存储结构的由来和优点，为什么要用这个以及其他方式的缺点对比。先上图

![这里写图片描述][SouthEast]  
这个图是由11个字母组成的树关系的图，为什么趁为树，因为他们之间的联系看起来像树而命名。  
图的深入分析：这个树的根节点是字符A,他的孩子节点又 是3个子树，分别是根节点B,C,D组成。叶子节点也就是没有孩子了有C,F,H,I,J,K.  
这个图完美的告诉了我们A字母和B,C,D是有前后联系，在计算机中我们比如输出了A字母，然后可以通过A数据对应的对象可以直接拿到B,C,D。这个关系我们把他们用图给画出来。  
现在我们想把这些关系和字母数据保存在计算机里面，假如我们是用数组连续内存的形式把这些数据字母全部保存在计算机中，并且把字母之间的联系也保存下来，这些联系是指什么我们要实现的是比如字母我们拿到了B字母之后可以一步拿到B字母的父亲和孩子节点。我们设计的数据结构就是实现这个操作，所以我们趁这个数据结构叫双亲孩子存储数据结构。  
现在我们的需求明白了就是用我们的编程语言设计出可以保存数据和数据和数据的孩子以及双亲的联系。首先我要说明下这个设计的好处，这个设计可以用0(1)时间复杂度查找到孩子和双亲节点，是不是效率不错，好了下面进入正题：  
现在是我们该如何设计这颗树中的每个节点的数据结构类型，我先上图在分析  
如何我们按照刚刚贴出的图来分析根节点的数据类型有3个孩子节点一个父节点类型，而 c节点又 是0个孩子节点一个父节点。每个节点数据节点类型里面包含的东西都不同，设计和维护都非常困难，因此不能安装这个图的法则去设计节点数据类型  
![这里写图片描述][SouthEast 1]  
请看上图，如果我们统一树每个节点数据类型里面的结构  
//孩子节点  
typedef struct CTNode  
\{  
int child1; //孩子节点的下标  
int child2; //孩子节点的下标  
int child3; //孩子节点的下标  
int child4; //孩子节点的下标  
……

\}\*ChildPtr;  
根据这颗树中节点孩子树最多的类型来设计。这个设计有什么缺点就是浪费很多内存，内存换设计的复杂性，可以看出里面很多内存都是null没有存任何数据。  
下面我上第二种方案  
![这里写图片描述][SouthEast 2]  
这个方案上述已经分析完毕，这个会设计很多数据类型，非常难维护。

分析以上2个方案的优点进行综合：第一个方案节点数据类型结构固定，第二方案每个节点只是保存了他的全部孩子节点的地址。

下面结合上述方案的优点结合产生第三种方案：

![这里写图片描述][SouthEast 3]  
大家仔细看我们树存储结构如图，首先我们是开了个连续内存的数组，我们假如内存编号从0到10分别存放字符ABC…jk. 现在我们来分析数组里的每个数据节点类型，这个类型里面包含了父亲内存节点和第一个孩子的内存地址。  
好了下面来分析孩子节点的数据节点类型设计  
通过图我们可以看的出孩子节点第一个存的是节点的地址以及下一个孩子节点的地址。  
现在开始上具体设计代码：

\#define MAX\_TREE\_\_SIZE 100 //定义常量树最大节点的数量  
typedef char ElemType;  
typedef struct CTNode //孩子节点数据结构类型的设计  
\{  
int child; //孩子节点的下标索引  
struct CTNode \*next； //指向下一个孩子的索引  
\}\*ChildPtr;

//下面针对数组结构中的具体一个元素设计数据结构类型  
//树的表头节点  
typedef struct  
\{  
ElemType data; //节点数据元素  
int parent; //存放双亲节点的下标  
ChildPtr firstChild; //当前节点的第一个孩子节点的下标  
\}CTBox;

//现在正式设计树数据结构类型  
typedef struct\{  
CTBox\[MAX\_TREE\_\_SIZE\];//保存全部的树节点数据元素  
int r,n; //保存根节点索引和树当前节点元素的数量。  
\}

ok双亲孩子存储结构设计类型设计完毕

[SouthEast]: /images/20220606/07387e764316458aa003a89bb7653717.png
[SouthEast 1]: /images/20220606/846333a4f6c5457da2ceef1af1696ead.png
[SouthEast 2]: /images/20220606/3501052db73d478e8f36d6e368fed52f.png
[SouthEast 3]: /images/20220606/5464baec28ba4e52af7f82edfac1df46.png