树的存储及转换

 

树的存贮结构有多种表示方法，比较典型的乃是顺序结构和链表结构两类。

顺序存贮结构即向量，一般将树结点按自上而下，自左至右的顺序一一存放。如前文所介绍的完全二叉树就可以采用顺序存贮结构。

1.双亲链表表示法

    顺序存储结构常用的有双亲表示法，这种方法在每个数组元素中存放某个结点信息和该结点的双亲下标值。

（1）双亲链表表示法的实现

 方法① 用动态链表实现

 方法② 用向量表示——更为方便

2.多重链表的孩子表示法

（1） 结点结构

① 定长结点

    即树中每个结点均按树的度k来设置指针。

    n个结点的树一共有n*k个指针域，而树中只有n-1条边，故树中的空指针数目为

     kn-(n-1)=n(k-1)+1（k越大，浪费的空间越多）。

②不定长结点

    即树中每个结点按本结点的度来设置指针数，并在结点中增设一个度数域degree指出该结点包含的指针数。

    各结点不等长，虽然节省了空间，但是给运算带来不便。

（2）孩子链表表示法

    孩子链表表示法是为树中每个结点设置一个孩子链表，并将这些结点及相应的孩子链表的头指针存放在一个向量中。

3.孩子兄弟链表表示法

（1）表示方法

    树最常用的是孩子 - 兄弟二叉链表表示法，这种方法表示规范，不仅适用于多叉树的存储，也适用于森林的存储。构成孩子 - 兄弟二叉链表的结点结构是：一个数据域和两个指针域，一个指针指向它的长子，另一指针指向它的一个兄弟。

4．树、森林到二叉树的转换

（1）将树转换为二叉树

    树中每个结点最多只有一个最左边的孩子(长子)和一个右邻的兄弟。按照这种关系很自然地就能将树转换成相应的二叉树。

　  将一般树转化为二叉树的思路，主要根据树的孩子 - 兄弟存储方式而来，步骤是：

(1) 加线：在各兄弟结点之间用虚线相链。可理解为每个结点的兄弟指针指向它的一个兄弟。

(2) 抹线：对每个结点仅保留它与其最左一个孩子的连线，抹去该结点与其它孩子之间的连线。可理解为每个结点仅有一个孩子指针，让它指向自己的长子。

(3) 旋转：把虚线改为实线从水平方向向下旋转 45 ℃ ，成右斜下方向。原树中实线成左斜下方向。这样就树的形状成呈现出一棵二叉树。

（2）将一个森林转换为二叉树

森林是树的有限集合，由上节可知，一棵树可以转换为二叉树（没有右子树），一个森林就可以转换为二叉树（没有右子树）的森林。 将森林转换为二叉树的一般步骤为：

（１）将森林中每棵子树转换成相应的二叉树。形成有若干二叉树的森林。

（２）按森林图形中树的先后次序，依次将后边一棵二叉树作为前边一棵二叉树根结点的右子树，这样整个森林就生成了一棵二叉树，实际上第一棵树的根结点便是生成后的二叉树的根结点。

5.二叉树到树、森林的转换

　  二叉树转换为一般树，此时的二叉树必须是由某一树（一般树）转换而来的没有右子树的二叉树。并非随便一棵二叉树都能还原成一般树。

其还原过程也分为三步：

（１）加线：若某结点 i 是双亲结点的左孩子，则将该结点 i 的右孩子以及当且仅当连续地沿着右孩子的右链不断搜索到所有右孩子，都分别与结点 i 的双亲结点用虚线连接。

（２）抹线：把原二叉树中所有双亲结点与其右孩子的连线抹去。这里的右孩子实质上是原一般树中结点的兄弟，抹去的连线是兄弟间的关系。

（３）进行整理：把虚线改为实线，把结点按层次排列。

6．森林的两种遍历方法

（1）前序遍历森林

    若森林非空，则：

①访问森林中第一棵树的根结点；

②前序遍历第一棵树中根结点的各子树所构成的森林

③前序遍历除第一棵树外其它树构成的森林。

（2）后序遍历森林

若森林非空，则:

①后序遍历森林中第一棵树的根结点的各子树所构成的森林；

②访问第一棵树的根结点；

③后序遍历除第一棵树外其它树构成的森林。

  注意：

    ① 前序遍历森林等同于前序遍历该森林对应的二叉树

    ② 后序遍历森林等同于中序遍历该森林对应的二叉树