二叉树的遍历（前序、中序、后序、已知前中序求后序、已知中后序求前序）

秒速五厘米 2022-12-19 00:53 157阅读 0赞

# ![9ae3b38d3e56c024e830ca7a9395315b.png][] #

之前的一篇随笔（[二叉树、前序遍历、中序遍历、后序遍历][Link 1]）只对二叉树的遍历进行了笼统的描述，这篇随笔重点对前、中、后序的遍历顺序进行分析

# 二叉树的遍历 #

二叉树的深度优先遍历可细分为前序遍历、中序遍历、后序遍历，这三种遍历可以用递归实现（本篇随笔主要分析递归实现），也可使用非递归实现的

前序遍历：根节点->左子树->右子树**（根->左->右）**

中序遍历：左子树->根节点->右子树**（左->根->右）**

后序遍历：左子树->右子树->根节点**（左->右->根）**

在进行已知两种遍历顺序求另一种遍历顺序前，先看一下不同遍历顺序对应的代码

**前序遍历**

![复制代码][48304ba5e6f9fe08f3fa1abda7d326ab.png]

1 /* 以递归方式 前序遍历二叉树 */
     2 void PreOrderTraverse(BiTree t, int level)
     3 {
     4     if (t == NULL)    
     5     {
     6         return ;
     7     }
     8     printf("data = %c level = %d\n ", t->data, level);
     9     PreOrderTraverse(t->lchild, level + 1);
    10     PreOrderTraverse(t->rchild, level + 1);
    11 }

![复制代码][48304ba5e6f9fe08f3fa1abda7d326ab.png]

**中序遍历**

![复制代码][48304ba5e6f9fe08f3fa1abda7d326ab.png]

1 /* 以递归方式 中序遍历二叉树 */
     2 void PreOrderTraverse(BiTree t, int level)
     3 {
     4     if (t == NULL)    
     5     {
     6         return ;
     7     }
     8     PreOrderTraverse(t->lchild, level + 1);
     9     printf("data = %c level = %d\n ", t->data, level);
    10     PreOrderTraverse(t->rchild, level + 1);
    11 }

![复制代码][48304ba5e6f9fe08f3fa1abda7d326ab.png]

**后序遍历**

![复制代码][48304ba5e6f9fe08f3fa1abda7d326ab.png]

1 /* 以递归方式 后序遍历二叉树 */
     2 void PreOrderTraverse(BiTree t, int level)
     3 {
     4     if (t == NULL)    
     5     {
     6         return ;
     7     }
     8     PreOrderTraverse(t->lchild, level + 1);
     9     PreOrderTraverse(t->rchild, level + 1);
    10     printf("data = %c level = %d\n ", t->data, level);
    11 }

![复制代码][48304ba5e6f9fe08f3fa1abda7d326ab.png]

三种遍历方式对应的代码几乎相同，只是一条语句的位置发生了变化

printf("data = %c level = %d\n ", t->data, level);

只看文字和代码来理解遍历的过程是比较困难的，建议读者亲自去遍历，为了理清遍历的过程下面上题

![490adcd30d363dd2d47c98db94a0f253.png][]

