二叉树遍历的基础知识是软件评测师考试的重要考点，经常出现在上午场的客观选择题当中。遍历是按某种策略访问树中的每个结点，且仅访问一次的过程。由于二叉树所具有的递归性质，一棵非空的二叉树是由根结点、左子树和右子树三部分构成的，因此若能依次遍历这三部分，也就遍历了整棵二叉树。按照先遍历左子树后遍历右子树的约定，根据访问根结点位置的不同，可得到二叉树的先序、中序和后序3种遍历方法。下面就该知识点并结合例题进行总结学习。
一、先序遍历
先序遍历就是先遍历根节点，然后遍历左子树，最后遍历右子树。对于左子树或者右子树本身，也是符合先序遍历的顺序的，也就是遍历的递归性质：子树本身也是作为一颗单独的二叉树看待的。对于算术表达式，先序遍历后得到前缀表达式。
对于上图进行先序遍历，先访问根节点，也就是1；然后访问左子树，此时左子树本身也可以看成一棵树，也符合先序遍历的递归性质，所以左子树的先序遍历顺序为：2、4、5；最后访问右子树，此时右子树本身也可以看成一棵树，也符合先序遍历的递归性质，所以右子树的先序遍历顺序为：3、6；
综上可得整个二叉树的先序遍历顺序为：1、2、4、5、3、6。
二、中序遍历
中序遍历就是先遍历左子树，然后遍历根节点，最后遍历右子树。对于左子树或者右子树本身，也是符合中序遍历的顺序的，也就是遍历的递归性质：子树本身也是作为一颗单独的二叉树看待的。对于算术表达式，中序遍历后得到中缀表达式，此时需要注意的是，中缀表达式是需要根据具体情况通过添加括号来表示优先级的，也是我们看着最顺眼的一种形式。
对于上图进行中序遍历，先访问左子树，此时左子树本身也可以看成一棵树，也符合中序遍历的递归性质，所以左子树的中序遍历顺序为：4、2、5；然后访问根节点，也就是1；最后访问右子树，此时右子树本身也可以看成一棵树，也符合中序遍历的递归性质，所以右子树的中序遍历顺序为：6、3；
综上可得整个二叉树的中序遍历顺序为：4、2、5、1、6、3。
三、后续遍历
后序遍历就是先遍历左子树，然后遍历右子树，最后遍历根节点。对于左子树或者右子树本身，也是符合后序遍历的顺序的，也就是遍历的递归性质：子树本身也是作为一颗单独的二叉树看待的。对于算术表达式，后序遍历后得到后缀表达式，后缀表达式又叫做逆波兰式。例如对于算术表达式：a+b-c*d。其后缀表达式计算过程为：
（1）先把字母按顺序列出来，即abcd；
（2）然后按照计算的优先级往字母后面加符号。此时按照优先级应该先计算c*d，所以先往cd后面加一个*，即：abcd*，此时cd*就相当于和a一样的一个字符值。
（3）然后计算a+b，所以往ab后面加一个+，即ab+cd*，此时ab+就相当于和a一样的一个字符值。
（4）最后计算a+b的结果减去c*d的结果，也就是往最后加一个-，即ab+cd*-。
对于上图进行后序遍历，先访问左子树，此时左子树本身也可以看成一棵树，也符合后序遍历的递归性质，所以左子树的后序遍历顺序为：4、5、2；然后访问右子树，此时右子树本身也可以看成一棵树，也符合后序遍历的递归性质，所以右子树的后序遍历顺序为：6、3；最后访问根节点，也就是1；
综上可得整个二叉树的后序遍历顺序为：4、5、2、6、3、1。
下面是近几年对该知识点考察过的真题，以后仍是考试出题的重点，大家要重视起来。
【2018年第17-18题】某算术表达式用二叉树表示如下，该算术表达式的中缀式为（ 1 ），其后缀式为（ 2 ）。
（1）
A、a-b+c*d
B、a-(b+c)*d
C、(a-(b+c))*d
D、a-(b+c*d)
（2）
A、abc+-d*
B、abcd*+-
C、ab-c+d*
D、abcd+*-
解析：本题考查二叉树的基础知识。
中序遍历可以得到中缀式，先中序遍历根结点的左子树，此时左子树本身也可以看成是一棵二叉树，也符合中序遍历的性质，中序遍历左子树可得a-（b+c）；再访问根结点*，最后中序遍历根结点的右子树d。综上可得该二叉树最后中序遍历的结果为：（a-（b+c））*d。
后序遍历可以得到后缀式，先后序遍历根结点的左子树，此时左子树本身也可以看成是一棵二叉树，也符合后序遍历的性质，后序遍历左子树可得abc+-；再后序遍历根结点的右子树d，再访问根结点*。综上可得该二叉树后序遍历的结果为：abc+-d*。
故正确答案为：（1）C （2）A
【2019年第24题】若某二叉树的先序遍历序列是ABDCE，中序遍历序列是BDACE，则该二叉树为（ ）。
A、
B、
C、
D、
解析：本题考查二叉树遍历的基础知识。
对于这一类题只需要依次验证各个选项即可。
选项A：先序遍历的结果为: ABDEC；中序遍历的结果为: DBEAC；
选项B：先序遍历的结果为: ABCDE；中序遍历的结果为: BADCE；
选项C：先序遍历的结果为: ABDCE；中序遍历的结果为: BDAEC；
选项D：先序遍历的结果为: ABDCE；中序遍历的结果为: BDACE；
最终选项D符合题目要求，故正确答案为：D
作者唯一官方个人微信公众号（昊洋与你一起成长）：HYJY20180101
写于2021年10月8日
作者：昊洋讲师
版权所有，侵权必究
