先序中序数组推后序数组

素颜马尾好姑娘i 2022-04-15 06:07 173阅读 0赞

# 二叉树遍历 #

所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问 题。 遍历是[二叉树][Link 1]上最重要的运算之一，是二叉树上进行其它运算之基础。

从二叉树的[递归][Link 2]定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作：

⑴访问结点本身（N），

⑵遍历该结点的左子树（L），

⑶遍历该结点的右子树（R）。

以上三种操作有六种执行次序：

NLR、LNR、LRN、NRL、RNL、RLN。

注意：

前三种次序与后三种次序对称，故只讨论先左后右的前三种次序。

### 遍历命名 ###

根据访问结点操作发生位置命名：

① NLR：[前序遍历][Link 3](Preorder Traversal 亦称（先序遍历））

——访问根结点的操作发生在遍历其左右子树之前。

② LNR：[中序遍历][Link 4](Inorder Traversal)

——访问根结点的操作发生在遍历其左右子树之中（间）。

③ LRN：[后序遍历][Link 5](Postorder Traversal)

——访问根结点的操作发生在遍历其左右子树之后。

注意：

由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为[先根遍历][Link 6]、中根遍历和后根遍历。

给出某棵树的先序遍历结果和中序遍历结果（无重复值），求后序遍历结果。

比如

先序序列为：1，2，4，5，3，6，7，8，9

中序序列为：4，2，5，1，6，3，7，9，8

### 方法1：我们可以重建整棵树： ###

### [https://blog.csdn.net/hebtu666/article/details/84322113][https_blog.csdn.net_hebtu666_article_details_84322113] ###

建议好好看这个网址，对理解这个方法有帮助。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70][]

如图

然后后序遍历得出后序序列。

### 方法2：我们可以不用重建，直接得出： ###

过程：

1）根据当前先序数组，设置后序数组最右边的值

2）划分出左子树的先序、中序数组和右子树的先序、中序数组

3）对右子树重复同样的过程

4）对左子树重复同样的过程

原因：我们的后序遍历是左右中的，也就是先左子树，再右子树，再根

举个例子：

比如这是待填充序列：

![20181122145811848.png][]

我们确定了根，并且根据根和中序序列划分出了左右子树，黄色部分为左子树：

![20181122145916928.png][]：

先处理右子树（其实左右中反过来就是中右左，顺着填就好了）：

![20181122150317998.png][]

我们又确定了右子树的右子树为黑色区域，然后接着填右子树的右子树的根（N)即可。

举例说明：

a\[\]先序序列为：1，2，4，5，3，6，7，8，9

b\[\]中序序列为：4，2，5，1，6，3，7，9，8

c\[\]后序序列为：0，0，0，0，0，0，0，0，0（0代表未确定）

我们根据先序序列，知道根一定是1，所以后序序列：0，0，0，0，0，0，0，0，1

从b\[\]中找到1，并划分数组：

左子树的先序：2，4，5，

中序：4，2，5

右子树的先序：3，6，7，8，9，

中序：6，3，7，9，8

我们继续对右子树重复相同的过程：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 1][]

（图示为当前操作的树，我们是不知道这棵树的样子的，我是为了方便叙述，图片表达一下当前处理的位置）

当前树的根一定为先序序列的第一个元素，3，所以我们知道后序序列：0，0，0，0，0，0，0，3，1

我们继续对左右子树进行划分，中序序列为6，3，7，9，8，我们在序列中找到2，并划分为左右子树：

左子树：

先序序列：6

中序序列：6

右子树：

先序序列：7，8，9

中序序列：7，9，8

我们继续对右子树重复相同的过程，也就是如图所示的这棵树：

![20181122144039981.png][]

现在我们的后序序列为0，0，0，0，0，0，0，3，1

这时我们继续取当前的根（先序第一个元素）放在下一个后序位置：0，0，0，0，0，0，7，3，1

划分左右子树：

