《数据结构》—— 由遍历序列构造唯一二叉树

我就是我 2022-09-14 00:19 137阅读 0赞

### 遍历序列构造唯一二叉树 ###

*   *  一、一种遍历确定二叉树？
     *  二、两种遍历确定二叉树？
     *   *  2.1 先序 + 中序遍历序列
         *  2.2 后序 + 中序遍历序列
         *  2.3 层序 + 中序遍历序列

## 一、一种遍历确定二叉树？ ##

**通过先、中、后序遍历的序列，确定唯一的二叉树。**

例如：BDCAE的的中序遍历：中序遍历左子树、根结点、中序遍历右子树。可以画出不同的树。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_20_color_FFFFFF_t_70_g_se_x_16]  
BDCAE的前序遍历，画出不同的树。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
BDCAE的后序遍历：前序遍历左子树、前序遍历右子树、根结点。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
层序遍历序列也是同理。

**所以结论：** 若只给出一棵二叉树的 先、中、后、层 序遍历序列中的一种，不能唯一确定一棵二叉树。

--------------------

## 二、两种遍历确定二叉树？ ##

### 2.1 先序 + 中序遍历序列 ###

先序遍历可以推出根节点，中序序列确定左右子树。

**例如：**  
前序遍历序列：A D B C E  
中序遍历序列：B D C A E  
**【分析】：A为根节点，(BDC)为左子树，(E)为右子树；**

**然后还剩下：(BDC)序列：**  
前序遍历序列：D B C  
中序遍历序列：B D C  
**【分析】：D为根节点，B为左子树，C为右子树。**  
![在这里插入图片描述][541d7bd2710041e8831cc3e5e2914198.png]  
最后验证一下二叉树的先序与中序是否跟原条件一样。

--------------------

**例如：**  
先序遍历序列：D A E F B C H G I  
中序遍历序列：E A F D H C B G I  
根节点为D，左子树(E A F)，右子树(H C B G I) ；

**1、对左子树(E A F)：**  
先序遍历序列：A E F  
中序遍历序列：E A F  
根节点A，左E，右F；  
![在这里插入图片描述][140e293143fc4d41b33c330c1f5114a9.png]

**2、对右子树(H C B G I)：**  
先序遍历序列：B C H G I  
中序遍历序列：H C B G I  
根节点B，左HC，右GI；  
![在这里插入图片描述][9eb4c63e628943d1800b9f50f72af802.png]  
**3、对HC：**  
先序遍历序列：C H  
中序遍历序列：H C  
根为C，左H；

**4、对GI：**  
先序遍历序列：G I  
中序遍历序列：G I  
根G，右I；

二叉树如下图所示：  
![在这里插入图片描述][783097dc70d2483c83a9185778ed7edc.png]

--------------------

### 2.2 后序 + 中序遍历序列 ###

同理，后序的最后一个是根节点，中序序列确定左右子树。

**例如：**  
后序遍历序列：E F A H C I G B D  
中序遍历序列：E A F D H C B G I  
D为根节点，左(E A F)，右( H C B G I)

**1、对左子树(E A F)：**  
后序遍历序列：E F A  
中序遍历序列：E A F  
根节点A，左E，右F；

**2、对右子树(H C B G I)：**  
后序遍历序列：H C I G B  
中序遍历序列：H C B G I  
根节点B，左HC，右GI；  
![在这里插入图片描述][786140720e4749768f77b928ce92fe7a.png]  
**3、对HC：**  
后序遍历序列：H C  
中序遍历序列：H C  
根为C，左H；

**4、对GI：**  
后序遍历序列：I G  
中序遍历序列：G I  
根G，右I；

![在这里插入图片描述][636d8768a8c940f7abd6b545bc7049e2.png]

--------------------

### 2.3 层序 + 中序遍历序列 ###

层序遍历第一个为根节点，中序序列确定左右子树。

**例如：**  
层序遍历序列：A B C D E  
中序遍历序列：A C B E D  
根结点A，左为空NULL，右为(C B E D)；

**1、右为(C B E D)；**  
层序遍历序列：B C D E  
中序遍历序列：C B E D  
根B，左C，右ED；  
![在这里插入图片描述][53a791d611154db9bf88389b91b18819.png]  
**2、右ED：**  
层序遍历序列：D E  
中序遍历序列：E D  
根为D，左为E。  
![在这里插入图片描述][c2da93c858bc4ed88110d3f34069c88e.png]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/6b5fe6cac8bb45c185b2d6272fa378b9.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/40981550cc0647b48305118c85acc0c1.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/17f74a21d23248839e26ddca6ed7f40b.png
[541d7bd2710041e8831cc3e5e2914198.png]: /images/20220828/850e48318b6b4e00864f1090b14a67e1.png
[140e293143fc4d41b33c330c1f5114a9.png]: /images/20220828/d9474bfba60c431f954067017ea36e19.png
[9eb4c63e628943d1800b9f50f72af802.png]: /images/20220828/faec8ce8023f4bdeb9fbf2817f853eb3.png
[783097dc70d2483c83a9185778ed7edc.png]: /images/20220828/aad9aa398e2247c2b082007ce1ac107c.png
[786140720e4749768f77b928ce92fe7a.png]: /images/20220828/4284e9cffb9846c8a0295e572fbb7d55.png
[636d8768a8c940f7abd6b545bc7049e2.png]: /images/20220828/d0f5a1b3dd9a468fa8f1b111825439a3.png
[53a791d611154db9bf88389b91b18819.png]: /images/20220828/17c3fc31dc9140c39f466799535be8ce.png
[c2da93c858bc4ed88110d3f34069c88e.png]: /images/20220828/b88e26225e32430abbbd676989d39aec.png