5.4.1树的存储结构

知识总览：

树的逻辑结构：

一个树下有多个子树，每个树中节点的子树数量不确定，可能某个节点的子树有2个，另外一个节点的子树有3个，如果把节点按照下标依次放到数组里边，即使数组中有下标但是因为每个节点的孩子数量不确定，所以也不能确定节点之间的逻辑关系

 

树的存储1：双亲表示法

用数组记录每个节点的父节点在数组中的索引位置，纯顺序存储

因为在树中每个节点除了根节点之外都有唯一的父节点，所以可以把各个节点放在数组中各个索引位置上，另外在数组中再加一个字段表示该节点的父节点索引位置，根节点没有父节点则对应的父节点索引位置设为-1，如下第2张图，根节点A的parent=0，E和F的parent=1，即数组中Index=1即B节点

PTNode每个节点中包括data字段存储节点元素的数据，int类型的parent字段存储该节点的父节点在数组中的索引,struct结构体中包含PTNode数组存储所有的节点+n变量表示树中一共有多少元素

双亲表示法也可以用来表示森林，森林中有多个树，把每个树的根节点的父节点的索引值设为-1，其他节点按层序遍历放到PTNode数组中，好像是这样的。。。。。。。 

优缺点：

在找某个节点的父亲时，直接找该节点对应的parent字段找到父节点的index位置即可，可实现随机访问，方便，在找某个节点的孩子时，只能遍历所有的节点，然后找出parent字段是该节点的，即找孩子时不方便，适用于找父亲多，找孩子少的情况，如并查集

树的存储2：孩子表示法

 用数组记录每个节点的孩子，因为树中每个节点的孩子可能是多个，所以记录孩子的字段是个链表结构，顺序+链式存储

CTBox每个节点信息中包括data字段存储节点元素的数据和指向第一个孩子的指针firstChild，指针firstChild中包括该孩子节点在数组中的索引位置+指向下一个孩子的指针。struct结构体中包含CTBox数组存储所有的节点+n变量表示树中一共有多少元素+r记录根节点在数组中的index索引位置，孩子为空的firstChild指针记为NULL

孩子表示法也可用来表示森林，因为森林有多个树，每个树都有一个根节点，先把所有根节点放到数组中，然后再层次遍历其他节点放在数组中，在记录根的位置时因为有多个根节点所以需要记录多个根的位置

优缺点：

在找某个节点的孩子时，直接找该节点对应的firstChild字段指向的链表即可找到所有孩子节点的index位置，找孩子方便，在找某个节点的父亲时，只能遍历所有的节点的链表，然后找出firstChild指向的孩子链表中有该节点的元素，对应的data即为该节点父亲，即找父亲时不方便，适用于找孩子多，找父亲少的情况，如服务流程树，拨打电话普通话服务请按1,然后再问你办理业务1按#键啥的，，，，直到找到最下一层服务节点

 

树的存储3：孩子兄弟表示法(链式存储)

纯二叉链表结构存储

类似于二叉树的二叉链表结构(data字段存储元素数据，lchild指针指向左子树，rchild指针指向右子树)，每个节点表示时用一个data字段表示节点数据，用firstChild指针指向该节点的第一个孩子(从左到右顺序)，nextsibling指针指向该节点的右边的一个兄弟节点(从左到右顺序)

如下第2张图：树的根节点A节点的第一个孩子从左到右是B节点，则放在A节点左指针下方作为A的左子树，A节点没有兄弟节点，则A节点的右指针指向NULL，此时已经画了A、B节点，则从树的层序遍历从左到右顺序，下一个处理C节点，C是B的右边第一个兄弟，则C放在B的右指针下方成为B的右子树，处理D，D是C的右边第一个兄弟，则D放在C的右指针下方成为C的右子树，然后处理下一层EFGHIJ，按照从左到右顺序先处理E，E是B的第一个左孩子则E放在B的左指针下方成为B的左孩子，处理F，F是E的右边第一个兄弟放在E的右指针下方成为E的右孩子，再看G是C的第一个孩子，则G放在C的左指针下方成为C的左孩子，看H是D的第一个孩子则放在D的左指针下方成为D的左孩子，I是H的右边的兄弟节点则放在I的右指针位置成为I的右孩子，J是I的右边兄弟节点则J放在I的右指针下方位置成为I的右子树，再处理下一层K，K是E的第一个孩子，则把K放在E的左指针下方成为E的左子树

看该节点的第一个孩子让该孩子成为该节点的左子树，剩下的孩子依次成为兄弟节点，依次放在这些节点的右指针位置

孩子兄弟表示法可以表示森林：

森林有多个树，每个树都有一个根节点，这些根节点可以视为平级的兄弟关系，从左到右让第一个树的根节点作为孩子兄弟表示法的根节点，剩余根节点依次成为上一个节点的右孩子。如下最后一张图BCD是根节点，从左到右顺序B是根节点，C是B的右边的兄弟节点，D是C右边的兄弟节点，则C放在B的右指针位置成为B的右孩子，D放在C的右指针位置成为C的右孩子，再按层序遍历遍历剩余没处理的节点，第2层的EFGHIJ，E是B的第一个孩子放在B的左指针下方成为B的左孩子，F是E的右兄弟节点放在E的右指针下方成为E的右孩子，再处理G，G是C的第一个孩子放在C的左指针位置成为C的左孩子，H是D的第一个孩子，H放在D的左指针位置成为D的左孩子，I是H的右边的兄弟节点，J是I右边的兄弟节点，则I放在H的右指针位置成为H的右孩子，J放在I的右指针位置成为I的右孩子，按层序遍历从左到右遍历第3层的KLM，K是E的第一个孩子放在E的左指针位置成为E的左孩子,L是K的右边的兄弟节点，则L放在K的右指针位置成为K的右孩子，M是H的第一个孩子放在H的左指针位置成为H的左孩子,所有节点处理完成，结束。

 

 知识回顾：

。。。。。。。。。。