接上回树结构

二叉树是一个程序，总不能是我们人为的去说吧，所以我们要用专门的程序来对二叉树进行遍历，并用程序来表达，让我们每一个元素去用电脑来运用，这就是我们今天要说的主题——二叉树的遍历

这里呢我们举了3个结点的遍历方法，分别为先序，中序和后序

通过这些遍历方法我们可以把拥有3个结点的数遍历出来，至于比较大的树，我们可以把他拆成很多3个结点的小树，再用上面的方法遍历出来。

先序遍历

这里呢我们先学习先序遍历

我们以一颗九个结点的二叉树来进行讲解

先遍历根节点，再遍历左子树。即：1是根节点先遍历1,1的左子树是2,4,5,7，而4又是2的左子树，所以遍历4，最后再遍历4的左子树，7，则这部分答案为1,2,4,7

遍历完左子树就到右子树了，而4没有右子树，所以直接来到2，2的右子树是5，遍历5

则这部分结果为5

遍历完1的左子树以后就应该到右子树了，即3,6,8,9，而3,6,8,9里面3是这课树的根节点，所以遍历3,3没有左子树，所以遍历右子树即6，而6的左子树是8，所以遍历8

则这部分答案为3,6,8

最后遍历右子树，9

最后呢我们的答案是124753689.

正如上面的知识点所说，先序遍历有3个原则：

1.先访问根结点；

2.先序遍历左子树；

3.先序遍历右子树。

其实遍历就可以总结为3个字“根，左，右”（根节点，左子树，右子树）

通过上面的讲解也可以很清晰的看出来了

巩固一下，我们再来做一道题

用先序遍历以下的树。

做做试试

答案是：1，2，4，5，8，9，3，6，7，10

你做对了吗？

中序遍历

学完了先序，我们再来看中序

图都一样，我们挨个看看

中序的遍历方法就有点逆向了，大家看看

图一：我们先遍历左子树（最左最下的（注意是先最左在最下）），是7，而7又是4的左子树，左子树遍历完了，就应该遍历根节点了，所以下一个为4,。根节点以后就应该是右子树，但是我们发现这里的4没有右子树，所以我们直接跳过。来看到4,4又是2的左子树所以我们下一个应该遍历的是根节点即2.所以第一部分的结果为7,4,2

图二：接上面，左子树，根节点都遍历完了，就应该到右子树了，右子树只有5，所以我们直接输出5就行，所以接着就是7,4,2,5

图3：一样的，我们发现1的左子树遍历完了，接下来就是根节点，1所以目前是7,4,2,5,1

图4：接下来就应该遍历有右子树了，而这里右子树的根节点3没有左子树，那么久遍历根节点即3，所以接下来就是7,4,2,5,1,3

图5:3遍历完左子树和根节点就到了右子树，即6，而6作为8,9的根节点那就应该先遍历左子树即8，接下来就是根节点6，左后是左孩子9，所以最后结果是7,4,2,5,1,3,8,6,9

我们也是遵守了以下的3个规律：

1.中序遍历左子树；

2.访问根结点；

3.中序遍历右子树。

总结起来就是“左，根，右”（左子树，根节点，右子树）

这个中序是很难的，经常会考，大家需要牢记。

我们在做1道题巩固一下吧：

还是之前那副图。大家做一下

答案是：4,2，8,5,9,1,6,3,10,7

怎么样，做对了么？没做对那就再看一遍吧（这道题挺难的）

后序遍历

看图

根据后序遍历的规则，我们先遍历左子树再遍历右子树，而这课大树的根节点为1，而1的左子树是2，而2的左子树又是4，以此类推，则最后一个左孩子是7，而隶属于7这个小树没有右子树所以直接遍历根节点，4，最后2这个根节点的左子树遍历完了就应该到右子树，则遍历出5，最后遍历根节点2.所以这个部分的答案是，7,4,5,2

遍历完左边就应该到右边了即3,6,8,9，像之前一样，先遍历左子树，而3没有左子树所以直接遍历右子树6，而6的左子树是8，遍历8，接下来就是右子树9，遍历9，遍历根节点6，最后遍历1的右子树这个树的根节点，3，则这部分的结果是，8,9,6,3

最后遍历根节点1.。所以答案如下

7,4，5,2,8,9,6,3,1.

所以

后（根）序遍历规则如下：

1.后序遍历左子树；

2.后序遍历右子树；

3,。访问根结点。

做题。

思考

答案是：4,2，8，5，9，1，6，3，10，7

现在我们已经学会了树的3种基本遍历方法

接着努力吧

下一节课我们来说关于树建立的代码

灰常重要，记得来看

点个赞吧，谢谢你们！