1. 层序遍历
即从上到下按层次访问该树，每一层单独输出一行，每一层要求访问的顺序为从左到右。
例子中层序遍历为EBFADHCGIKJ，一层一层从上往下，从左往右输出。
2. 先序遍历
遍历顺序是 先根再左子树再右子树，访问根结点的操作发生在遍历其左右子树之前。
我们看例子，首先从根节点E开始，先根输出E，然后左子树B，此时的位置在B，B相当于AD两个结点的根，所以遍历B之后，遍历B的左子树A，A没有孩子结点，所以遍历B的右子树D，D有左子树遍历C，这样完成了E的左子树遍历，再遍历E的右子树F，再遍历F的左子树，这里没有，就遍历F的右子树H，然后再遍历H的左右子树，左子树G，当然G没有孩子结点，所以接下来是I，然后 K J类似。
所以先序遍历是EBADCFHGIKJ，记住一点，访问根结点的操作发生在遍历其左右子树之前，在上面的例子中，访问完E之后访问B，接下来不是访问F，而是访问B的左右子树。
3. 中序遍历
先左子树再根再右子树
A / \ BC
中序遍历就是 BA C，如果B有左右子树,如下图，再访问B之前先访问B的左子树
A/ \BC
/\
DE
中序遍历为 D B E A C，如果C有右子树没有左子树，如下图则是先访问C再访问F
A/ \BC
/\
DE
\ /
FG
中序遍历为 D B F G A C E，最上面提到的例子
E /\ B F
/\ \ A D H
CG I \
K /
J
中序就是：ABCDEFGHIJK，在访问E的时候，发现E有左子树B，先B，再访问B的时候发现有左子树A，所以肯定还是A先，所以这个序列是从A开始的。
4. 后序遍历
其访问顺序是先左再右再根，下面的例子，后序就是BCA
A /\ B C
如果B有左右子树，如下图，先访问B的左右子树，再访问B，其后序是DEBCA
A/\B C
/\ DE
如果C有右子树没有左子树有右子树，再访问C时的右子树F再访问C，其后序是DEBFCA
A/\ B C
/\/\ DE
如果C有右子树没有左子树有右子树，再访问C时的右子树F再访问C，其后序是DEBFCA
A/\ B C
/\/\ DE
\/\ F G
K J I H D
最开始提到的例子
E /\ B F
/\ \ A D H
CG I \
K /
J
后序是ACDBGJKIHFE
下载本文
