广东省汕头市金山中学高中信息技术信息学竞赛班数据结构专项培训教程07树
【练习】：
请将前面遍历二叉树的算法稍加改动，分别写出先序、中序、后序建立二叉树的算法。
§7.5 树的存储结构
【思考】 请先不要看下面内容，如果对一棵树（不定支数），你如何设计它的存储结构？ 多重链表表示法
每个结点的设m个指针域指向该结点的子数，m为树的度，结点结构如下：
Data child1 child2 …… childm
很容易看出，多重链表的缺点是，当树中结点的子树数相差较大，许多结点的度小于m时，链表中有很多空指针域，空间较浪费。 双亲表示法
这种存储结构利用每个结点（除根外）只有唯一的双亲的性质，以一组连续空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲结点在链表中的位置。
A ○data A B C D E F G H I parent 0 1 1 2 2 3 5 5 5
1 2 3 4 5 6 7 8 9
B ○C ○D ○E ○F ○
G ○H ○I ○其存储结构说明如下：
TYPE tnode=record Data：char；
Parent：integer； end；
VAR tree：array [1..maxnode] of tnode；
孩子表示法
将每个结点的孩子结点用单链表链接起来，树中n个结点就有n条孩子链（叶子的孩子链为空），而将这n条链的头结点按顺序排列起来，组成一个线性表。
2 3 2 3 1 1 A 0 A 2 2 B 1 4 5 B 4 5 3 3 C 1 C 6 6 4 D 4 D 2 5 5 E 2 7 8 9 E 7 8 9 6 F 6 F 3 7 G 7 G 5 8 8 H 5 H 9 I 9 I 5 （a）孩子链表
42 / 17 图7.5.1
（b）带双亲的孩子链表
广东省汕头市金山中学高中信息技术信息学竞赛班数据结构专项培训教程07树
如图7.5.1（a）孩子链表的存储结构说明如下： TYPE tlink=^tnode; Tnode=RECORD
Data : char; Next : tlink; End;
Var tree: array [1..n] of tlink;
这种方法较适用于涉及孩子的操作，但不适用于涉及双亲的操作。我们可以采取改进的存储方法，在每一个孩子链的头结点中加一个域，存储其双亲结点的位置，如图7.5.1(b)。 孩子兄弟表示法
又称二叉链表表示法，链表中结点的两个链接域分别指向该结点的第一个孩子结点和下一个兄弟结点。
结点结构说明如下： TYPE tlink=^tnode; 1 Tnode=RECORD
Data : char; 2 3 fch , nsib :tlink; END 4 5 6 7 8 9
§7.6 森林与二叉树的转换
从上面树的孩子兄弟表示法可以看出，二叉树和树都可用二叉链表作为存储结构，则以二叉链表作为媒介可导出树与二叉树之间的一个对应关系。也就是说，给定一棵树，可以找出唯一的一棵二叉树与之对应。
将一般树或森林转换成二叉树表示，其目的是为了节省存储空间。 §7.6.1 树或森林转换成二叉树 树转换成二叉树的步骤如下：
① 将结点的所有兄弟连接在一起；
② 将所有不是连到最左子结点的子结点链表删除； ③ 将结点的右子树向顺时针方向旋转45°。
A 【图7.6.1】 ○A ○
B ○C ○D ○B ○C ○D ○
E ○F ○G ○H ○I ○J ○E ○F ○G ○H-○I-○J ○（a） 43 / 17 （b）
广东省汕头市金山中学高中信息技术信息学竞赛班数据结构专项培训教程07树
A A A ○○○
B ○ B ○C ○D B ○C ○D ○○ E ○C ○ ○E ○F ○G ○H ○I ○J E ○F ○G ○H ○I ○J ○F ○G ○D ○
（c） （d）
H ○树转换成二叉树的步骤如下：
I ○① 将森林中的各棵树分别转换成二叉树；
② 将所有转换而成的二叉树的树根相连；第二棵树作为第一棵 J ○（e）树的右子树，第三棵树作为第二棵树的右子树……，以第一棵树的树根为根。
算法描述如下:
如果 F＝{T1 , T2 , …, Tm} 是森林，则可按如下规则转换成一棵二叉树 B＝{root , LB , RB}。 （1）若F为空，即m＝0，则B为空树；
（2）若F非空，即m≠0，则B的根root即为森林中第一棵树的根root(T1)； B的左子树LB是第一棵树转换而成的二叉树；
B的右子树RB是从森林F’＝{T2 , T3 , …, Tm}转换而成的二叉树。 ★ 转换所得的二叉树，左支是孩子，右支是兄弟。 §7.6.2 二叉树转换成森林或树
二叉树转换成树其实是树转二叉树的逆过程，步骤如下： ① 将每个结点的右子树向逆时针方向旋转45°。 ② 删除与左子树的横向连接；
③ 断开连接后的结点与左子树为兄弟，将其与双亲相连。
如果B＝{root , LB , RB}是一棵二叉树，则可按如下规则转换成森林F＝{T1 , T2 , … , Tm}。 （1）若B为空，则F为空；
（2）若B非空，则F中第一棵树T1的根 root(T1) 即为二叉树B的根root； T1中根结点的子树森林是由B的左子树LB转换而成的森林；
F中其余的树F’＝{T2 , T3 , … , Tm} 是由B的右子树RB转换而成的森林。
【练习】将下列的树或森林转换成二叉树 （1）
A ○
B ○C ○
D ○E ○F ○G ○
H ○I ○
44 / 17
广东省汕头市金山中学高中信息技术信息学竞赛班数据结构专项培训教程07树
（2）
C I A ○○○
D ○E ○H J ○K ○L B ○○○
M F ○G ○ ○
【练习】将下列的二叉树转换成树或森林 （1） （3） A ○A ○
B ○ B ○ C ○C ○
D ○ D ○
（2） （4）
A ○A ○ B ○B ○
C ○ C ○D○
D ○E ○
（5）
A ○
B ○C ○
D ○E ○F ○G ○
H ○I ○J ○K ○L ○M ○N ○O ○
§7.7 树和森林的遍历
A E G ○○○先序遍历森林
若森林非空，可按以下规则遍历： B F H ○○○ （1）访问第一棵树的根；
C I ○○ （2）先序遍历第一棵树的子树；
（3）先序遍历余下的其它树； D J ○○对上图森林进行遍历 中序遍历森林
若森林非空，可按以下规则遍历：
（1）中序遍历森林中第一棵树的根结点
45 / 17
先序遍历序列：
A B C D E F G H I J 中序遍历序列：
B C D A F E H J I G
广东省汕头市金山中学高中信息技术信息学竞赛班数据结构专项培训教程07树
（2）访问第一棵树的根结点； （3）中序遍历余下的其它树；
§7.8 哈夫曼树及其应用 §7.8.1 扩充二叉树 · 几个基本概念
从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径； 路径上的分支数目称为路径长度；
树的路径长度是从树根到每一结点的路径长度之和；
· 扩充二叉树是指将原二叉树中每个凡缺少左、右孩子的结点，均扩充为带左、右两个孩子。 例如图7.8.1（a）中的二叉树变为扩充二叉树后如图7.8.1（b）所示，图中圆形结点是原来的，称为内部结点；方形结点是扩充结点，又称外部结点。
【图7.8.1】
（a）二叉树 （b） 扩充二叉树
内路径长度 I (从根到每一内结点的路径长度之和): I = 1 + 2 + 1 + 2 + 3 + 2 = 11
外路径长度 E (从根到每一外结点的路径长度之和): E = 3 + 3 + 2 + 3 + 4 + 4 + 3 + 3 = 25 · 一些规律：
(1) 若扩充二叉树有n个内部结点，则有 个外部结点；
(2) 扩充二叉树的内、外路径长度I、E的关系是 E＝ 。 答案： （1）n+1 (2) E=I+2n 证明：
(1). n + 1
证明： 根据二叉树性质3
（对任意一棵二叉树，如果度为2的结点数为n2，则其叶子结点数为n2+1）
扩充二叉树的内部结点的度都是2，有n个内部结点，则外部结点（即叶子）有n+1个。 证毕。
(2). E = I + 2n
证明： （数学归纳法）
当n=1时，由于只有一个内部结点， I＝0，E＝2， 所以 E＝I＋2n 假设对于所有的k，都有 E k = I k + 2 k 当 k+1时，即添加一个内部结点，设其路径长度为L， 则 I k+1 ＝ I k + L
E k+1 ＝ E k －L + 2 ( L + 1 ) ＝ E k + L + 2
＝ ( I k + 2 k ) + L + 2 ＝ I k + L + 2 k + 2
46 / 17
广东省汕头市金山中学高中信息技术信息学竞赛班数据结构专项培训教程07树
