树转化为二叉树、森林转化为二叉树、二叉树转化为树、二叉树转化为森林

Myth丶恋晨 2021-12-13 13:15 288阅读 0赞

一、将树转换为二叉树：  
树中每个结点最多只有一个最左边的孩子(长子)和一个右邻的兄弟。按照这种关系很自然地就能将树转换成相应的二叉树：  
1.在所有兄弟结点之间加一连线  
2.对每个结点，除了保留与其长子的连线外，去掉该结点与其它孩子的连线。  
如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MjEzNjM0_size_16_color_FFFFFF_t_70]  
二、将一个森林转换为二叉树：  
具体方法是：1.将森林中的每棵树变为二叉树；  
2.因为转换所得的二叉树的根结点的右子树均为空，故可将各二叉树的根结点视为兄弟从左至右连在一起，就形成了一棵二叉树。  
如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MjEzNjM0_size_16_color_FFFFFF_t_70 1]  
三、二叉树转换为树：  
是树转换为二叉树的逆过程。  
1.加线。若某结点X的左孩子结点存在，则将这个左孩子的右孩子结点、右孩子的右孩子结点、右孩子的右孩子的右孩子结点…，都作为结点X的孩子。将结点X与这些右孩子结点用线连接起来。  
2.去线。删除原二叉树中所有结点与其右孩子结点的连线。  
如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MjEzNjM0_size_16_color_FFFFFF_t_70 2]  
四、二叉树转换为森林：  
假如一棵二叉树的根节点有右孩子，则这棵二叉树能够转换为森林，否则将转换为一棵树。  
1.从根节点开始，若右孩子存在，则把与右孩子结点的连线删除。再查看分离后的二叉树，若其根节点的右孩子存在，则连线删除…。直到所有这些根节点与右孩子的连线都删除为止。  
2.将每棵分离后的二叉树转换为树。  
如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MjEzNjM0_size_16_color_FFFFFF_t_70 3]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MjEzNjM0_size_16_color_FFFFFF_t_70]: /images/20211213/b930eb27396a421cacb277731e7c4f9f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MjEzNjM0_size_16_color_FFFFFF_t_70 1]: /images/20211213/2359fe18e0644d839d87c969dccd014e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MjEzNjM0_size_16_color_FFFFFF_t_70 2]: /images/20211213/e8d03a72ccbb4dec882c74249ad1ba48.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MjEzNjM0_size_16_color_FFFFFF_t_70 3]: /images/20211213/34a4bc9cc0044bb4943110c35f76e190.png