树 .?—
-O二义树
2. 树转换为二叉树的步骤：
加线：在兄弟结点之间加一连线；
抹线：对任何结点，除了其最左的孩了外，抹掉该结点原先与其他孩了之间的连线； 旋转：将水平的连线和原有的连线，以树根结点为轴心，按顺时针方向粗略地旋转450。
3. 二叉树还原成树的步骤：
加线：如果某结点是双亲结点的左孩了;则将该结点的右孩了，右孩了的右孩了,……，沿着右分 支搜索到的
所有右孩子都分别与该结点的双亲用线连接起來； 抹线：抹掉原二叉树中所有结点与其右孩了的连线； 调整：将结点按层次排列，形成树的结构.
4. 森林转换成二叉树的步骤：
转换：将森林中的每一颗树转换成二叉树； 连线：将各棵转换后的二叉树的根结点相连；
旋转：将添加的水平线和原有的连线,以第一?颗树的根结点为轴心，按顺时针方向旋转450o
5. 森林转化成二叉树的规则
若森林F为空，即n = 0,则对应的二叉树B为空二叉树。
若F不空，贝IJ对应二义树B的根root (B),是F中笫一棵树T1的根root (T1)； 其左子树为LB,是由root仃:L)的子树森林｛TLL,T12,…,Tim｝转换而来的;
其右了树为RB,是由除T1外其它树构成的森林｛ T2Z T3,…,Tn ｝转换而来的。 6. 二叉树转换为森林的规则
如果B为空，则对应的森林F也为空。
如果B非空，贝I」F中笫一棵树T1的根root (T1),是二叉树B的根root(B)； T1的根的子树森林｛Til, T12, -zTlm｝,是由root的左子树LB转换而来;
F中除了 T1之外其余的树组成的森林｛T2,T3, -,Tn｝,是由root的右子树RB转换而来。 7. 森林的遍历
先根遍历时结点的 访问次序：
/T
可以分解成三部分:
ABEFCDGHIJK j 右
后根遍历时结点 的访问次序：@
1.森林中第一棵树
的根结点：
（J）
EEBCIJKHGDA
层次遍历时结点的 访问次序：
2. 森林中第一棵 树
1
幺
的子树森林；
ABCDEFGHIJK
3. 森林中其它树构
成的森林。
O森林的先序遍历
若森林不空，则
1?访问森林中第一棵树的根结点； 2. 先序遍历森林中笫一棵树的子树森林；
3. 先序遍历森林屮（除第一棵树之外）其余树构成的森林。 O森林的小序遍历
若森林不空，则
1. 中序遍历森林中第一棵树的了树森林； 2. 访问森林中第一棵树的根结点；
3. 中序遍历森林屮（除第一棵树之外）其余树构成的森林。
例如：已知权值W={ 5, 6, 2, 7, 7,7 }
⑤⑥②⑦⑦⑦
例如：已知权值 W={ 5,6,2,9,7 }
29
可以证明： 哈夫曼树是试优树！（［ 13 16 / )( V 7 C5J (
\\VPL=6X2+7X2+5X3+2X3+9X2 =65
= 18+7X10=8?
举例：
1?已知菜系统在通讯联络中只可能出现八种字符A,B,C,D,E,F,G,H,其概率分别为:
0.05, 0.29, 0.07, 0.08, 0.14, 0.23,0.03,0.11 试设计赫夫曼编码. 设权 w = { 5, 29, 7, & 14, 23, 3, 11}
A B C D E F G H
0110 0111 1110 1111
2. 数据文件压缩：
已知一个由A,B,C,D,E￡G,H等八个字符组成的文件包含10000个字符，如果对这八个字符都 按等长编码：000,001,010,011,100,101,110, 111 则文件包含的总位数为：10000X3 = 30000位 现12知八个字符在文件屮出现的频率分别为：
0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11
如果采用赫夫曼编码：0110,10,1110,1111,110,00,0111,010
则文件的总位数为:(4X0.05 + 2X0.29+4X0.07 + 4X0.08 + 3X0.14 + 2X0.23 + 4X0.03 + 3
X0.11) X 10000 = 27100 位
压缩率为：9.67% ◎课后思考题及解答：
1、 一-棵度为2的树与一-棵二叉树有何区别？
2、 已知用一维数组存放的一棵完全二叉树：ABCDEFGHIJKL,写出该二叉树的先序、中序和 后序遍历序列。 3、 假设一棵二叉树的先序序列为EBADCFHGIKJ,中序序列为ABCDEFGHIJK,请写出该二叉 树的后序遍历序
列。
4、 给定一组权值(5, 9, 11, 2, 7, 16),试设计相应的哈夫曼树。
5、 给定一棵用二叉链表表示的二叉树，其屮的指针t指向根结点，试写出从根开始，按层 次遍历二叉树的
算法，同层的结点按从左至右的次序访问。
O算法题：
1、 顺序存储方式的二叉树的建立算法。
2、 已知先根序列，递归建立的二叉树，要求输入的序列字数要补齐。 3、 已知二叉树的中根序列和先根序列，构造建立相应的二叉链表。
4、 二叉树的遍历算法(利用递归和非递归算法完成前序、中序、后序的遍历)。
第七章图 ◎课堂笔记及重要知识点:
练习:1丽出有向图G的邻接矩阵 ■邻接农.逆邻接农。
? /V ■ C C C C、
练习;
路径：1> 2. 3. 5> 6. 3 s
简单路径：1. 2. 3. 5 阿路：1> 2> 3> 仏 6, 3, 1
0 1 2 3 4 0 0 I 0 0 I 0 0 0 0
0
0 0 0 I 0 0 0 0 I
0 I I 0 0 I 0 0 0 0
简mi训路：3> 5. 6?3 路径：I. 2. 5. 7, 6. 5. 2 路径长7
邻
0 1 2 3 4 逆
接表
邻接表
L 2. 5- 7. 6 & 7, 6> 5, 2 m： r 2>
简单冋L 2. 3. I
练习：画出有向图G的十字链表。
0 Vi | I 1 V2匚 1 2 A|-P 1I3AA
2V3 j - 2 3 A| 3 0 A J
4 A A ?3 3呵| - f 4 Vs A imitB卜面有向图的DFS±成树与BFS生成树。
DFS生成栉.????
??
@ (vs)
??????/BFS
生成树
/?????■■ ? (3) @
? �)
练习：画出从顶点W开始的DFS与BFS牛成森林。
?
利用普里姆算法建立最小生成树
D
(a)无向网
，
5
?
10
i
(e)选取(B、F)
(f)选取(B、C) (g)选取(E、F)
应用克鲁斯卡尔算法构造最小生成树的过程
?
10
? ①
(f)
(g)
(h)
练习：利用Prim算法、Kruskal算法构造放小生成树<>
?2 2O ?
@ 1 2 1
2
。…①
1 ?
结果:
2?2 2O ?
《数据结构教学资料》4-10章复习资料.doc
