数据结构与算法：python语言解释 之 通俗理解二叉树前序中序后序遍历

二叉树遍历有深度遍历和宽度遍历，深度遍历就是指前序遍历，中序遍历，后序遍历，

宽度遍历就是指层次遍历，每一层从上到下，从左到右的遍历。

层次遍历的过程，如下图所示：

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

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

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

注意：根节点指一个节点，就一个小圆圈

前序遍历，中序遍历，后序遍历的前，中，后，指的是遍历 根节点 的顺序。

前序遍历：根左右

中序遍历：左根右

后序遍历：左右根

以后在我们遍历二叉树时，要时刻牢记这9个字。

例如，我们做前序遍历，心里默念：根左右，根左右，根左右，，，就当是念经------念经法

下面看个栗子：

由字符ABCDEFGH组成的二叉树

下面开始做前序遍历，不断念我们的如来真经：根左右

本次念经需要念三次。

第一次念真经根左右，‘根，呦呵，A不就是根节点吗！写下来：A

接下来是 ‘左’，左子树是下面一坨，是一棵树

还是一棵树，开始第二次念我们的真经 根左右 ，B 是根，找到了，记下来，于是：A --> B 

‘左’是一个叶子节点D，不是树，直接记下来，于是：A --> B -->D

‘右’是一颗树，右子树，对右进行念经，需要再来一次完整的根左右念经

对这个右子树，开始我们的第三次念经：

根，是E，于是A --> B -->D --> E

左 ，是G，于是A --> B -->D --> E -->G

右 ，是H，于是A --> B -->D --> E -->G --> H

第三次根左右念经，我们很顺利，没有碰到树，直接念完（遍历完）

这个右子树，是第二次念经 根左右 的右 ，所以 第二次念经的 右 念完（遍历完），即第二次念经完成

第二次念经完成，是第一次念经的左，也就是 第一次念经的‘左’念完（遍历完）

第一次念经，根左已经完成，接下来是 右 ；右是由 C F 组成的右子树

念真经，根左右，根是C，于是A --> B -->D --> E -->G --> H  -->C 

左 ，没有左，不要理会；接下来是 右，右是F 记下来

于是：A --> B -->D --> E -->G --> H  -->C  --> F

至此，第一次念经的 右 念完，即前序遍历完成。

同样的道理，采用多次念经法，我们可以完成其他两种遍历：

中序遍历：D --> B -->G --> E -->H --> A  -->C  --> F

后序遍历：D --> G -->H --> E -->B --> F  -->C  --> A

这是我学习二叉树遍历时，自创的念经法，我觉着很好用，你们看看还能适应吗？

来总体感觉一下三种遍历的过程：

前序遍历：根左右

中序遍历：左根右

后序遍历：左右根