大学计算机基础：树的存储结构

由于树中每个节点的孩子可以有多个，所以简单的顺序存储结构无法满足树的实现要求。下面介绍三种常用的表示树的方法：双亲表示法、孩子表示法和孩子兄弟表示法。

1.双亲表示法

由于树中每个节点都仅有一个双亲节点（根节点没有），我们可以使用指向双亲节点的指针来表示树中节点的关系。这种表示法有点类似于前面介绍的静态链表的表示方法。具体做法是以一组连续空间存储树的节点，同时在每个节点中，设一个「游标」指向其双亲节点在数组中的位置。

由于根节点没有双亲节点，我们约定根节点的parent域值为-1。树的双亲表示法如图9-20所示：

图9-20　树的双亲表示法

这样的存储结构，我们可以根据节点的parent域在O（1）的时间找到其双亲节点，但是只能通过遍历整棵树才能找到它的孩子节点。一种解决办法是在节点结构中增加其孩子节点的域，但若节点的孩子节点很多，节点结构将会变的很复杂。

2.孩子表示法

由于树中每个节点可能有多个孩子，可以考虑用多重链表，即每个节点有多个指针域，每个指针指向一个孩子节点，我们把这种方法叫多重链表表示法。它有两种设计方案：

方案一：指针域的个数等于树的度，图9-21所示。

对于上一节中的树，树的度为3，其实现为：

图9-21　树的多重链表表示法1

显然，当树中各节点的度相差很大时，这种方法对空间有很大的浪费。

方案二，每个节点指针域的个数等于该节点的度，取一个位置来存储节点指针的个数，图9-22所示

对于上一节中的树，这种方法的实现为：(www.xing528.com)

图9-22　树的多重链表表示法2

这种方法克服了浪费空间的缺点，但由于各节点结构不同，在运算上会带来时间上的损耗。

为了减少空指针的浪费，同时又使节点相同。我们可以将顺序存储结构和链式存储结构相结合。具体做法是：把每个节点的孩子节点以单链表的形式链接起来，若是叶子节点则此单链表为空。然后将所有链表存放进一个一维数组中。这种表示方法被称为孩子表示法。其结构如图9-23所示：

图9-23　树的孩子表示法

这种结构对于查找某个节点的孩子节点比较容易，但若想要查找它的双亲或兄弟，则需要遍历整棵树，比较麻烦。可以将双亲表示法和孩子表示法相结合，这种方法被称为双亲孩子表示法。其结构如图9-24所示：

图9-24　树的双亲孩子表示法

其代码和孩子表示法的基本相同，只需在Node节点中增加parent域即可。

3.孩子兄弟表示法

任意一棵树，它的节点的第一个孩子如果存在则是唯一的，它的右兄弟如果存在也是唯一的。因此，我们可以使用两个分别指向该节点的第一个孩子和右兄弟的指针来表示一颗树。

其结构如图9-25所示：

图9-25　树的孩子兄弟表示法

这个方法，可以方便的查找到某个节点的孩子，只需先通过firstChild找到它的第一个孩子，然后通过rightSib找到它的第二个孩子，接着一直下去，直到找到想要的孩子。若要查找某个节点的双亲和左兄弟，使用这个方法则比较麻烦。

这个方法最大的好处是将一颗复杂的树变成了一颗二叉树。这样就可以使用二叉树的一些特性和算法了。