左子树：空，也就是它![20181122144350454.png][]

右子树：先序8，9，中序9，8，也就是这个树![20181122144402688.png][]

我们继续处理右子树：先序序列为8，9，所以根为8，我们继续填后序数组0，0，0，0，0，8，7，3，1

然后划分左右子树：

左子树：先序：9，中序：9

右子树：空

对于左子树，一样，我们取头填后序数组0，0，0，0，9，8，7，3，1，然后发现左右子树都为空.

![20181122144855963.png][]我们就把这个小框框处理完了

![20181122144039981.png][]然后这棵树的右子树就处理完了，处理左子树，发现为空。这棵树也处理完了。

![20181122145023830.png][]这一堆就完了。我们处理以3为根的二叉树的左子树。继续填后序数组：

0，0，0，6，9，8，7，3，1

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 2][]

整棵树的右子树处理完了，左子树同样重复这个过程。

最后4，5，2，6，9，8，7，3，1

好累啊。。。。。。挺简单个事写了这么多。

回忆一下过程：

1）根据当前先序数组，设置后序数组最右边的值

2）划分出左子树的先序、中序数组和右子树的先序、中序数组

3）对右子树重复同样的过程

4）对左子树重复同样的过程

就这么简单

先填右子树是为了数组连续填充，容易理解，先处理左子树也可以。

最后放上代码吧

a=[1,2,4,5,3,6,7,8,9]
    b=[4,2,5,1,6,3,7,9,8]
    l=[0,0,0,0,0,0,0,0,0]
    
    def f(pre,tin,x,y):
        #x,y为树在后序数组中对应的范围
        if pre==[]:return
        l[y]=pre[0]#根
        pos=tin.index(pre[0])#左子树元素个数
        f(pre[pos+1:],tin[pos+1:],x+pos,y-1)#处理右子树
        f(pre[1:pos+1],tin[:pos],x,x+pos-1)#处理左子树
        
    f(a,b,0,len(l)-1)
    print(l)

[Link 1]: https://baike.baidu.com/item/%E4%BA%8C%E5%8F%89%E6%A0%91/1602879
[Link 2]: https://baike.baidu.com/item/%E9%80%92%E5%BD%92
[Link 3]: https://baike.baidu.com/item/%E5%89%8D%E5%BA%8F%E9%81%8D%E5%8E%86
[Link 4]: https://baike.baidu.com/item/%E4%B8%AD%E5%BA%8F%E9%81%8D%E5%8E%86
[Link 5]: https://baike.baidu.com/item/%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86
[Link 6]: https://baike.baidu.com/item/%E5%85%88%E6%A0%B9%E9%81%8D%E5%8E%86
[https_blog.csdn.net_hebtu666_article_details_84322113]: https://blog.csdn.net/hebtu666/article/details/84322113
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70]: /images/20220415/f03d6bfa7ee94192b2c8f42f4eb0b2b0.png
[20181122145811848.png]: /images/20220415/d378f8f0f58748ebb6995e3ef6c909a3.png
[20181122145916928.png]: /images/20220415/ebaf16e2827343d899d4554402eb93e3.png
[20181122150317998.png]: /images/20220415/0a33ef01e8474ada96cec873b8b6ccc0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 1]: /images/20220415/1061d7160b4146b8b638b52ba73bea3c.png
[20181122144039981.png]: /images/20220415/f0d9bfc6ad7c414386277a956c86ca27.png
[20181122144350454.png]: /images/20220415/9dfa545f7b3744e99791f1e6fa34212d.png
[20181122144402688.png]: /images/20220415/50af59c0fbce4e84a616641506292ef2.png
[20181122144855963.png]: /images/20220415/73b22db0375641d18ea15fe83ec7774a.png
[20181122145023830.png]: /images/20220415/0029813de3d941c0863ef97f1e38358a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 2]: /images/20220415/422d95f4a127427dbd2bd7baaf824002.png