引入

前面，我们介绍了双亲表示法，每个结点中出了节点的值，还保存了parent的信息。今天我们换个角度，用孩子表示法来看看如何构建树的存储结构。

想一想

现在双亲表示发的问题在哪？

只能体现双亲信息和该结点信息
没有孩子的信息
增加节点内的结构只能增加部分孩子信息，如3个、5个
如果某个子节点大量孩子加入，会造成内存空间浪费

想达到什么效果？

能体现孩子的信息
孩子无论增加多少，都可以只浪费一定的内存空间
如果能再包含双亲的信息就更好了！

我们看着这张图，然后想，能不能将链表和顺序存储结构结合起来

数组下标	Data	Pointer	P1	P1-Node	P2	P2-Node	P3	P3-Node
0	A	->	1	->	2	->	3	NULL
1	B	->	4	NULL
2	C	NULL
3	D	->	5	->	6	NULL
4	E	->	7	->	8	->	9	NULL
5	F	NULL
6	G	->	10	NULL
7	H	NULL
8	I	NULL
9	J	NULL
10	K	NULL

经过修改，我们看这个架构，由数组和链表组合而成

数组存储结点信息和链表的头部地址
链表则存储者孩子的信息
例如：A 是根，下标是0，A 有三个孩子，三个孩子分别在下标1、2、3，A 的指针域是链表的头部，指向了三个孩子所在的下标。
这种通过链表的方式扩展孩子，每个结点只要留出一个用于存储地址的指针域空间，就可以通过链表的方式不断的增加孩子的数量了。

等等…我们不是说最好再有双亲信息就更完美了吗？

没关系，我们把上一节的双亲表示法和孩子表示法结合组成双亲孩子表示法

数组下标	Data	Parent	Pointer	P1	P1-Node	P2	P2-Node	P3	P3-Node
0	A	-1	->	1	->	2	->	3	NULL
1	B	0	->	4	NULL
2	C	0	NULL
3	D	0	->	5	->	6	NULL
4	E	1	->	7	->	8	->	9	NULL
5	F	3	NULL
6	G	3	->	10	NULL
7	H	4	NULL
8	I	4	NULL
9	J	4	NULL
10	K	6	NULL

我们将结点的信息再次增加一个 Parent 信息，这样我们既可以直到孩子的信息，又可以直到双亲的信息，并且孩子的后期扩展也不会大量的浪费内存空间。

代码

我们来看看如何构建这个双亲孩子表示法

#define MAXSIZE 100

struct child{
    int child;  //孩子链表的中该结点对应的数组下标
    struct child *next;  //指向下一个结点，也就是其兄弟的地址
};

struct treeNode{
    int data;  //每个结点存储的数据
    int parent;   //每个结点父母的下标位置
    struct child *next;  //如果有孩子，孩子链表的头结点地址
};

struct tree{
    struct treeNode *tree[MAXSIZE];  //树上的结点
    int r;  //存储根的位置
    int n;  //存储当前结点数量
};

之后还有孩子兄弟表示法，我们先学习完二叉树的概念，然后再看看孩子兄弟表示法。

尾巴

这是我的个人学习笔记，主要是应付考研复习使用，充斥着一些吐槽和个人观点，并不严谨，欢迎大家参考、指正。