树、森林与二叉树的转换

不念不忘少年蓝@ 2021-09-15 01:00 365阅读 0赞

树或森林与二叉树之间有一个自然的一一对应关系。任何一个森林或一棵树可惟一地对应到一棵二叉树；反之，任何一棵二叉树也能惟一地对应到一个森林或一棵树。  
   
 1．树、森林到二叉树的转换  
（1）将树转换为二叉树  
    　树中每个结点最多只有一个最左边的孩子(长子)和一个右邻的兄弟。按照这种关系很自然地就能将树转换成相应的二叉树：  
　　①在所有兄弟结点之间加一连线；  
　　②对每个结点，除了保留与其长子的连线外，去掉该结点与其它孩子的连线。  
【例1】下面(a)图所示的树可转换为(c)图所示的二叉树。

![Image 1][]

**具体转换过程可【[参见动画演示][Link 1]】**

注意：  
　    由于树根没有兄弟，故树转化为二叉树后，二叉树的根结点的右子树必为空。  
  
（2）将一个森林转换为二叉树  
 具体方法是：  
　　① 将森林中的每棵树变为二叉树  
　　② 因为转换所得的二叉树的根结点的右子树均为空，故可将各二叉树的根结点视为兄弟从左至右连在一起，就形成了一棵二叉树。  
【例2】下图中，左边包含三棵树的森林可转换为右边的二叉树。

![Image 1][]

#####       ** ****具体转换过程可【[参见动画演示][Link 1]****】**  #####

2.二叉树到树、森林的转换  
　    把二叉树转换到树和森林自然的方式是：若结点x是双亲y的左孩子，则把x的右孩子，右孩子的右孩子，…，都与y用连线连起来，最后去掉所有双亲到右孩子的连线。  
【例3】下图的森林就是由例2中二叉树转换成的。

![Image 1][]

** ****具体转换过程可【[参见动画演示][Link 1]】**

转自：[http://student.zjzk.cn/course\_ware/data\_structure/web/shu/shu6.5.1.htm][http_student.zjzk.cn_course_ware_data_structure_web_shu_shu6.5.1.htm]

[Image 1]: 
[Link 1]: http://student.zjzk.cn/course_ware/data_structure/web/flashhtml/zhuanhuan.htm
[http_student.zjzk.cn_course_ware_data_structure_web_shu_shu6.5.1.htm]: http://student.zjzk.cn/course_ware/data_structure/web/shu/shu6.5.1.htm