【数据结构】树：非二叉树（普通树）与森林的遍历

比眉伴天荒 2021-12-04 00:55 364阅读 0赞

\#笔记整理

**树的定义参照前文：**  
[二叉树、遍历二叉树与线索二叉树等树的定义与解析、二叉树遍历实现][Link 1]

## 非二叉树与森林的遍历 ##

#### 树的遍历（两种） ####

**1） 先根遍历**  
若树非空，则遍历方法为：  
①访问根结点。  
②从左到右， 依次先根遍历根结点的每一棵子树。  
等同于转换的二叉树进行先序遍历  
![在这里插入图片描述][20190719121644284.png]  
**2）后根遍历**  
若树非空， 则遍历方法为：  
①从左到右， 依次后根遍历根结点的每一棵子树。  
②访问根结点。  
等同于转换的二叉树进行中序遍历。  
![在这里插入图片描述][20190719121707859.png]

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

#### 森林的遍历（2种） ####

**1） 先序遍历**  
若森林非空， 则遍历方法为：  
①访问森林中第一棵树的根结点。  
②先序遍历第一棵树的根结点的子树森林。  
③先序遍历除去第一棵树之后剩余的树构成的森林。  
等同于转换的二叉树进行先序遍历  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 1]

**2） 中序遍历**  
若森林非空， 则遍历方法为：  
①中序遍历森林中第一棵树的根结点的子树森林。  
②访问第一棵树的根结点。  
③中序遍历除去第一棵树之后剩余的树构成的森林。  
等同于转换的二叉树进行中序遍历  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 2]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 3]

### 由遍历确定树和森林 ###

①给定树的先根遍历序列和后根遍历序列可唯一画出一棵树。  
②给定森林的先序遍历序列和中序遍历序列可唯一确定一森林。

### 由遍历确定二叉树 ###

①任何n(n≥0)个不同结点的二叉树,都可由它的中序序列和先序序列唯一地确定。  
②任何n(n＞0)个不同结点的二叉树,都可由它的中序序列和后序序列唯一地确定。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 5]

#### 森林转换为二叉树 ####

森林也可以方便地用孩子兄弟链表表示。森林转换为二叉树的方法如下：  
（1）将森林中的每棵树转换成相应的二叉树。  
（2）第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子， 当所有二叉树连在一起后，所得到的二叉树就是由森林转换得到的二叉树。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 6]

#### 二叉树还原为树或森林 ####

将一棵二叉树还原为树或森林，具体方法如下：  
（1） 若某结点是其双亲的左孩子，则把该结点的右孩子、 右孩子的右孩子……都与该结点的双亲结点用线连起来。  
（2） 删掉原二叉树中所有双亲结点与右孩子结点的连线。  
（3） 整理由（1）、（2）两步所得到的树或森林， 使之结构层次分明。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 7]  
  
  
  
  
  
部分内容来源：

1.  《数据结构（C语言版）》----严蔚敏
2.  《数据结构》课堂教学ppt ---- 刘立芳
3.  《数据结构算法与解析（STL版）》 ---- 高一凡

[Link 1]: https://blog.csdn.net/yohjob/article/details/95644144
[20190719121644284.png]: /images/20211203/0d1f13ad43354c969c3e37474670fc3a.png
[20190719121707859.png]: /images/20211203/30c218fc6e5748d39df47312b1c08cbd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70]: /images/20211203/f889fbe4b021426a98415def36192759.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 1]: /images/20211203/f12089a043b74f2597d70ee80374d03c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 2]: /images/20211203/c6b91b1b92cd4c9992585f7e608a87a1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 3]: /images/20211203/57a40548807147bbb73f22bdabdee1a7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 4]: /images/20211203/f4ab1bc661794e0aae3b41acb04748da.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 5]: /images/20211203/a7f338420e054f49be0eb869eaf1313a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 6]: /images/20211203/9e9ca6d5825f45918b0903536db24034.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 7]: /images/20211203/efca52a471e247c3998fbc46e4703db1.png