考研专业课之统考计算机蓝宝书(25)

来源：跨考网 2009-01-07 21:16

3.3.2 树、森林与二叉树的转换

1. 树转换为二叉树

将一棵树转换为二叉树的方法是：
(1). 树中所有相邻兄弟之间加一条连线。
(2). 对树中的每个结点，只保留它与第一个孩子结点之间的连线，删去它与
其它孩子结点之间的连线。
(3). 以树的根结点为轴心，将整棵树顺时针转动一定的角度，使之结构层次
分明。可以证明，树作这样的转换所构成的二叉树是唯一的。由上面的转换可以看出，在二叉树中，左分支上的各结点在原来的树中是父子关系，而右分支上的各结点在原来的树中是兄弟关系。由于树的根结点没有兄弟，所以变换后的二叉树的根结点的右孩子必为空。事实上，一棵树采用孩子兄弟表示法所建立的存储结构与它所对应的二叉树的二叉链表存储结构是完全相同的。

订阅收藏考研专业课之统考计算机蓝宝书

2. 森林转换为二叉树

由森林的概念可知，森林是若干棵树的集合，只要将森林中各棵树的根视为兄弟，每棵树又可以用二叉树表示，这样，森林也同样可以用二叉树表示。
森林转换为二叉树的方法如下：
(1). 将森林中的每棵树转换成相应的二叉树。
(2). 第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结
点作为前一棵二叉树根结点的右孩子，当所有二叉树连起来后，此时所得到的二叉树就是由森林转换得到的二叉树。

这一方法可形式化描述为：
如果F＝{ T1，T2，...，Tm }是森林，则可按如下规则转换成一棵二叉树B＝（root，LB，RB）。
(1). 若F为空，即m＝0，则B为空树；
(2). 若F非空，即m≠0，则B的根root即为森林中第一棵树的根Root(T1)；
B的左子树LB是从T1中根结点的子树森林F1＝{ T11，T12，...，T1m1 }转换而成的二叉树；其右子树RB是从森林F'＝{ T2，T3，...，Tm }转换而成的二叉树。

3. 二叉树转换为树和森林

树和森林都可以转换为二叉树，二者不同的是树转换成的二叉树，其根结点无右分支，而森林转换后的二叉树，其根结点有右分支。显然这一转换过程是可逆的，即可以依据二叉树的根结点有无右分支，将一棵二叉树还原为树或森林，具体方法如下：
(1). 若某结点是其双亲的左孩子，则把该结点的右孩子、右孩子的右孩子......
都与该结点的双亲结点用线连起来；
(2). 删去原二叉树中所有的双亲结点与右孩子结点的连线；
(3). 整理由（1）、（2）两步所得到的树或森林，使之结构层次分明。

这一方法可形式化描述为：
如果B＝（root，LB，RB）是一棵二叉树，则可按如下规则转换成森林F＝{ T1，T2，...，Tm }。
(1). 若B为空，则F为空；
(2). 若B非空，则森林中第一棵树T1的根ROOT（T1）即为B的根root；
T1中根结点的子树森林F1是由B的左子树LB转换而成的森林；F中除T1之外其余树组成的森林F'＝{ T2，T3，...，Tm }是由B的右子树RB转换而成的森林。