二叉树遍历结合实例,说明例子不能太简单。

遍历方法包括序列遍历、前序列遍历、中序列遍历、后序列遍历等。以下面的二叉树为例介绍遍历。

E

/ \

B F

/ \ \

一个小时

/ / \

C G I

\

K

/

J

1.序列遍历

即从上到下分层访问树,每一层单独输出一行,每一层要求的访问顺序是从左到右。

在示例中,顺序遍历是EBFADHCGIKJ,从上到下、从左到右输出。

2.优先遍历

遍历顺序是先根,再左子树,再右子树,访问根节点的操作发生在遍历其左右子树之前。

让我们看看例子。首先我们从根节点E开始,然后在根输出E,然后是左子树B,此时位置是B,相当于AD的两个节点的根。所以遍历B后,B的左子树A没有子节点,所以B的右子树D有左子树C,这样就完成了E的左子树遍历,E的右子树F,F的左子树。

所以优先遍历是EBADCFHGIKJ。记住,访问根节点的操作发生在遍历它的左右子树之前。在上面的例子中,访问E之后,访问B,然后访问B的左右子树,而不是F..

3.中间顺序遍历

首先是左子树,然后是根,然后是右子树。

A

/ \

公元前

中序遍历是B A C .如果B有左右子树,如下图,先访问B的左子树再访问B。

A

/ \

公元前

/ \

设计工程师

中序遍历是D B E A C,如果C有右子树没有左子树,如下图所示,就是先访问C再访问f。

A

/ \

公元前

/ \ \

欧洲发展基金

上面提到的例子

E

/ \

B F

/ \ \

一个小时

/ / \

C G I

\

K

/

J

中间的序列是:ABCDEFGHIJK,我访问E的时候发现E有一个左子树B,先是B,然后我访问B的时候发现了一个左子树A,所以肯定是A第一,所以这个序列是A开头的。

3.后序遍历

访问顺序是先左后右,然后是root。在下面的示例中,后一个顺序是BCA。

A

/ \

公元前

如果B有左右子树,如下图所示,先访问B的左右子树,然后是B,最后是DEBCA。

A

/ \

公元前

/ \

设计工程师

如果C有右子树,没有左子树有右子树,C的右子树F会再次访问C,后面是DEBFCA。

A

/ \

公元前

/ \ \

欧洲发展基金

第一个例子提到

E

/ \

B F

/ \ \

一个小时

/ / \

C G I

\

K

/

J

后者是ACDBGJKIHFE。