（图片来源：[https://www.cnblogs.com/xinchrome/p/4905608.html][https_www.cnblogs.com_xinchrome_p_4905608.html]）

## 前序遍历 ##

前序的遍历的特点，根节点->左子树->右子树，注意看前序的遍历的代码printf语句是放在两条递归语句之前的，所以先**访问根节点G，打印G**，然后访问左子树D，此时左子树D又作为根节点，**打印D，**再访问D的左子树A

A又作为根节点，**打印A，**A没有左子树或者右子树，函数调用结束返回到D节点（此时已经打印出来的有：**GDA**）D节点的左子树已经递归完成，现在递归访问右子树F，F作为根节点，**打印F，**F有左子树访问左子树E，E作为

根节点，**打印E，**（此时已经打印出来的有：**GDAFE**），E没有左子树和右子树，函数递归结束返回F节点，F的左子树已经递归完成了，但没有右子树，所以函数递归结束，返回D节点，D节点的左子树和右子树递归全部完成，

函数递归结束返回G节点，访问G节点的右子树M，M作为根节点，**打印M，**访问M的左子树H，H作为根节点，**打印H，**（此时已经打印出来的有：**GDAFEMH**）H没有左子树和右子树，函数递归结束，返回M节点，M节点的左子树已经

递归完成，访问右子树Z，Z作为根节点，**打印Z，**Z没有左子树和右子树，函数递归结束，返回M节点，M节点的左子树右子树递归全部完成，函数递归结束，返回G节点，G节点的左右子树递归全部完成，整个二叉树的遍历就结束了

（MGJ，终于打完了··）

**前序遍历结果：GDAFEMHZ**

**总结一下前序遍历步骤**

第一步：**打印该节点（再三考虑还是把访问根节点这句话去掉了）**

第二步：访问左子树，返回到第一步（注意：返回到第一步的意思是将根节点的左子树作为**新的根节点**，就好比图中D是G的左子树但是D也是A节点和F节点的根节点）

第三步：访问右子树，返回到第一步

第四步：结束递归，返回到上一个节点

** 前序遍历的另一种表述：**

**（1）访问根节点**

**（2）前序遍历左子树**

**（3）前序遍历右子树**

**（在完成第2,3步的时候，也是要按照前序遍历二叉树的规则完成）**

**前序遍历结果：GDAFEMHZ**

## 中序遍历（详细遍历过程就不再赘述了，(┬＿┬)） ##

## 中序遍历步骤 ##

第一步：访问该节点左子树

第二步：若该节点有左子树，则返回第一步，**否则打印该节点**

第三步：若该节点有右子树，则返回第一步，**否则结束递归并返回上一节点**

（按我自己理解的中序就是：先左到底，左到不能在左了就停下来并打印该节点，然后返回到该节点的上一节点，并打印该节点，然后再访问该节点的右子树，再左到不能再左了就停下来）

**中序遍历的另一种表述：**

**（1）中序遍历左子树**

**（2）访问根节点**

**（3）中序遍历右子树**

**（在完成第1，3步的时候，要按照中序遍历的规则来完成）**

**所以该图的中序遍历为：ADEFGHMZ**

## 后序遍历步骤 ##

第一步：访问左子树

第二步：若该节点有左子树，返回第一步

第三步：若该节点有右子树，返回第一步，**否则打印该节点并返回上一节点**

** 后序遍历的另一种表述：**

**（1）后序遍历左子树**

**（2）后序遍历右子树**

**（3）访问根节点**

**（在完成1,2步的时候，依然要按照后序遍历的规则来完成）**

**该图的后序遍历为：AEFDHZMG**

（读者如果在纸上遍历二叉树的时候，仍然容易将顺序搞错建议再回去看一下三种不同遍历对应的代码）

# 进入正题，已知两种遍历结果求另一种遍历结果（其实就是重构二叉树） #

## 第一种：已知前序遍历、中序遍历求后序遍历 ##

前序遍历：ABCDEF

中序遍历：CBDAEF

在进行分析前读者需要知道不同遍历结果的特点

**1、前序遍历的第一元素是整个二叉树的根节点**

**2、中序遍历中根节点的左边的元素是左子树，根节点右边的元素是右子树**

**3、后序遍历的最后一个元素是整个二叉树的根节点**

**（如果读者不明白上述三个特点，建议再回去看一下三种不同遍历对应的代码，并在纸上写出一个简单的二叉树的三种不同的遍历结果，以加深对三种不同遍历的理解）**

用上面这些特点来分析遍历结果，

**第一步：**先看前序遍历**A**肯定是根节点![df5dc1e29d58c5f2765dc6a3a1934b18.png][]

**第二步：**确认了根节点，再来看中序遍历，中序遍历中根节点A的左边是**CBD**，右边是**EF**，所有可以确定二叉树既有左子树又有右子树![b97681e8ed4dc8c3322e67645474cf0b.png][]

**第三步：**先来分析左子树**CBD，**那么CBD谁来做A的左子树呢？这个时候**不能**直接用中序遍历的特点（左->根->右）得出左子树应该是这个样子![4e6d25d1f67985f227e3a8d2ec045411.png][]

因为有两种情况都满足中序遍历为**CBD![2c6b828783f2c3ee3237b854f0918d7e.png][]**无法直接根据中序遍历来直接得出左子树的结构，这个时候就要返回到前序遍历中去

观察前序遍历**ABCDEF，**左子树**CBD**在前序遍历中的顺序是**BCD，**意味着**B**是左子树的根节点（这么说可能不太好理解，换个说法就是B是A的左子树）,得出这个结果是因为如果一个二叉树的根节点有左子树，那么

这个左子树一定在前序遍历中一定紧跟着根节点（这个是用前序遍历的特点（根->左->右）得出的）,到这里就可以确认**B**是左子树的根节点![9e535d020553404a0d415c0064b30f73.png][]

**第四步：**再观察中序遍历**CBDAEF，**B元素左边是**C**右边是**D**，说明B节点既有左子树又有右子树，左右子树只有一个元素就可以直接确定了，不用再返回去观察前序遍历![38395a15c0551f8275787c8def995ce3.png][]

**第五步：**到这里左子树的重建就已经完成了，现在重建右子树，因为重建右子树的过程和左子树的过程一模一样，步骤就不像上面写这么细了（(┬＿┬)），观察中序遍历右子树为**EF**，再观察前序遍历**ABCDEF**中右子树

的顺序为**EF**，所以E为A的右子树，再观察中序便利中**E**只有右边有**F**，所有F为E的右子树，最后得到的二叉树是这个样子的

![9f0044a82d58034e5950b98d0b57a0d8.png][]所有求得的后序遍历为：**CDBFEA**

总结一下上述步骤： 先观察前序遍历找到根节点->观察中序遍历将根节点左边归为左子树元素，右边归为右子树元素（可能会出现只有左子树或者右子树的情况）->观察前序遍历中左\\右子树几个元素的顺序，最靠前的为左\\右子树的根节点->重复前面的步骤

## 第二种：已知中序遍历、后序遍历求前序遍历（题还是上面这道） ##

中序遍历：CBDAEF

后序遍历为：CDBFEA

仍然是根据不同遍历方式结果的特点来重构二叉树，过程很相似这里就不详细说了，后序遍历的最后一个元素A是根节点，在中序遍历中以根节点A作为分界将元素分为左子树（**CBD**）和右子树（**EF**），再观察后序遍历中左子树的顺序是CDB

，可以判断出B是左子树的根节点（因为后序遍历是：左->右->根），再观察中序遍历，B元素左边是C右边是D，说明B节点既有左子树又有右子树，左右子树只有一个元素就可以直接确定了，不用再返回去观察后序遍历，左子树重建完成，

现在来看右子树，右子树有两个元素**EF，**观察后序遍历E在F的后面，所以E是右子树的根节点，然后看中序遍历中E只有右边一个F元素了，即F是E的右子树，此时整个二叉树重构完成

总结一下上述步骤：先观察后序遍历找到根节点->观察中序遍历将根节点左边归为左子树元素，右边归为右子树元素（可能会出现只有左子树或者右子树的情况）->观察后序遍历中左\\右子树几个元素的顺序，最靠后的为左\\右子树的根节点->重复前面的步骤

## 注意：已知前序遍历、后序遍历无法求出中序遍历（因为由前序后序重构出来的二叉树不止一种） ##

举个栗子![627ffb3e044bc74154ea08fb2f28cc4e.png][]左图这两种二叉树前序（**BEFA**）和后序（**AFEB**）一样，但对应的中序遍历结果不一样（左边的是AFEB右边的是BEFA），所以仅靠前序后序是

重构出唯一的二叉树

[9ae3b38d3e56c024e830ca7a9395315b.png]: /images/20221120/ce66d22fb5774588a6aee3303c243c53.png
[Link 1]: https://www.cnblogs.com/lanhaicode/p/10358736.html
[48304ba5e6f9fe08f3fa1abda7d326ab.png]: /images/20221120/84a58a58cb784d4bac6263ddf7f66100.png
[490adcd30d363dd2d47c98db94a0f253.png]: https://img-blog.csdnimg.cn/img_convert/490adcd30d363dd2d47c98db94a0f253.png
[https_www.cnblogs.com_xinchrome_p_4905608.html]: https://www.cnblogs.com/xinchrome/p/4905608.html
[df5dc1e29d58c5f2765dc6a3a1934b18.png]: https://img-blog.csdnimg.cn/img_convert/df5dc1e29d58c5f2765dc6a3a1934b18.png
[b97681e8ed4dc8c3322e67645474cf0b.png]: https://img-blog.csdnimg.cn/img_convert/b97681e8ed4dc8c3322e67645474cf0b.png
[4e6d25d1f67985f227e3a8d2ec045411.png]: https://img-blog.csdnimg.cn/img_convert/4e6d25d1f67985f227e3a8d2ec045411.png
[2c6b828783f2c3ee3237b854f0918d7e.png]: https://img-blog.csdnimg.cn/img_convert/2c6b828783f2c3ee3237b854f0918d7e.png
[9e535d020553404a0d415c0064b30f73.png]: https://img-blog.csdnimg.cn/img_convert/9e535d020553404a0d415c0064b30f73.png
[38395a15c0551f8275787c8def995ce3.png]: https://img-blog.csdnimg.cn/img_convert/38395a15c0551f8275787c8def995ce3.png
[9f0044a82d58034e5950b98d0b57a0d8.png]: https://img-blog.csdnimg.cn/img_convert/9f0044a82d58034e5950b98d0b57a0d8.png
[627ffb3e044bc74154ea08fb2f28cc4e.png]: https://img-blog.csdnimg.cn/img_convert/627ffb3e044bc74154ea08fb2f28cc4e.png

发表评论取消回复

表情：

评论列表（有 0 条评论，157人围观）

还没有评论，来说两句吧...

相关阅读

相关二叉树的遍历（前序、中序、后序、已知前中序求后序、已知中后序求前序）

![9ae3b38d3e56c024e830ca7a9395315b.png][] 之前的一篇随笔（[二叉树、前序遍历、中序遍历、后序遍历][Link 1]）只对二叉树的

秒速五厘米/ 2022年12月19日 00:53/ 0 赞/ 158 阅读

相关二叉树，前序+中序=>后序

include<iostream> include<cstdio> include<vector> include<cstring> u

落日映苍穹つ/ 2022年09月27日 15:29/ 0 赞/ 172 阅读

相关二叉树前序、中序、后序遍历相互求法

[二叉树前序、中序、后序遍历相互求法][Link 1] 今天来总结下二叉树前序、中序、后序遍历相互求法，即如果知道两个的遍历，如何求第三种遍历方法，比较笨的方法是画

Bertha 。/ 2022年08月26日 03:54/ 0 赞/ 143 阅读

相关二叉树前序、中序、后序遍历相互求法

今天来总结下二叉树前序、中序、后序遍历相互求法，即如果知道两个的遍历，如何求第三种遍历方法，比较笨的方法是画出来二叉树，然后根据各种遍历不同的特性来求，也可以编程求出，下面我们

雨点打透心脏的1/2处/ 2022年08月21日 09:46/ 0 赞/ 119 阅读

相关已知二叉树中序，前序（或后序 -求后序（或前序

已知前序，中序的遍历的求后序 node print_postOrder(int len,char a,char b) { int i;

向右看齐/ 2022年07月12日 07:11/ 0 赞/ 157 阅读

相关已知二叉树中序，前序（或后序 -求后序（或前序

已知前序，中序的遍历的求后序 node print_postOrder(int len,char a,char b) { int i;

灰太狼/ 2022年07月12日 07:11/ 0 赞/ 148 阅读

相关二叉树遍历（已知中序、先序求后序）

二叉树的遍历 Time Limit: 1000ms Memory Limit: 32768KB This problem will be judged on HRBU

灰太狼/ 2022年06月09日 10:38/ 0 赞/ 197 阅读

相关二叉树遍历（已知先序、中序求后序）

【例3-4】求后序遍历时间限制: 1000 ms 内存限制: 65536 KB 提交数: 11 通过数: 9 【题目描述】输入一棵二叉树的先

柔情只为你懂/ 2022年06月09日 10:30/ 0 赞/ 206 阅读

相关 Python剑指offer之已知前序中序求后序遍历

详细清晰的思路介绍可以参见博客：[已知二叉树的前序遍历和中序遍历，如何得到它的后序遍历][Link 1] 下面给出题目和python实现代码：题目：输入某二叉树的前序遍

柔情只为你懂/ 2022年05月26日 09:47/ 0 赞/ 108 阅读

相关已知二叉树的中序和后序求前序

例子，后序遍历为 gbdehfca，中序遍历为 dgbaechf 后序遍历中的最后一个元素是根节点，a，然后查找中序中a的位置把中序遍历分成 dgb a echf

朱雀/ 2021年10月09日 03:44/ 0 赞/ 304 阅读