前言

废话不多，数据结构必须学！ 每天更新一章，一篇写不完的话会分成两篇来写~

6.3.2孩子表示法

换一种完全不同的考虑方法。由于树中每个结点可能有多棵子树，可以考虑用多重链表，即每个结点有多个指针域，其中每个指针指向一棵子树的根结点,我们把这种方法叫做多重链表表示法。 不过，树的每个结点的度，也就是它的孩子个数是不同的。所以可以设计两种方案来解决。

方案一：

一种是指针域的个数就等于树的度，复习一下，树的度是树各个结点度的最大值

[data|child|child1|...|childn]

其中data是数据域，child1到childn是指针域，用来指向该结点的孩子结点

用图来说明一下吧

这种方法显然是很浪费空间的，因为有很多结点，它的指针域都是空的

第二种方案

每个结点指针域的个数等于该结点的度，专门取一个位置来存储结点指针域的个数

如下

data为数据域，degree为度域，也就是存储该结点的孩子结点的个数，child1到childn为指针域，指向该结点的各个孩子的结点

实现如图所示

这种方法克服了浪费空间的缺点，对空间利用率提高了很多，但是各个结点的链表是不相同的结构，加上要维护结点的度的数值，在运算上就会带来时间上的损耗

能不能有既可以减少空指针的浪费又能使结点结构相同。

我们为了要便利整棵树，把每个结点放到一个顺序存储结构的数组中是合理的，但，每个结点的孩子有多少是不确定的，所以我们再对每个结点的孩子建立一个单链表来体现它们的关系

这就是孩子表示法。具体办法是，把每个结点的孩子结点排列起来，以单链表作存储结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空。然后n个头指针又组成一个线性表，采用顺序存储结构，存放进一个一维数组中

如下图：

图中：

data firstchild是表示表头结点，其中data是数据域，存储某结点的数据信息。firstchild是头指针域，存储该结点的孩子链表的头指针

child next中child是数据域，用来存储某个结点在表头数组中的下标。next是指针域，用来指向某结点的下一个孩子结点的指针

代码实现如下：

/*树的孩子表示法结构定义*/
 #define MAX TREE SIZE 100
 typedef struct CTNode/* 孩子结点*/
 {
     int child;
     struct CTNode *next;
 }
 typedef struct  //表头结构
 {
     TelemType data;
     ChildPty firstchild;
 }CTBox;
 typedef struct      //树结构
 {
     CTGBox nodes[MAX_TREE_SIZE];    //结点数组
     int r,n;        //根的位置和结点数
 }CTree;

这样的结构对于我们要查找某个结点的某个孩子，或者找某个结点的兄弟，只需要查找这个结点的孩子单链表即可。 对于遍历整棵树也是很方便的，对头结点的数组循环即可。

6.3.3孩子兄弟表示法

任意一个树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此设置两个指针，分别指向该结点的第一个孩子和此节点的右兄弟

如图

其中data是数据域，firstchild 为指针域，存储该结点的第一个孩子结点的存储地址，rightsib 是指针域，存储该结点的右兄弟结点的存储地址。

代码实现：

/*树的孩子兄弟表示法结构定义*/
 typedef struct CSNode
 {
 TElemType data;
 struct CSNodeZ* firstchild, *rightsib;
 } CSNode, *CSTree;

实现效果：

这种表示法，给查找某个结点的某个孩子带来了方便

通过fistchild 找到此结点的长子，

然后再通过长子结点的rightsib 找到它的二弟，

接着一直下去，直到找到具体的孩子。

当然，如果想找某个结点的双亲，这个表示法也是有缺陷的

在来个指针就可以了对吧！~~

上述这种孩子兄弟表示法最大的好处是它把一颗复杂的树变成了一颗二叉树

如下所示

好，开始学二叉树喽~~~