算法通关村——如何使用中序和后序来恢复一棵二叉树

Myth丶恋晨 2024-03-23 17:59 15阅读 0赞

## 通过序列构造二叉树 ##

> 给出以下三个二叉树遍历的序列：
> 
> (1) 前序: 1 2 3 4 5 6 8 7 9 10 11 12 13 15 14
> 
> (2) 中序: 3 4 8 6 7 5 2 1 10 9 11 15 13 14 12
> 
> (3) 后序: 8 7 6 5 4 3 2 10 15 14 13 12 11 9 1

### 前中序复原二叉树 ###

#### 所需序列 ####

> (1) 前序: 1 2 3 4 5 6 8 7 9 10 11 12 13 15 14
> 
> (2) 中序: 3 4 8 6 7 5 2 1 10 9 11 15 13 14 12

#### 左子树复原 ####

**第一轮**

> 通过前序： 前序第一个访问的是根节点，因此根节点就是1
> 
> 通过中序：中序遍历的特点就是根节点的左子树的元素都在根节点的左侧，右子树的元素都在根节点的右侧，从中序遍历序列结合前序序列可知，中序序列1的左侧为左子树，1的右侧为右子树。从而前序通过中序划分可知，前序的左右子树。划分如下：
> 
> 中序序列划分： \[3 4 8 6 7 5 2\] 1 \[ 10 9 11 15 13 14 12\]
> 
> 前序序列划分: 1 \[2 3 4 5 6 8 7 \] \[9 10 11 12 13 15 14\]

**分析**

> 如何知道两个括号从哪里分开？可参照中序的两个数组划分的。
> 
> 前序中 7 之前的元素都在中序第一个数组中，9之后的所有元素都在第二个数组中，因此从7和9之间划分。

第一轮划分结果如下图

![image.png][]

**第二轮**

> 我们先看前序和中序的第一个数组  
> 前序: 2 3 4 5 6 8 7
> 
> 中序: 3 4 8 6 7 5 2
> 
> 通过上面的结论可知：
> 
> 根节点为2（前序）
> 
> 然后可划分为：
> 
> 前序: 2 \[3 4 5 6 8 7 \]
> 
> 中序: \[3 4 8 6 7 5 \] 2

第二轮划分结果如下图

![image.png][image.png 1]

**第三轮**

> 对 3 4 5 6 8 7 继续划分：
> 
> 前序: 3 \[4 5 6 8 7\]
> 
> 中序: 3 \[4 8 6 7 5\]

第三轮划分结果如下图

![image.png][image.png 2]

**第四轮**

> 对 4 5 6 8 7 进行划分：
> 
> 前序：4 \[5 6 8 7\]
> 
> 中序：4 \[ 8 6 7 5 \]

第四轮划分结果如下图

![image.png][image.png 3]

**第五轮**

> 对 5 6 8 7 划分：
> 
> 前序：5 \[6 8 7\]
> 
> 中序：\[8 6 7\] 5

**第六轮**

> 对 6 8 7 划分
> 
> 前序：6 \[ 8 7 \]
> 
> 中序： \[8\] 6 \[7\]
> 
> 至此，便可知左子树的树结构了。

左子树的树结构效果如下：

![image.png][image.png 4]

##### 左子树的复原结果如下 #####

![image.png][image.png 5]

#### 右子树复原 ####

**第一轮**

> 由第一轮可知如下序列
> 
> 前序： 9 10 11 12 13 15 14
> 
> 中序： 10 9 11 15 13 14 12
> 
> 对其进行划分，结果如下
> 
> 前序：9 \[ 10 11 12 13 15 14\]
> 
> 中序：\[10\] 9 \[11 15 13 14 12\]
> 
> 由结果可知，10 是 9 的左子树，11 15 13 14 12为还需划分的序列

**第二轮**

> 将序列11 12 13 15 14进行划分：
> 
> 前序：11 \[12 13 15 14\]
> 
> 中序：11 \[15 13 14 12\]

**第三轮**

> 将12 13 15 14进行划分：
> 
> 前序：12\[13 15 14\]
> 
> 中序： \[15 13 14\]12

**第四轮**

