树的存储与森林的存储我们往往都是使用二叉链表作为其存储结构,这就涉及到了树、森林与二叉树的转换
长子作为左孩子兄弟关系向右斜
A
/ | \
B C D
/ \ \
E F G
长子作为左孩子兄弟关系向右斜
A
/
B
/ \
E C
\ \
F D
/
G左孩子作长子右斜关系做兄弟
A
/
B
/ \
E C
\ \
F D
/
G
左孩子作长子右斜关系做兄弟
A
/ | \
B C D
/ \ \
E F G第一个树的根作二叉树的根，其余树的根向右斜、各树变为二叉树
A E G
/ | \ | / \
B C D F H I
各个树转二叉树
A E G
/ / /
B F H
\ \
C I
\
D
第一个根作根，其余根向右斜
A
/ \
B E
\ / \
C F G
\ /
D H
\
I右斜关系给分开，形成多个二叉树，每个二叉树转为树
第一个根作根，其余根向右斜
A
/ \
B E
\ / \
C F G
\ /
D H
\
I
多个二叉树
A E G
/ / /
B F H
\ \
C I
\
D
各二叉树转树
A E G
/ | \ | / \
B C D F H I如果树非空，则先访问根节点，然后按从左到右的顺序，先根遍历根节点的每一棵子树，树的先根遍历顺序与该树对应的二叉树的先序遍历顺序相同。
A
/ | \
B C D
/ \ \
E F G
1、访问A 2、去往B子树 3、访问B 4、去往E子树 5、访问E 6、去往F子树
7、访问F 8、去往C子树 9、访问C 10、去往D子树 11、访问D
12、去往G子树 13、访问G
A B E F C D G
A
/
B
/ \
E C
\ \
F D
/
G
二叉树先序遍历序列
A B E F C D G如果树非空，则按从左到右的顺序，后根遍历根节点的每一棵子树，然后访问根节点。树的后根遍历顺序与该树对应的二叉树的中序遍历顺序相同。
A
/ | \
B C D
/ \ \
E F G
1、去往A 2、去往B 3、去往E 4、返回到E （去左为空 去右为空 返回到E）
5、访问E 6、去往F 7、访问F 8、去往B 9、访问B 10、去往C
11、访问C 12、去往D 13、去往G 14、访问G 15、去往D
16、访问D 17、去往A 18、访问A
E F B C G D A
A
/
B
/ \
E C
\ \
F D
/
G
二叉树中序遍历序列
E F B C G D A如果森林非空
序列与森林的二叉树的先序遍历序列相同
A E G
/ | \ | / \
B C D F H I
从左到右一棵一棵地采用先根遍历树
A B C D | E F | G H I
A
/ \
B E
\ / \
C F G
\ /
D H
\
I
森林二叉树的先序遍历
A B C D E F G H I如果森林非空
序列与森林的二叉树的中序遍历序列相同
A E G
/ | \ | / \
B C D F H I
从左到右一棵一棵地采用后根遍历树
B C D A F E H I G
A
/ \
B E
\ / \
C F G
\ /
D H
\
I
森林二叉树的中序遍历
B C D A F E H I G| 树 | 森林 | 二叉树 |
|---|---|---|
| 先根遍历 | 先序遍历 | 先序遍历 |
| 后根遍历 | 中序遍历 | 中序遍历 |