树的存储结构

因为树中某个结点的孩子可以有多个，这就意味着，无论按何种顺序（无论是顺序存储还是链式）将树中所有结点存储到数组中，结点的存储位置都无法直接反映逻辑关系。

不过充分利用顺序存储和链式存储的特点，完全可以实现对树的存储结构的表示，三种不同的表示法：双亲表示法、孩子表示法、孩子兄弟表示法。

双亲表示法

假设以一组连续空间存储树的结点，同时在每个结点中，附设一个指示器指示其双亲结点到链表中的位置。即每个结点，除了知道自己是谁外，还知道它的双亲在哪里。

其中 data 是数据域，存储结点的数据信息，而 parent 是指针域，存储该结点的双亲在数组中的下标。代码如下：

有了这样的结构定义，我们就可以实现双亲表示法了。由于根结点是没有双亲的，所以我们约定根结点的位置域设置为 -1，

这样的存储结构，我们可以根据结点的 parent 指针很容易找到它的双亲结点，所用时间复杂度为O(1)，直到 parent 为 -1 时，表示找到了树结点的根。如果要知道结点的孩子，还是要遍历整个结构。

相应演变：

增加最左边孩子的域  增加右兄弟域

孩子表示法

由于树中每个结点可能有多棵子树，可以考虑用多重链表，即每个结点有多个指针域，其中每个指针指向一棵子树的根结点，我们把这种办法称为多重链表表示法。
问题：每个结点的度，也就是它的孩子个数不同，怎么解决？

1. 方案一：
   一种是指针域的个数等于树的度，（即树各个结点度的最大值），其结构如下。
   其中 data 是指针域， child1 到 childd 是指针域，用来指向该结点的孩子结点。
   
   特点：
   树中各结点的度相差很大时，显然是很浪费空间的，因为有很多结点它的指针域是空的。

如果树的各结点度相差很小时，那就意味着开辟的空间被充分利用了。

2. 方案二——按需分配
   每个结点指针域的个数等于该结点的度，专门取一个位置来存储结点指针域的个数。其结构如图所示。
   
   data 为数据域， degree 为度域，也就是存储该结点的孩子结点的个数， child1 到 childd 为指针域，指向该结点的各个孩子的点。
   
   特点：
   克服了浪费空间的缺点，对空间利用率是提高了，但是由于各个结点的链表是不相同的结构，加上要维护结点的度的数值，在运算上就会带来时间上的损耗。

方法改进： 对每个结点的孩子建立一个单链表体现它们的关系。

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

孩子兄弟表示法

经观察发现，任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。所以，我们设置了两个指针，分别指向该结点的第一个孩子和此结点的右兄弟。
如图：
其中 data 是数据域， firstchild 为指针域，存储该结点的第一个孩子结点的存储地址， rightsib 是指针域，存储该结点的右兄弟结点的存储地址。
结构定义：
这种方法实现的示意图：

这种表示法，给查找某个结点的某个孩子带来了方便，只需要通过 firstchild 找到此结点的长子。
问题：如何找到某个结点的双亲？
可以通过再增加一个 parent 指针来解决快速查找双亲的问题。

这个表示法的最大好处就是它把一棵复杂的树变成了一棵二叉树。