二叉树的转换

6.4　二叉树的转换

如果对树或森林采用链表存储并设定一定的规则,就可以用二叉树结构表示树和森林。这样,对树的操作实现就可以借助二叉树存储,利用二叉树上的操作来实现。本节将讨论树和森林与二叉树之间的转换方法。

6.4.1　树的存储结构

在实际应用中,很多事物是不能直接用二叉树来描述的,而只能用树和森林来表示。

1.双亲表示法

双亲表示法是用一组连续的空间来存储树上的结点,同时在每个结点上附加一个指示器来指明其双亲结点所在的位置。图6－19所示是一棵树及其双亲表示法的示意图。其类型定义如下。

图6－19　树及其双亲表示法示意图

在这种表中,每个结点（除根结点外）有且仅有一个双亲结点,通过parent域很容易查找到任何结点的双亲。但是,在查找孩子结点时则需要遍历整个表。为了使查找孩子结点更方便些,可以采取下面的存储结构。

2.孩子链表表示法

孩子链表表示法也是用一组连续的空间来存储树上的结点,同时在每个结点上附加一个指针指向由其孩子结点构成的单链表。图6－20是图6－19中树的孩子链表表示法示意图,其类型定义如下。

图6－20　图6－19中树的孩子链表表示法示意图

图6－21　图6－19中树的孩子双亲表示法示意图

在这种表示法中,找孩子结点比较容易,只要搜索firstchild指针指向的单链表即可。但要找某一结点的双亲结点就比较困难了,需要搜索所有的单链表。为了克服上述两种表示法的弊端,可以将两种表示法综合起来使用。

3.孩子双亲表示法

孩子双亲表示法也是用一组连续的空间来存储树上的结点,同时在每个结点上附加一个指示器来指示其双亲结点的位置,再附加一个指针指向其孩子结点构成的单链表。

图6－21所示是图6－19中树的孩子双亲表示法示意图,其类型定义如下。

在这种表示法中,既能很快地找到每个结点的双亲结点,又能很快地找到每个结点的孩子结点。但这种方法是用空间的代价换来的时间效率,在具体应用中一定要根据不同的情况去选择较为适合的存储结构。

以上三种结构都是用顺序表的形式来表示树和森林,这很难转换成二叉树的存储形式,也就不能用二叉树中理论和结构来描述树和森林。

4.孩子兄弟表示法

孩子兄弟表示法是以二叉链表作为存储结构来表示树和森林的一种结构,其中每个结点的两个指针分别指向其第一个孩子结点和下一个兄弟结点。图6－22所示是图6－19中树的孩子兄弟表示法示意图,其类型定义如下。

图6－22　孩子兄弟表示法示意图

这种结构有利于实现树和森林的各种操作。例如,找某个结点的第i个孩子结点,只要先沿着firstchild指针找到第一个孩子结点,然后再沿着该孩子结点的nextsibling指针走i－1步即可。若每个结点增加一个双亲指针域,则可以很快找到其双亲结点。此外,孩子兄弟链表实质上就是前述的二叉链表,只是解释不同而已,有关二叉树的大部分操作均可在这种结构上实现。因此,孩子兄弟链表也成为树、森林与二叉树之间的桥梁和纽带。

6.4.2　一般树转换为二叉树

1.一般树和二叉树的二叉链表存储结构比较

一般树是无序树,树中结点的各孩子的次序是无关紧要的；二叉树中结点的左、右孩子结点是有区别的。为避免发生混淆,约定树中每一个结点的孩子结点按从左到右的次序排列。如图6－23所示为一棵一般树,根结点A有B、C、D三个孩子,可以认为,结点B为A的长子,结点C为B的次弟,结点D为C的次弟。

图6－23　一般树

图6－24所示为一般树和二叉树的二叉链表存储结构示意图。

图6－24　一般树和二叉树链表存储结构

2.将一般树转换为二叉树的方法

比较图6－24所示的两种存储结构,只要把一般树的长子作为其父结点的左子树,把一般树的次弟作为其兄结点的右子树,即可以把一棵一般树转换为一棵二叉树。

整个转换可以分为如下三步。

（1）连线——链接树中所有相邻的亲兄弟结点之间连线。

（2）删线——保留父结点与长子结点的连线,打断父结点与非长子结点之间的连线。

（3）旋转——以根结点为轴心,将整棵树顺时针旋转一定的角度,使之层次分明。

可以证明,一般树进行如此的转换所构成的二叉树是唯一的。图6－25（a）、（b）、（c）给出了图6－23所示的一般树转换为二叉树的转换过程。

由上面的转换可以得出以下结论。

（1）在转换产生的二叉树中,左分支上的各结点在原来的树中是父子关系,而右分支上的各结点在原来的树中则是兄弟关系。

（2）由于树的根结点无兄弟,所以转换后的二叉树的根结点必定无右子树。

（3）一棵树采用长子、兄弟表示法所建立的存储结构与它所对应的二叉树的二叉链表存储结构是完全相同的。

（4）一般树转换为二叉树以后,将使树的深度增加。如图6－23所示的树深度为4,转换为二叉树以后,其深度就变成7了,如图6－25（c）所示。

6.4.3　森林转换为二叉树

森林是若干棵树的集合。只要将森林中的每一棵树的根视为兄弟,而每一棵树又可以用二叉树表示,这样,森林也就可以用二叉树来表示了。

图6－25　一般树转换为二叉树的转换过程示意图

森林转换为二叉树的方法如下。

（1）将森林中的每一棵树转换成相应的二叉树。

（2）第一棵二叉树保持不动,从第二棵二叉树开始,依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右子树,直到把最后一棵二叉树的根结点作为其前一棵二叉树的右子树为止。

【例6－5】　将图6－26（a）所示的森林转换为二叉树。

图6－26　森林转换为二叉树的过程示意图

6.4.4　二叉树转换为树和森林

树转换为二叉树以后,其根结点必定无右子树；而森林转换为二叉树以后,其根结点有右分支。显然这一转换过程是可逆的,即可以依据二叉树的根结点有无右子树,将一棵二叉树还原为树或森林。

下面以图6－27（a）所示的二叉树为例,说明其转换方法。

（1）若某结点是其父结点的左孩子结点,则把该结点的右孩子结点、右孩子结点的右孩子结点,直到最后一个右孩子结点都与该结点的父结点连起来,如图6－27（b）所示。

（2）删除原二叉树中所有的父结点与右孩子结点的连线,如图6－27（c）所示。

（3）整理（1）、（2）的结果,使之层次分明,显示出树或森林的形状,如图6－27（d）所示。

图6－27所示为一棵二叉树还原为森林的过程的示意图。

图6－27　二叉树还原森林的过程

【例6－6】　将图6－28（a）所示的二叉树转换为树。

图6－28　二叉树转换为树的过程示意图