二叉树遍历结合例子具体讲解例子不能太简单

Question

二叉树遍历结合例子具体讲解例子不能太简单

Answer 1

遍历的方法有：层序遍历、先序遍历、中序遍历、后序遍历等，以下面的二叉树为例介绍遍历
E
/ \
B F
/ \ \
A D H
/ / \
C G I
\
K
/
J
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
/ \
B C
中序遍历就是 B A C，如果B有左右子树,如下图，再访问B之前先访问B的左子树
A
/ \
B C
/ \
D E
中序遍历为 D B E A C，如果C有右子树没有左子树，如下图则是先访问C再访问F
A
/ \
B C
/ \ \
D E F
最上面提到的例子
E
/ \
B F
/ \ \
A D H
/ / \
C G I
\
K
/
J
中序就是：ABCDEFGHIJK，在访问E的时候，发现E有左子树B，先B，再访问B的时候发现有左子树A，所以肯定还是A先，所以这个序列是从A开始的。
3.后序遍历
其访问顺序是先左再右再根，下面的例子，后序就是BCA
A
/ \
B C
如果B有左右子树，如下图，先访问B的左右子树，再访问B，其后序是DEBCA
A
/ \
B C
/ \
D E
如果C有右子树没有左子树有右子树，再访问C时的右子树F再访问C，其后序是DEBFCA
A
/ \
B C
/ \ \
D E F
最开始提到的例子
E
/ \
B F
/ \ \
A D H
/ / \
C G I
\
K
/
J
后序是ACDBGJKIHFE