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

我们假设以一段连续空间存储树的结点，同时在每个结点中，附设一个指示器指示其双亲结点到链表中的位置。也就是说，每个结点除了直到自己是谁外，还要直到自己的双亲在哪里。如图：

其中data就是数据域，存储结点的信息。而parent是指针域，存储该结点的双亲在数组中的下标。 双亲表示法的结点结构定义代码：

有了这样的结构定义，我们就可以实现双亲定义法了。由于跟结点没有双亲，所以我们约定根结点的位置域设置为-1，这就意味着，我们所有结点都直到他双亲的位置。如图的树结构和双亲表示法的图表。

我们可以通过上面快速的找到结点的双亲。但是我们要知道结点的孩子怎么办？那就只有遍历整个结构了。 我们能否改进一下？当然可以，我们可以给结点增加孩子域。

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

指针域的个数等于树的度。（树的度是树各个结点度的最大值）。（结点拥有的子树称为结点的度）。

如图，data就是数据域，child1····是指针域，用来指向该结点的孩子结点。

就像6-4-1的树一样，我们用这个方法来实现。如图。 我们可以看到。^这个符号就是代表当前这个指针域并没有用到。这样如果树的各结点的度差距过大的话，显然非常浪费空间。那我们为什么不按需分配空间呢？这样就有第二种方案了

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

如图，data就是数据域。degree是度域，也就是存在该结点的孩子结点数。child1····是指针域，用来指向该结点的孩子结点。

那么对应的树图就应该是这样。 显然，方案二克服了浪费空间的缺点，但是由于各个结点的链表结构是不相同的，在加上要维护结点的度的数值，在运算上显然有损耗。 能否有更好的方法？既可以减少浪费，又能使结点结构相同。 我们把每一个结点放入顺序存储结构中是合理的，但是每个结点的孩子多少是不确定的，所以我们再对每个结点的孩子建立一个单链表来体现他们的关系。 这就是我们的孩子表示法。 具体办法：把每个结点的孩子排列起来，以单链表作存储结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空。然后n个头指针有组成一个线性表，采用顺序存储结构，存进一个一维数组。如图。 为此，设计两种结构，一个是孩子链表的孩子结点，如图。

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

另一个是表头数组的表头结点。如图。

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

以下是孩子表示法的结构定义代码。

我们可以改进一下。把双亲表示法和孩子表示法综合一下，加一个双亲域。如图。（双亲孩子表示法）

任何一棵树，它的结点的第一个孩子如果是唯一的，它的右兄弟如果存在也是唯一的，因此，我们设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟。 结点结构如图。

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

结构定义代码如下.

对于6-4-1的树来说，这种方法实现的示意图如图。 这种方法给查找某结点的某个孩子带来了方便，只需要通过firstchild 找到此结点的左儿子，然后再通过左儿子找到二弟，一直下去，知道找到具体的孩子。当然，如果想要找到双亲，完全可以增加一个parent 指针域来解决。

参考： 大话数据结构/程杰 著.—北京：清华大学出版社，2011.6