能否通过两种遍历序列画出一棵树？

淡淡的烟草味﹌ 2021-12-15 11:13 236阅读 0赞

树有通常三种遍历方法：前序遍历，中序遍历，后序遍历，还有一种层序遍历。如果只单单知道其中一种遍历方法，是无法确定一颗树的，但是如果有两种遍历方法能否确定一颗树呢？这里不是二叉树，只是简单的树，也就是当只有一个儿子的时候不严格区分是左儿子还是右儿子，统一当作是第一个儿子。

对于二叉树来说，如果确定了中序遍历或者层序遍历以后，给出任意一种其他的遍历序列，都可以得到唯一的一棵二叉树。在只给出前序遍历和后序遍历的时候，无法确定唯一二叉树。

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

### 前序遍历和中序遍历 ###

首先，先明白，前序遍历是先访问树根在分别前序遍历子树，也就是第一个访问到的一定是当前树或者子树的树根。中序遍历是先中序遍历第一个子树，然后访问树根，在分别中序遍历剩余的子树。

所以可以以根作为突破口一层一层的把子树分划出来。

举个栗子：  
**前序遍历：A B E F I J C D G H**  
**中序遍历：E B I F J A C G D H**

首先我们可以确定A是这颗树的根，通过查找中序列表可以知道EBIFJ为第一颗子树，CGDH为另一边的子树，当然我们不知道有几颗子树。

所以初步的图就是这样的：  
![1329608-20181218133029347-544082052.png][]

然后我们再用相同的手法划分一下EBIFJ这颗子树，它的前序列表是BEFIJ，可以知道B是根结点，E为第一个叶子，IFJ为另一边的子树，我们再对比一下IFJ的前序列表为FIJ，F为根，左右叶子为I和J，没有冲突。

现在我们的图就是这个样子的了：  
![1329608-20181218133040046-221369477.png][]

然后再来看另外一边是CGDH，前序列表为CDGH，按照之前的思考，C为根，GDH为另一边的子树，可是，不可能出现没有第一颗子树的情况，作为树，应该写成GDHC才符合。所以，可以认为C是一个独立的叶子。GDH为另一棵子树。按照之前的思路，D为根，G为左，H为右。没有冲突。

最终图就是：  
![1329608-20181218133109508-594297281.png][]

然后我们现在顺便写出它的后序遍历：E I J F B C G H D A。

当然画成严格区分左右子树的二叉树也是可以的：  
![1329608-20181222095147973-226345757.png][]

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

### 后序遍历和中序遍历 ###

这个和前序遍历和中序遍历的方法类似，只不过后续遍历的根是在最后，找到根，在中序列表中找到子树的划分方式，按照相似的方法可以画出一颗树。  
**中序遍历：E B I F J A C G D H**  
**后序遍历：E I J F B C G H D A**  
但是很可惜，画出来的树是这样的：ps：这里c作为二叉树的话是左儿子。  
![1329608-20181218133123023-1909761027.png][]

![1329608-20181218133132304-196983656.png][]

我们发现这两棵树的后序遍历和中序遍历序列是一样的，由此我们可以可以简单的看出，利用中序遍历和后序遍历可以确定一颗唯一的二叉树，但是无法确定唯一的一颗树。

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

### 前序遍历和后序遍历 ###

结论先写在前面，依靠前序遍历和后序遍历也是无法确定一颗树的。所以我们尝试着画出一棵符合要求的树：

**前序遍历：A B E F I J C D G H**  
**后序遍历：E I J F B C G H D A**

我们顺序遍历一下前序列表，先确定A是根，在后序遍历中A左边的序列都是它的子树，当然这堆子树长啥样我们不知道。然后观察到B，我们知道B是A的一个儿子，先画上去，然后在后序列表中观察B左边的序列是EIJF，这就是B的子树。然后在前序列表中跳过EFIJ，观察到C，所以C也是A的儿子，然后观察后序列表中C的左边没有序列了（B到C之间没有其他结点），所以C就是一个孤单的叶子。继续观察到D，D是A的第三个儿子，然后观察后序列表中D左边的序列发现GH是它的子树，然后前序列表跳过GH，结束第一次遍历。  
![1329608-20181218133143303-431377099.png][]

然后利用相同的思路划分一下EIJF和GH就可以了，易得E是单独的B的儿子，F是IJ的父亲，GH分别为D的儿子。

最终树为：  
![1329608-20181218133151812-1036839880.png][]

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

### 二叉树层序遍历特性 ###

这里做个小的补充，针对于二叉树来说，层序遍历很好的给出了二叉树每一层从左至右的结点，例如对于ABICGFJDEHK这个层序列表，A是第一层也就是根，BI是第二层，CGFJ是第三层，DEHK就是最后一层了。然后搭配前序，中序，后序列表就能画出一棵唯一二叉树。

转载于:https://www.cnblogs.com/pullself/p/10136568.html

[1329608-20181218133029347-544082052.png]: /images/20211214/9868e596d3304307b674e40686ddb02a.png
[1329608-20181218133040046-221369477.png]: /images/20211214/9f39f50672ed4b52ba9c59cdaa4e26ee.png
[1329608-20181218133109508-594297281.png]: /images/20211214/2e865d31ef8c4a738347c3ac207fd0ff.png
[1329608-20181222095147973-226345757.png]: /images/20211214/52a79277ba654e65988bd4c78b926230.png
[1329608-20181218133123023-1909761027.png]: /images/20211214/64153f687479424aa6dd9a8ee8c1f2e3.png
[1329608-20181218133132304-196983656.png]: /images/20211214/bce74325d19b49d9bc7bbef821e38e9b.png
[1329608-20181218133143303-431377099.png]: /images/20211214/b92a2b03f8a84ec8be4bd1c78284c1a9.png
[1329608-20181218133151812-1036839880.png]: /images/20211214/ca1c1e3630c04e698c8e77c1d688f863.png