树、森林和二叉树的转换

Love The Way You Lie 2023-02-15 01:18 6阅读 0赞

1.  ## 树转化为二叉树 ##
    
    （1）加线：在兄弟结点之间加一条连线  
    （2）去线：树中的每个结点，只保留它第一个孩子结点的连线，删除与其他孩子之间的连线。  
    （3）层次调整：以树的根节点为轴心，将整棵树顺时针旋转一定角度，使其结构层次分明。（第一个孩子结点变为左孩子，兄弟结点变右孩子）  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmJlaTE_size_16_color_FFFFFF_t_70]
2.  ## 森林转化为二叉树 ##
    
    （1）把每一棵树转化为二叉树  
    （2）第一棵二叉树不动。从第二棵二叉树开始，把后一棵二叉树的根结点作为前一个二叉树的右孩子，用线连起来。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmJlaTE_size_16_color_FFFFFF_t_70 1]
3.  ## 二叉树转化为树 ##

（1）加线：若某结点X的左孩子结点存在，则将这个左孩子结点的右结点、右孩子的右孩子结点、右孩子的右孩子的右孩子结点…，都作为结点X的结点，用线将结点X与这些右孩子用线连接起来。  
（2）去线：删除原有的孩子结点的右结点的连线。  
（3）层次调整。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmJlaTE_size_16_color_FFFFFF_t_70 2]  
4. \#\# 二叉树转化为森林  
如果一棵二叉树的根结点有右孩子，则这棵二叉树能转换为森林，否则转换为一棵树。  
（1）从根结点开始，右孩子存在，则把与右孩子结点的连线删除。再查看分离后的二叉树。若其根结点的右孩子存在，则连线删除，直到所有的根结点与右孩子的连线都删除为止。  
（2）将每一棵分离后的二叉树转换为树。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmJlaTE_size_16_color_FFFFFF_t_70 3]  
出自《大话数据结构》

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmJlaTE_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200604084558578.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmJlaTE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmJlaTE_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200604084800738.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmJlaTE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmJlaTE_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200604085506692.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmJlaTE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmJlaTE_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200604085857529.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmJlaTE=,size_16,color_FFFFFF,t_70