> 将 13 15 14进行划分：
> 
> 前序：13 \[ 15 14\]
> 
> 中序： \[15\] 13 \[14\]
> 
> 最终由中序获得结果，15为13的左子树，14为13的右子树

##### 左右子树复原结果如下 #####

![image.png][image.png 6]

### 中后序恢复二叉树 ###

> 通过中后序恢复二叉树与前中序唯一的不同就是：后续的最后一个是根节点，中序的处理和上述相同。所需序列如下：
> 
> (2) 中序: 3 4 8 6 7 5 2 1 10 9 11 15 13 14 12
> 
> (3) 后序: 8 7 6 5 4 3 2 10 15 14 13 12 11 9 1

#### 左子树复原 ####

**第一轮**

> 中序序列划分：\[3 4 8 6 7 5 2\] 1 \[10 9 11 15 13 14 12\]
> 
> 后序序列划分：\[8 7 6 5 4 3 2 \] \[10 15 14 13 12 11 9 \]1
> 
> 由于上述经过了上述分析，对划分结果有所了解了，因此此次划分就不画中间过程了

**第二轮**

> 对序列 8 7 6 5 4 3 2 进行划分
> 
> 中序：\[3 4 8 6 7 5 \] 2
> 
> 后序：\[8 7 6 5 4 3 \] 2

**第三轮**

> 对序列 8 7 6 5 4 3 进行划分:
> 
> 中序：3\[4 8 6 7 5\]
> 
> 后序：\[8 7 6 5 4\] 3

**第四轮**

> 对序列8 7 6 5 4进行划分：
> 
> 中序：4 \[8 6 7 5\]
> 
> 后序：\[8 7 6 5\] 4

**第五轮**

> 对序列8 7 6 5进行划分：
> 
> 中序：\[8 6 7 \] 5
> 
> 后序：\[8 7 6 \] 5

**第六轮**

> 对序列 8 7 6进行划分：
> 
> 中序：\[8\] 6 \[7\]
> 
> 后序：\[8 7\] 6
> 
> 最终，由中序划分可知，8是6的左子树，7是6的右子树

##### 左子树复原结果如下 #####

![image.png][image.png 5]

#### 右子树复原 ####

> 右子树复原所需要的序列：
> 
> 中序：10 9 11 15 13 14 12
> 
> 后序：10 15 14 13 12 11 9

**第一轮**

> 将序列10 15 14 13 12 11 9进行划分（一般选择能确定根节点的那个节点）：
> 
> 中序：\[10\] 9 \[11 15 13 14 12\]
> 
> 后序：\[10 15 14 13 12 11\] 9
> 
> 由此划分可知，10为9的左节点，11 15 13 14 12为9的右子树

**第二轮**

> 对序列15 14 13 12 11进行划分：
> 
> 中序：11 \[15 13 14 12\]
> 
> 后序：\[15 14 13 12\] 11

**第三轮**

> 对序列15 14 13 12进行划分：
> 
> 中序：\[15 13 14\] 12
> 
> 后序：\[15 14 13\] 12

**第四轮**

> 对序列15 14 13 进行划分：
> 
> 中序：\[15\] 13 \[14\]
> 
> 后序：\[15 14\]13
> 
> 从中序结果可知，15为13的左子树，14为13的右子树

##### 左右子树复原结果如下 #####

![image.png][image.png 6]

> 由此可知，前中序和中后序恢复成 二叉树的过程有些不同，但是所需的步骤和结果都是一致的。

知道了序列是如何构造成二叉树之后，便可以将其使用代码实现了，代码实现在下次总结。

[image.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/d71b5aa7ebce465eadf3be6c19f424fe.png
[image.png 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/01abeaf534b34edbb61c3477767f5249.png
[image.png 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/6c9bd516518c44598bfdb9ba722dca33.png
[image.png 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/74c5b10208324beaa97a18ec3dc1c16b.png
[image.png 4]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/b1d6e10efa4c4e37913e727feb2adc60.png
[image.png 5]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/53662add1b5b4f058f8448ea32b2b95e.png
[image.png 6]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/8ca4d9f7cc7445bbad54c3cde2e7cdd1.png