赞
踩
GitHub同步更新(已分类):Data_Structure_And_Algorithm-Review
公众号:URLeisure 的复习仓库
公众号二维码见文末
以下是本篇文章正文内容,下面案例可供参考。
先根遍历
和后根遍历
两种方式。以下图树为例。
先序遍历:
A
B
E
F
C
D
G
I
H
ABEFCDGIH
ABEFCDGIH
中序遍历:
E
F
B
C
I
G
H
D
A
EFBCIGHDA
EFBCIGHDA
如果树非空,则先访问根节点
,然后按从左向右的顺序,先跟遍历根节点的每一棵子树。(像是对树进行类似二叉树的先序遍历)
树的先根遍历顺序与该树对应的二叉树
的先序遍历顺序相同。
(有个地方画的有点问题,但不影响观看)
先
根
遍
历
:
A
B
E
F
C
D
G
I
H
先根遍历:ABEFCDGIH
先根遍历:ABEFCDGIH
然后访问根节点
。(像是对树进行类似二叉树的后序遍历步骤)对应的二叉树
的中序遍历顺序相同。
后
根
遍
历
:
E
F
B
C
I
G
H
D
A
后根遍历:EFBCIGHDA
后根遍历:EFBCIGHDA
先序遍历
和中序遍历
两种方式。以下图森林为例。
先序遍历:
A
B
C
D
E
F
G
H
J
I
ABCDEFGHJI
ABCDEFGHJI
中序遍历:
B
C
D
A
F
E
J
H
I
G
BCDAFEJHIG
BCDAFEJHIG
先访问第一棵树的根节点
,先序遍历第一棵树的根节点的所有子树森林;对应的二叉树
的先序遍历顺序相同。(有个地方画的有点问题,但不影响观看)
先
序
遍
历
:
A
B
C
D
E
F
G
H
J
I
先序遍历:ABCDEFGHJI
先序遍历:ABCDEFGHJI
然后访问第一棵树的根节点
;对应的二叉树
的中序遍历顺序相同。
中序遍历:
B
C
D
A
F
E
J
H
I
G
BCDAFEJHIG
BCDAFEJHIG
树和森林的遍历与二叉树的遍历对应关系
:树 | 森林 | 二叉树 |
---|---|---|
先根遍历 | 先序遍历 | 先序遍历 |
后根遍历 | 中序遍历 | 中序遍历 |
下期预告:实现树的深度、叶子数、节点数
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。