扫码获取更多资源

●树的存储表示及操作实现

树的存储结构除了要求能存储各结点的数据信息，还要求能唯一地反映树中各结点之 间的逻辑关系。但由于树中各结点的度变化范围较大，因此树的存储结构比较复杂。下面 将介绍树的几种表示方法，在应用问题中应该根据问题的特点和所需要进行的操作适当 选择。

双亲表示法

由于树中每个结点都有且仅有一个双亲，因此可以采用一维数组按层序存储树的各个 结点。假设以一组连续空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲 在数组中的位置。采用这种存储结构的树称为双亲顺序表(Parent Sequential List),其实质 是一个静态链表。

数组元素结构如图6-6所示。其中：data存储树中结点的数据信息；parent存储该结 点双亲在数组中的下标，当为一1时表示该结点无双亲，即该结点是根结点。

双亲顺序表的特点

这种存储结构利用了每个结点(根结点除外)只有唯一双亲的性质。由于parent向上 连接，因此适合求指定结点的双亲或祖先(包括根)的操作。但在这种表示法中，如果求指定 结点的孩子或其他后代时，则需要遍历整个结构。

孩子表示法

多重链表

由于树中每个结点都可能有多个孩子，因此可以釆用多重链表，即每个结点有多个指针 域，其中每个指针指向一个孩子。因为树中各结点的度不同，所以结点指针域的设置有两种 方法。

对于①，“访问”的含义是对学号进行修改操作；对于②，“访问”的含义是打印每一个结 点的部分信息；对于③，“访问”的含义只是统计。但不管访问的具体操作是什么，都必须做 到既无重复，又无遗漏。

方法一是指针域的个数等于该结点的度，如图6-8(a)所示。其中：data存储该结点的 数据信息；degree存储该结点的度；d等于degree域的值；child】〜chil如 存储指向该结 点孩子的指针。

不失一般性，在此将“访问”定义为输出结点的信息，因此通过遍历，可以使树中结点变 成某种意义上的线性序列。

孩子链表

把每个结点的孩子结点排列起来，看成是一个线性表，且以单链表作为存储结构，则n 个结点有n个孩子链表，叶子的孩子链表为空表；而n个头指针又组成一个表头线性表，为 了便于查找，采用顺序存储结构按层序存储。采用这种存储结构的树称为孩子链表(Child Linked List) o

孩子结点结构如图6-9(a)所示，其中：child存储树中结点孩子在表头数组中的下标； next存储指向该结点下一个孩子的指针。表头结点如图6-9(b)所示，其中：data存储树中 结点的数据信息；firstchild存储该结点孩子单链表的头指针。

双亲孩子表示法

在树的孩子链表的表头结点结构中增加一个双亲域，即将树的双亲顺序表与树的孩子 链表结合起来。釆用这种存储结构的树称为双亲孩子链表(Parent Child Linked List)o

双亲孩子链表的孩子结点结构与树的孩子链表中的

孩子结点结构相同，如图6-9(a)所示。表头结点结构修 —data ~parent I firstchild I

改如图6-11所示，其中:data存储树中结点的数据信 图6_ii双亲孩子链表表头结点结构 息；parent存储该结点双亲在表头数组中的下标，当为

-1时表示该结点无双亲，即该结点是根结点；firstchild存储该结点孩子单链表的头指针。 对于图6-2(a)所示的树

孩子兄弟表示法

链表中的结点是同构的，每个结点除了数据域外，还设置了两个指针域，分别指向该结 点的第一个孩子和下一个兄弟。采用这种存储结构的树称为孩子兄弟链表(Child Sibling Linked List),又称为二叉链表(Binary Linked List)

二叉链表结点结构如图6-13所示，其中：data存储树中

结点的数据信息；firstchild指向该结点的第一个孩子；firstchild data rightsib rightsib指向该结点的下一个兄弟。对于图6-2 (a)所不的 图6T3二叉链表结点结构 树，其二叉链表存储结构如图6-14所示。

联系我们：