森林转二叉树举例：（法二）
AE
G
B
C
D
F
H
I
J
AAEGBCDFHIJ兄弟相连长兄为父孩子靠左头根为根
ABECFGDHIJ61
讨论4：二叉树如何还原为森林？
即B={root, LB, RB} F={T1, T2, …,Tm}
要点：把最右边的子树变为森林，其余右子树变为兄弟
A
B
E
C
F
GD
H
IJ
AEBFCDAEBCDFGHIJGHIJ62
2. 树和森林的存储方式
树有三种常用存储方式：
①双亲表示法②孩子表示法③孩子兄弟表示法
1、用双亲表示法来存储
思路：用一组连续空间来存储树的结点，同时在每个结点中附设一个指示器，指示其双亲结点在链表中的
dataparents位置。
1
dataparents23n
结点结构
树结构
63
例1: 双亲表示法
A
0A-11B0BC2C03D1DE
F
G
4E15F2H
I6G27H38I
3
缺点：求结点的孩子时需要遍历整个结构。
64
