5.8 二叉树、树以及森林之间的转换

5.8  二叉树、树以及森林之间的转换

由于二叉树和树都可用二叉链表作为存储结构，则以二叉链表作为媒介可导出树与二叉树之间的一个对应关系。也就是说，给定一棵树，可以找到唯一的一棵二叉树与之对应，从物理结构来看，它们的二叉链表是相同的，只是解释不同而已。

从树的二叉链表表示的定义可知，任何一棵和树对应的二叉树，其右子树必空。若把森林中第二棵树的根节点看成是第一棵树的根节点的兄弟，则同样可导出森林和二叉树的对应关系。

5.8.1  树和森林转换为二叉树

前面讨论了二叉树的存储结构和运算，那么如何实现一般树的运算呢？由于一般树的子树个数不定，如果采用类似二叉链的存储结构，其节点的指针域个数必须采用最多子树的个数，这样会浪费很多空间。为此，将一般树转换成二叉树，采用二叉树的存储结构和运算，在处理之后再将该二叉树转换成一般树。下面讨论一般树和森林与二叉树之间的转换方法。

1．树转换成二叉树

将一棵树转换成二叉树的过程如下：

（1）将树中所有相邻兄弟之间加一条连线。

（2）对树中的每个节点，只保留它与第一个孩子节点之间的连线，删除它与其他孩子节点之间的连线。

（3）以树的根节点为轴心，将整棵树顺时针转动45°，使之结构层次分明。

【例5-3】将图5-27（a）所示的树转换成二叉树。

解：转换的过程如图5-27（b）～（d）所示。

2．森林转换为二叉树

将森林转换为二叉树的过程如下：

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

（2）第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根节点作为前一棵二叉树根节点的右孩子节点，当所有二叉树连在一起后，此时所得到的二叉树就是由森林转换得到的二叉树。

【例5-4】将图5-28（a）所示的森林转换成二叉树。

解：转换的过程如图5-28（b）～（e）所示。

图5-27  一棵树转换成二叉树的过程

图5-28  森林转换成二叉树的过程

5.8.2  二叉树还原为树或森林

二叉树还原为树或森林的过程如下：

（1）若某节点是其双亲的左孩子，则将该节点的右孩子、右孩子的右孩子……都与该节点的双亲节点用连线连起来。

（2）删除原二叉树中所有双亲节点与右孩子节点的连线。

（3）整理由（1）、（2）两步所得到的树或森林，使之结构层次分明。

【例5-5】将图5-29（a）所示的一棵二叉树还原为树。

解：转换的过程如图5-29（b）～（d）所示。

图5-29  二叉树还原为树的过程