树的存储结构

  • 双亲表示法
  • 孩子表示法
  • 孩子兄弟表示法

双亲表示法

用一组联系的存储单元存储树的结点，每个结点包含数据域 data 用于存储数据和双亲域 parent 用于指向其双亲（父节点）。

data parent

原理：利用了每个结点只有唯一一个双亲（父节点）的性质。

孩子表示法

树中每个结点有多棵子树，每个结点包含一个数据域 data 和多个指针域 $child_n$。

data $child_1$ $child_2$ $child_3$ … $child_d$

d表示树的度。
缺点：很多的结点度都是小于 d 的，所以有很多的空链域，即在一棵 n 个结点度为 k 的树中必有 n(k-1)+1 个空链域。

孩子兄弟表示法

也称为二叉链表表示法，树中的每一个结点包含一个数据域 data 和两个指针域 firstchild 指向第一个孩子和 nextsibling 指向下一兄弟。

firstchild data nextsibling 
1
2
3
4
typedef struct CSNode {
    Elemtype data;
    struct CSNode *fiestchild, *nextsibling;
}CSNode, *CSTree；

森林与二叉树的转换

任何一棵和树对应的二叉树，其根结点的右子树必定是空。
把森林中第二棵树的根结点看成是第一棵树的根结点的兄弟，就可以推导出森林与二叉树的对应关系。

  • 森林转换成二叉树
    $F$ = { $T_1$, $T_2$, …$T_m$ }是森林，将其转化成一棵二叉树 $B$ = ( $root$, $LB$, $RB$ )。
    1. 若 $F$ 为空，即 $m = 0$，则 $B$ 为空树。
    2. 若 $F$ 非空，即 $m \neq 0$,则 $B$ 的根 $root$ 即为森林中第一棵树的根 $ROOT$($T_1$); $B$ 的左子树 $LB$ 是从 $T_1$ 中根结点的子树森林 $F_1$ = {$T_{11}$, $T_{12}$, … ,$T_{1m}$}转换而成的二叉树；其右子树 $RB$ 是从森林 $F’$ = { $T_2$, $T_3$, …, $T_m$}转换而成的二叉树。
  • 二叉树转换成森林
    $B$ = ( $root$, $LB$, $RB$ )一棵二叉树，将其转化成森林 $F$ = { $T_1$, $T_2$, …$T_m$ }
    1. 若 $B$ 为空，则 $F$ 为空。
    2. 若 $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$ 转换而成的森林。

无论是森林转二叉树，还是二叉树转森林，其核心都是递归思想。