数据结构：树和森林

在前面，我们讨论了树的基本概念以及二叉树的遍历，今天我们来看另一个知识点：树和森林。

一、树的存储结构

树的存储结构有很多种形式。其中，常用的表示方法有3种：双亲表示法、孩子表示法和孩子兄弟表示法。下面分别介绍。

1.1、双亲表示法

双亲表示法，是指结点中增设了指示其双亲结点的指针域。该方法以一组连续的存储单元存放树中结点。每个结点除了数据域data之外，还附设一个parent域用以指示其双亲结点的位置，其结点形式如下图所示：

这种存储结构利用了每个结点（除根以外）只有唯一双亲的性质。在这种存储结构下，求结点的双亲十分方便，也很容易求树的根，但求结点的孩子时需要遍历整个结构。如下图，是一棵树及其双亲表示法的存储结构：

1.2、孩子表示法

孩子表示法，是指结点中增设了指示其孩子结点的指针域。树中每个结点可能有多棵子树，因此可用多重链表，即每个结点有多个指针域，每个指针指向一棵子树的根结点。此时，链表中的结点可以有如下两种形式：

在第一种结点形式中，多重链表中的结点是同构的，其中d为树的度。由于树中很多结点的度小于d，所以链表中有很多空链域，空间较浪费。不难推出，在一棵有n个结点、度为k的树中必有n(k−1)+1个空链域。

在第二种结点形式中，多重链表中的结点不是同构的，其中d为结点的度，degree域的值同d。此时，虽能节约存储空间，但操作不方便。

除了上述形式外，还有另一种形式，把每个结点的孩子结点排列起来，看成一个线性表，且以单链表作为存储结构。这样，在一棵有n个结点的树中，就有n个孩子链表。为了便于查找，可将树中各结点的孩子链表的头指针存放在一个指针数组中。

与双亲表示法相反，孩子表示法便于那些涉及孩子的操作的实现。如下图，是一棵树及其孩子表示法的存储结构：

此外，还可以把孩子表示法和双亲表示法结合起来，即将双亲表示和孩子链表合在一起。如下图，是一棵树及其带双亲的孩子链表存储结构：

1.3、孩子兄弟表示法

孩子兄弟表示法，是指结点中增设了指示其孩子结点和兄弟结点的指针域。孩子兄弟表示法又称二叉树表示法，或二叉链表表示法，即以二叉链表作为树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点，分别命名为firstchild域和nextsibling域，其结点形式如下：

在C语言中，树的孩子兄弟表示法的类型描述如下：

typedef struct CSNode {
    ElemType data;
    struct CSNode *firstchild, *nextsibling;
}CSNode, *CSTree;

利用这种存储结构便于实现树的各种操作。首先易于实现找结点孩子等的操作。例如，若要访问结点x的第i个孩子，则只要先从firstchild域找到第1个孩子结点，然后沿着孩子结点的nextsibling域连续走i−1步，便可找到x的第i个孩子。当然，如果为每个结点增设一个parent域，则同样能方便地实现查找双亲的操作。

这种存储结构的优点是，它和二叉树的二叉链表完全一样，便于将一般的树结构转换为二叉树进行处理，利用二叉树的算法来实现对树的操作。因此孩子兄弟表示法是应用较为普遍的一种树的存储表示方法。如下图，是一棵树及其二叉链表存储结构：

二、森林与二叉树的转换

从树的二叉链表表示法可知，任何一棵和树对应的二叉树，其根结点的右子树必为空。若把森林中第二棵树的根结点，看成是第一棵树的根结点的兄弟，则可导出森林和二叉树的对应关系。如下图，是森林与二叉树的对应关系：

2.1、森林转换成二叉树

如果 $F=\{T_1,T_2,...,T_m\}$ 是森林，则可按如下规则将其转换成一棵二叉树 $B=(root, LB, RB)$ ：

若F为空，即 $m=0$ ，则B为空树；
若F非空，即 $m\neq0$ ，则B的根root是森林中第一棵树的根ROOT( $T_1$ )；B的左子树LB是 $T_1$ 中根节点的子树森林 $F_1=\{T_{11},T_{12},...,T_{1m}\}$ 转换而成的二叉树；B的右子树RB是森林 $F'=\{T_2,T_3,...,T_m\}$ 转换而成的二叉树。

2.2、二叉树转换成森林

如果 $B=(root, LB, RB)$ 是一棵二叉树，则可按如下规则将其转换成森林 $F=\{T_1,T_2,...,T_m\}$ ：

若B为空，则F为空；
若B非空，则F中第一棵树 $T_1$ 的根ROOT( $T_1$ )是二叉树B的根root； $T_1$ 中根结点的子树森林 $F_1$ 是由B的左子树LB转换而成的森林；F中除 $T_1$ 之外其余树组成的森林 $F'=\{T_2,T_3,...,T_m\}$ 是由B的右子树RB转换而成的森林。