Java数据结构--树、森林和二叉树

左手的ㄟ右手 2023-10-06 10:41 9阅读 0赞

## `一、树、森林和二叉树之间的转换` ##

> 树或森林与二叉树之间存在一一对应的关系。任何一棵树或一个森林可唯一地对应到一棵二叉树；反之，任何一棵二叉树也能唯一地对应到一个森林或一棵树。

#### 1.1 将树转化为二叉树 ####

> 树中每个结点最多只有一个最左边的孩子（长子）和一个右邻的兄弟。按照这种关系很自然地就能将树转换成相应的二叉树，具体步骤是：  
> 1）在所有兄弟结点之间加一连线；  
> 2）对每个结点，除了保留与其长子的连线外，去掉该结点与其他孩子的连线。  
> 示例：将`图2.1`所示的树转换为二叉树。

> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70]

> 根据树转二叉树的规则：第一步，加线；第二步：抹线；第三步：旋转。具体过程如`图2.2`所示。

> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70 1]

> 注意：由于树根没有兄弟，故树转化为二叉树后，二叉树的根结点的右子树必为空。

#### 1.2 将一个森林转换为二叉树 ####

> 具体方法：  
> 1）将森林中的每棵树变为二叉树；  
> 2）因为转换所得的二叉树的根结点的右树均为空，故将各二叉树的根结点视为兄弟从左至右连在一起，就形成了一棵二叉树。

> 示例：将如`图2.3`所示的森林转化为二叉树  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70 2]

#### 1.3 二叉树到树、森林的转换 ####

> 把二叉树转换成树和森林的方式是：若结点x是双亲y的左孩子。则把x的右孩子。右孩子的右孩子，…，都与y用连线连起来，最后去掉所有双亲到右孩子的连线。

> 示例：将`图2.4`所示的二叉树转换为树。  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70 3]

## `二、树、森林的遍历` ##

#### 2.1 树的遍历 ####

> 树的遍历通常有先根遍历和后根遍历两种方式。  
> 1）先根遍历  
> 先根遍历的定义为：  
> 1、访问根结点；  
> 2、按照从左到右的顺序先根遍历根结点的每一棵子树。  
> 2）后根遍历  
> 后根遍历的定义为：  
> 1、按照从左到右的顺序后根遍历根结点的每一棵子树；  
> 2、访问根结点。

> 示例：  
> 先根和后根遍历如`图2.1（a）`所示的树，及先根和中根遍历`图2.1（b）`所示的二叉树。  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70 4]

> 根据树的遍历规则，如`图2.1（a）`所示的树的先根遍历结果是：A，B，C，D，E，F，I，J，D，H；后根遍历结果是：E，C，I，F，J，B，D，H，A。  
> 根据二叉树的遍历规则：`图2.1（a）`所示的二叉树的先根遍历结果是：A，B，C，E，F，I，J，D，H；中根遍历结果是：E，C，I，F，J，B，D，H，A。  
> `图`2.1（b）`所示的二叉树其实是`图2.1（a）\`所示的树转换而来的，又示例的遍历结果可知：  
> 1）前序遍历一棵树恰好等价于前序遍历该树对应的二叉树。  
> 2）后序遍历树恰好等价于中序遍历该树对应的二叉树。

#### 2.2 森林的遍历 ####

> 森林的遍历右前序遍历和后序遍历两种方式。  
> 1）前序遍历  
> 前序遍历的定义为：  
> 1、访问森林中第一棵树的根结点；  
> 2、前序遍历第一棵树的根结点的子树；  
> 3、前序遍历去掉第一棵树后的子森林。  
> 2）后序遍历  
> 后序遍历的定义为：  
> 1、后序遍历第一棵树的根结点的子树；  
> 2、访问森林中第一棵树的根结点；  
> 3、后序遍历去掉第一棵树后的子森林。

> 示例：  
> 先根和后根遍历如`图2.2（a）`所示的森林，及先根和中根遍历`图2.2（b）`所示的二叉树。  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70 5]

> 根据森林的遍历规则，`图2.2（a）`所示的树的先根遍历结果是：A，B，C，D，E，F，G，H，I，J，K，L；后根遍历的结果是：B，A，C，F，G，E，D，J，K，I，L，H。  
> 根据二叉树的遍历规则，`图2.2（b）`所示的二叉树的先根遍历结果是：A，B，C，D，E，F，G，H，I，J，K，L；中根遍历结果是：B，A，C，F，G，E，D，J，K，L，H。  
> `图2.2（b）`所示的二叉树其实是`图2.2（a）`所示的森林转换而来的，由示例的遍历结果可推知：  
> 1、前序遍历一个森林恰好等价于前序遍历该森林对应的二叉树。  
> 2、后序遍历森林恰好等价于中序遍历该森林对应的二叉树。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200711224325157.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200711225626672.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200711230733713.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200711232108921.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200711232427167.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/202007112327059.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx,size_16,color_FFFFFF,t_70