@author 汪春波

遍历

二叉树遍历

树的遍历方法也同样适用于二叉树（如右图4-11所示），不过由于二叉树的自身特点，还有一种中序遍历法。

前序遍历（根左右）

前序遍历（根左右，先访问根结点，然后分别用前序分别遍历左、右子树，也称为前根遍

历）。图4-11的前序遍历结果是：1，2，4，5，7，8，3，6。

中序遍历（左根右）

中序遍历（左根右，先按中序遍历左子树，再访问根结点，然后再按中序遍历右子树，也称为

中根遍历）。图4-11的中序遍历的结果是：4，2，7，8，5，1，3，6。

二叉树遍历

首先 根为 1 

4 2
7 8 54 2 7 8 5
1 3
3 6
1 3 6
4，2，7，8，5，1，3，6

后序遍历

后序遍历（左右根，分别按后序遍历要左、右子树，然后再访问根结点，也称为后根遍历）。

图4-11的后序遍历的结果是：4，8，7，5，2，6，3，1。

分析：
左右根，则 根节点1 肯定最后。

左边：
4开始， 4

7开始， 8 7

5开始， 7 5

4 8 7 5

从 2 开始， 4 5 2

4 8 7 5 2
6 3 1
4 8 7 5 2 6 3 1

层次遍历（最简单的）

层次遍历（首先访问处于0层的根结点，然后从左到右访问1层上的结点，以此类推，层层向下

访问）。图4-11的层次遍历的结果是：1，2，3，4，5，6，7，8。