数据结构-5.9.树的存储结构

---

一.树的逻辑结构：

---

二.双亲表示法(顺序存储)：

1.树中除了根结点外每一颗树中的任意一个结点都只有一个父结点(双亲结点)；

2.结点包括结点数据和指针；

3.上述图片中右边的顺序存储解析：比如A结点左边的0，就是在数组中的位置即第一个位置，A结点右边的-1代表没有双亲即没有父结点，结点C左边的2代表在数组中第3个位置，右边的0就是结点C的父结点即A结点在数组中的位置，其他同理；

4.上述图片中的代码解析：PTNode代表结点，结构体里的nodes数组是PTNode型，也就是结点的集合，构成了树，结构体PTNode里有结点的数据和指向双亲位置域的双亲指针，指针是int型(不是int *)，因此指向的是双亲结点在数组中的位置下标；

5.基本操作：

a.增加结点：

上述图片增加一个结点M在结点H下，顺序存储在第12个位置即数组下标为11，结点M的父结点为H，结点H在数组中下标为7，因此结点M的结点指针parent为7：

此时数组中数据元素的排列顺序表面像是层序规则排列，但在插入新结点时并不需要遵守层序的规则即不需要同一层中必须先从最左边添加，然后依次添加到最右边，而是可以随意添加在某个结点下，比如再插入一个L结点在E结点下：

b.删除结点：

比如删除G结点，有两种方案：

方案一：把G结点的双亲指针改为-1(因为双亲指针的值就是对应结点的父结点在数组中的位置，此时G结点不存在了，即在该树中没有父结点，因此双亲指针可设为-1，是一个不存在的数组下标)

方案二：把尾部的数据即结点L里的数据移动到G结点的位置上，这样就保证数组里的每一个存储单元都是有效的(比方案一好)

注：删除结点后要把结点数减一，不是数组长度减一

刚才删除的G结点是叶子结点，如果删除的不是叶子结点，那么既然该结点被删除了，那么这个结点下面连着的所有结点即以该结点为根结点的树就都被删除了：如删除D结点，那么结点D,H,I,J,M就都被删除了，此时就涉及到查询除了根结点D外H,I,J,M在数组中的位置，然后更改双亲指针进行删除；

c.查询结点(查询到结点后也可以修改结点数据)：

采用双亲表示法，找到父结点很容易，因为有双亲指针直接可以知道父结点在数组中的位置，

但如果找父结点的子结点，就只能从头到尾依次遍历，把每一个结点的双亲指针取出来，对比是否与父结点在数组中的下标相等，这也就暴露出删除结点中方案一是有些低效的，因为该方案中删除元素后会有双亲指针的无效数据，此时遍历数组时也会把这个无效数据一起遍历，降低了效率，因此删除结点中方案二较好，

6.回顾：二叉树的顺序存储（二叉树也是树，也可以用双亲表示法）

---

三.孩子表示法(顺序+链式存储结合)：

1.核心：先利用顺序表开辟一个顺序存储空间即数组来存储各个结点里的数据，每个结点包含数据域和指向第一个子结点的指针

2.代码：

解析：结点CTBox结构体中存储数据和第一个孩子，链表struct CTNode中的各个结点其实只是保存了各个子结点的数组下标

对于上述代码呈现出的存储结构，可知找子结点很方便，但找双亲结点就较麻烦；

---

四.孩子兄弟表示法(链式存储)：

1.代码：

解析：1.*firstchild指针可看作左指针，指向结点的第一个子结点(不一定叫左子结点，因为可能不是二叉树，但一定是第

一个结点)，

*nextsibling指针可看作右指针，指向结点的第一个子结点的后面结点即右兄弟结点

(左孩子，不同层；右兄弟，同层)

(从物理上看，用孩子兄弟表示法保存的树形状上和二叉树一样，只不过左右指针的含义不同)

如根结点A(只有孩子没有同层的兄弟)，结点A的*firstchild指针指向B结点，

由于B结点的右兄弟为C结点，所以结点B的 *nextsibling指针指向 C结点，

由于C结点的右兄弟为D结点，所以结点C的 *nextsibling指针指向D结点，

同理，结点B的第一个孩子为E结点，那么结点B的*firstchild指针指向E结点，

由于E结点的右兄弟为F结点，所以结点E的 *nextsibling指针指向 F结点，

结点E的第一个孩子为K结点，那么结点E的*firstchild指针指向K结点，

同理，结点C的第一个孩子为G结点，那么结点C的*firstchild指针指向G结点，

同理，结点D的第一个孩子为H结点，那么结点D的*firstchild指针指向H结点，

由于H结点的右兄弟为I结点，所以结点H的 *nextsibling指针指向 I结点，

由于I结点的右兄弟为J结点，所以结点I的 *nextsibling指针指向 J结点，

2.例如：二叉树转化为树

思路：要把二叉树看作是用二叉链表保存的树，左边的第一个结点是孩子，剩下的右边全是兄弟

首先A是根结点，A结点的左边第一个结点B为左孩子，可知在B的右边的结点C,F,L都是它的右兄弟，所以：

看以B为根结点的子树，D结点是B结点的左孩子，H结点连在D结点的右边，所以H结点是D结点的右兄弟，

同理，G结点是D结点的左孩子，后续同理，最终如下：

---

五.森林和二叉树的转换：

本质：用二叉树链表(孩子兄弟表示法)存储森林

核心：可以利用二叉链表的方式来存储森林，一个森林里有几个互不相交的树，首先把森林里的树都转换为二叉树，森林里的每一棵树在逻辑上看是平级的，因此可以把这些树的根结点看作兄弟结点，如果用二叉链表(孩子兄弟表示法)存储的话，右指针表示兄弟关系，因此可以把这些树的根结点用右指针连接起来：

例题：

把二叉树转换为森林：

思路：从根结点A出发，右边的结点C,F,L都是右兄弟，因此结点A,C,F,L是平级的兄弟关系，

因此结点A,C,F,L就是四棵互不相交的树的根结点，

对于A结点，第一个孩子为B结点，B结点没有右兄弟，C结点已经用了，这里无需处理C结点

对于B结点，第一个孩子为D结点，D结点没有右兄弟，

对于D结点，第一个孩子为G结点，D结点的右兄弟为H结点，因此B结点的右边连接H结点，

对于C结点，第一个孩子为E结点，F结点已经用了，这里无需处理F结点，

对于E结点，第一个孩子为I结点，E结点的右兄弟为J，因此C结点右边连接J结点，

对于F结点，第一个孩子为K结点，L结点已经用了，这里无需处理L结点，

对于L结点，左右没有连接任何东西，所以处理完毕：

---

六.总结：

---