树的应用 —— 树的存储

树的应用 —— 树的存储

树形结构是一对多的关系，除了树根，每个节点都有一个唯一的直接前驱（双亲）；除了叶子，每个节点都有一个或多个直接后继（孩子）。

那么如何将数据及它们之间的逻辑关系存储起来呢？

仍然可以采用顺序存储和链式存储。

【顺序存储】

顺序存储采用一段连续的存储空间，因为树中节点的数据关系是一对多的逻辑关系，所以不仅要存储数据元素，还要存储它们之间的逻辑关系。

顺序存储分为双亲表示法、孩子表示法和双亲孩子表示法。

[举个栗子]

① 双亲表示法

除了存储数据元素，还存储其双亲节点的存储位置下标，其中“-1”表示不存在。

每个节点都有两个域：数据域data和双亲域parent，如下图（a）所示。

树根A没有双亲，双亲被记为-1。B、C、D的双亲为A，而A的存储位置下标为0，因此B、C、D的双亲被记为0。同样，E、F的双亲为B，而B的存储位置下标为1，因此E、F的双亲被记为1。同理，其他节点也这样存储。

② 孩子表示法

除了存储数据元素，还存储其所有孩子的存储位置下标，如下图（b）所示。

A有3个孩子B、C、D，而B、C、D的存储位置下标为1、2、3，因此将1、2、3存入A的孩子域。

同样，B有两个孩子E、F，而E、F的存储位置下标为4、5，因此将4、5存入B的孩子域。在本题中，每个节点都被分配了3个孩子域，B只有两个孩子，另一个孩子域记为-1，表示不存在。同理，其他节点也这样存储。

③ 双亲孩子表示法

除了存储数据元素，还存储其双亲、所有孩子的存储位置下标，如下图（c）所示。

其实就是在孩子表示法的基础上增加了一个双亲域，其他的都和孩子表示法相同，是双亲表示法和孩子表示法的结合体。

[三种表示法的优缺点]

①双亲表示法只记录了每个节点的双亲，无法直接得到该节点的孩子；

②孩子表示法可以得到该节点的孩子，但是由于不知道每个节点到底有多少个孩子，因此只能按照树的度（树中节点的最大度）分配孩子空间，这样做可能会浪费很多空间；

③双亲孩子表示法是在孩子表示法的基础上增加了一个双亲域，可以快速得到节点的双亲和孩子，缺点和孩子表示法一样，可能浪费很多空间。

【链式存储】

由于树中每个节点的孩子数量无法确定，因此在使用链式存储时，孩子指针域不确定分配多少个合适。

如果采用“异构型”数据结构，将每个节点的指针域个数都按照节点的孩子数分配，则数据结构描述困难；如果采用每个节点都分配固定个数的指针域（例如树的度），则浪费很多空间。

可以考虑通过两种方法存储：

• 一种采用邻接表的思路，将节点的所有孩子都存储在一个单链表中，称之为孩子链表表示法；
• 另一种采用二叉链表的思路，左指针存储第1个孩子，右指针存储右兄弟，称之为孩子兄弟表示法

① 孩子链表示法

孩子链表表示法类似于邻接表，表头包含数据元素和指向第1个孩子指针，将所有孩子都放入一个单链表中。

在表头中，data存储数据元素，first为指向第1个孩子的指针。

单链表中的节点记录该节点的下标和下一个节点的地址。上图中的树，其孩子链表表示法如下图所示。

A有3个孩子B、C、D，而B、C、D的存储位置下标为1、2、3，因此将1、2、3放入单链表中，链接在A的first指针域。同样，B有2个孩子E、F，而E、F的存储位置下标为4、5，因此，将4、5放入单链表中，链接在B的first指针域。同理，其他节点也这样存储。

在孩子链表表示法的基础上，如果在表头中再增加一个双亲域parent，则为双亲孩子链表表示法。

② 孩子兄弟表示法

在孩子链表表示法的基础上，如果在表头中再增加一个双亲域parent，则为双亲孩子链表表示法。

下面左图中的树，其孩子兄弟表示法如下面右图所示。

• A有3个孩子B、C、D，其长子（第1个孩子）B作为A的左孩子，B的右指针存储其右兄弟C，C的右指针存储其右兄弟D。
• B有两个孩子E、F，其长子E作为B的左孩子，E的右指针存储其右兄弟F。
• C有1个孩子G，其长子G作为C的左孩子。
• D有两个孩子H、I，其长子H作为D的左孩子，H的右指针存储其右兄弟I。
• G有1个孩子J，其长子J作为G的左孩子。

孩子兄弟表示法：将长子作为左孩子，将兄弟关系向右斜。