【小白学算法】8.二叉树的遍历，前序、中序和后序

二叉树的遍历，同样也是为了访问到树中的每个结点（仅一次）。不过，由于树的结构与之前的线性存储不同，从根结点开始，二叉树可以有多种的访问次序的选择。按照我们通常的从左到右的习惯，常见的遍历次序有3种：前序、中序、后续。

一、什么是前序、中序、后序

为了方便说明，暂且我们把访问结点，就当做是打印输出这个结点信息。那么如何区分前中后，也正是根据输出的先后顺序来定的。

前序遍历：先输出父节点，再遍历左子树，然后遍历右子树。

中序遍历：先遍历左子树，再输出父节点，然后遍历右子树。

后序遍历：先遍历左子树，再遍历右子树，最后输出父节点。

如图所示的二叉树，它的前中后输出顺序分别就是：

前序：1易大师、2寒冰射手、3盲僧、4盖伦

中序：2寒冰射手、1易大师、3盲僧、4盖伦

后序：2寒冰射手、4盖伦、3盲僧、1易大师

二、代码实现前、中、后序遍历

实现思路很简单：

1、创建英雄结点，在这里编写遍历方法。

2、创建二叉树，调用遍历方法。

3、main方法进行测试。

运行测试遍历顺序与上面预测的相符合。本章我们知道了遍历二叉树，那如果我要查找二叉树中某一个结点，前中后序这3种的查找思路又是怎样呢？

例题：

已知某二叉树的前序遍历为A-B-D-F-G-H-I-E-C，中序遍历为F-D-H-G-I-B-E-A-C，请还原这棵二叉树。

解题思路：

从前序遍历中，我们确定了根结点为A，在从中序遍历中得出F-D-H-G-I-B-E在根结点的左边，C在根结点的右边，那么我们就可以构建我们的二叉树的雏形。

那么剩下的前序遍历为B-D-F-G-H-I-E，中序遍历为F-D-H-G-I-B-E，B就是我们新的“根结点”，从中序遍历中得出F-D-H-G-I在B的左边，E在B的右边，继续构建。

那么剩下的前序遍历为D-F-G-H-I，中序遍历为F-D-H-G-I，D就是我们新的“根结点”，从中序遍历中得出F在D的左边，H-G-I在D的右边，继续构建。

那么剩下的前序遍历为G-H-I，中序遍历为H-G-I，G就是我们新的“根结点”，从中序遍历中得出H在G的左边，I在G的右边，继续构建。