数据结构课件6数据结构课件树和二叉树1章节幻灯片.ppt

* 11.假设用于通讯的电文仅由8个字母组成,字母在电文中出 现的频率分别为0.07、0.19、0.02、0.06、0.32、0.03、 0.21、0.10。试为这8种字母设计哈夫曼编码。 解： （1）以7、19、2、6、32、3、21、10为权值构造哈夫曼树。 7 19 2 6 32 3 21 10 7 19 2 6 32 3 21 10 5 * 7 19 2 6 32 3 21 10 5 11 7 19 32 21 10 17 2 6 3 5 11 19 32 21 7 10 17 2 6 3 5 11 28 * 19 32 21 7 10 17 2 6 3 5 11 28 40 19 32 21 7 10 17 2 6 3 5 11 28 40 60 19 32 21 7 10 17 2 6 3 5 11 28 40 60 100 * （2）给叶子结点进行哈夫曼编码。 权值为0.07的字母的编码为： 权值为0.19的字母的编码为： 权值为0.02的字母的编码为： 权值为0.06的字母的编码为： 权值为0.32的字母的编码为： 权值为0.03的字母的编码为： 权值为0.21的字母的编码为： 权值为0.10的字母的编码为： 0110 10 01010 0100 00 01011 11 0111 19 32 21 7 10 17 2 6 3 5 11 28 40 60 100 * A B C E D A B C D E 先序： ABCDE 后序： BDCEA 先序： ABCDE 中序： BDCEA 后序： DECBA 树 二叉树 * 总结： 树 二叉树 森林 先序 后序 先序 中序 后序 先序 中序 * 6.6 哈夫曼树及其应用 6.6.1 哈夫曼树（最优二叉树） 路径—— 从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。 路径长度—— 路径上的分支数目。 树的路径长度—— 是从树根到每一结点的路径长度之和。 例：树T A B C D E A与D的路径：AB、BC、CD A与D的路径长度：3 树T的路径长度：1+2+3+3=9 * 结点的带权路径长度—— 从该结点到树根之间的路径长度与结点上权的乘积。 树的带权路径长度—— 树中所有叶子结点的带权路径长 度之和，记为： 例：树T A B C D E F G 3 5 6 8 9 12 6 结点D的带权路径长度：2*5=10 结点G的带权路径长度：3*12=36 树T的带权路径长度： 2*5+2*6+3*12=58 * 哈夫曼树—— 假设有n个权值{w1,w2,…,wn},试构造一棵有n个叶子结点的二叉树，每个叶子结点带权为Wi，则其中带权路径长度WPL最小的二叉树称做哈夫曼树。 例：有4个权值{7,5,2,4}，试构造一棵有4个叶子结点的哈夫曼树。 A B C D 7 5 2 4 C D A B 7 5 2 4 D A C B 7 5 4 2 （1）WPL=2*7+2*5+2*2+2*4=36 （2）WPL=3*7+3*5+1*2+2*4=46 （3）WPL=1*7+2*5+3*2+3*4=35 …… * 例如：要求编写一个将百分制转换成五分制的程序。 程序段： if (a60) b=‘bad’; else if ( a70) b=‘pass’; else if ( a80) b=‘general’; else if (a90) b=‘good’; else b=‘excellent’; 哈夫曼树的应用： a60: 不及格 60=a70:及格 70=a80:中等 80=a90:良好 90=a:优秀 * 判定树： a60 a70 a80 a90 exce gener pass bad good Y N Y Y Y N N N 程序段： if (a60) b=‘bad’; else if ( a70) b=‘pass’; else if ( a80) b=‘general’; else if (a90) b=‘good’; else b=‘excellent’; * 假设学生的成绩在五个等级上的分布是不均匀的，其