《最优二叉树哈夫曼树》由会员分享，可在线阅读，更多相关《最优二叉树哈夫曼树（11页珍藏版）》请在金锄头文库上搜索。
1、江苏省青少年信息学奥林匹克集训队第一轮函授 B4 226001 南通中学 岳军 154第四讲第四讲 最优二叉树最优二叉树哈夫曼树哈夫曼树目录目录第四讲 最优二叉树哈夫曼树.154 第七章 最优二叉树哈夫曼树.155 7.1 哈夫曼树的基本概念.156 7. 2 哈夫曼树的构造算法.158 7.3 哈夫曼树在编码问题中的应用.160 7.4 文件的编码和解码.162 7.5 哈夫曼树在判定问题中的应用.162 习题.163江苏省青少年信息学奥林匹克集训队第一轮函授 B4 226001 南通中学 岳军 155第七章第七章 最优二叉树最优二叉树哈夫曼树哈夫曼树【重点与难点】 1 带权二叉树与哈夫曼树
2、基本概念； 2 构造哈夫曼树； 3 哈夫曼编码及其算法实现。 【引入】 在实际应用中，常常要考虑一个问题：如何设计一棵二叉树，使得执行路径最短， 即算法的效率最高。 例例 7.1 快递包裹的邮资问题快递包裹的邮资问题 假设邮政局的包裹自动测试系统能够测出包裹的重量，如何设计一棵二叉树将包裹 根据重量及运距进行分类从而确定邮资。 国内快递包裹资费 单位：元 （2004 年 1 月 1 日起执行）运距（公里）首重 1000 克5000 克以内续重 每 500 克5001 克以上续重 每 500 克 5006.002.501.30 10007.003.001.6015008.003.501.9020
3、009.004.002.20250010.004.502.50300012.005.503.10400014.006.503.70500016.007.504.30600020.009.006.00 表 7.1 国家邮政局制定的快递包裹参考标准根据表 7.1 可以制定出许多种二叉树，但不同的二叉树判定的次数可能不一样，执 行的效率也不同。例例 7.2 铁球分类铁球分类 现有一批球磨机上的铁球，需要将它分成四类：直径不大于 20 的属于第一类;直径江苏省青少年信息学奥林匹克集训队第一轮函授 B4 226001 南通中学 岳军 156大于 20 而不大于 50 的属于第二类；直径大于 50 而不大
4、于 100 的属于第三类；其余的 属于第四类；假定这批球中属于第一、二、三、四类铁球的个数之比例是 1:2:3:4。 我们可以把这个判断过程表示为 图 7.1 中的两种方法：图 7.1 两种判断二叉树示意图那么究竟将这个判断过程表示成哪一个判断框，才能使其执行时间最短呢？让我们 对上述判断框做一具体的分析。 假设有 1000 个铁球，则各类铁球的个数分别为：100、200、300、400； 对于图 7.1 中的左图和右图比较的次数分别如表 7.2 所示：左图右图 序号比较式比较次数序号比较式比较次数 1a1001000 2a50600 3a0 do 由叶结点向上直到树根if HuffNodep
5、.lchild=c then cd.bitcd.start:=0else cd.bitcd.start:=1;dec (cd.start); c:=p;p:=HuffNodec.parent;end;for j:=cd.start+1 to n-1 do 保存求出的每个叶结点的哈夫曼编码和编码的起始位 begin HuffCodei.bitj:=cd.bitj; HuffCodei.start=cd.start; end; for i:=0 to n-1 do 输出每个叶子结点的哈夫曼编码begin for j:=HuffCodei.start+1 to n-1 do write(HuffCo
6、dei.bitj:10);writeln;end; end; 7.4 文件的编码和解码文件的编码和解码通过从上一节的学习，我们知道了如何利用哈夫曼树来构造字符编码。有了字符集 的哈夫曼编码表之后，对数据文件的编码过程是：依次读人文件中的字符 c，在哈夫曼 编码表 H 中找到此字符，若 Hi.ch=c，则将字符 c 转换为 Hi.bits 中存放的编码串。对压缩后的数据文件进行解码则必须借助于哈夫曼树 T，其过程是：依次读人文件 的二进制码，从哈夫曼树的根结点(即 Tm-1)出发，若当前读人 0，则走向左孩子，否 则走向右孩子。一旦到达某一叶子 Ti时便译出相应的字符 Hi.ch。然后重新从根出
7、发 继续译码，直至文件结束。7.5 哈夫曼树在判定问题中的应用哈夫曼树在判定问题中的应用在本章的引入部分，两个例子都是判定问题，这两个判定问题都可以通过构造哈夫 曼树来优化判定，以达到总的判定次数最少。 再如，要编制一个将百分制转换为五级分制的程序。显然，此程序很简单，只要利 用条件语句便可完成。江苏省青少年信息学奥林匹克集训队第一轮函授 B4 226001 南通中学 岳军 163【程序段】 if a60 then b:=badelse if a70 then b:=passelse if a80 then b:=generalelse if a90 then b:=goodelse b:=e
8、xcellent; 如果上述程序需反复使用，而且每次的输入量很大，则应考虑上述程序的质量问题， 即其操作所需要的时间。因为在实际中，学生的成绩在五个等级上的分布是不均匀的， 假设其分布规律如表 7.4 所示：分数 059 6069 7079 8089 90100 比例数 0.05 0.15 0.40 0.30 0.10 表 7.4 分数段的分布频率则 80以上的数据需进行三次或三次以上的比较才能得出结果。假定以 5，15，40，30 和 10 为权构造一棵有五个叶子结点的哈夫曼树，它可使大部分的数据经过较少的比较 次数得出结果。但由于每个判定框都有两次比较，将这两次比较分开，得到新的判定树，
9、按此判定树可写出相应的程序。请您自己画出此判定树。 假设有 10000 个输入数据，若上程序段的判定过程进行操作，则总共需进行 31500 次比较；而若新判定树的判定过程进行操作，则总共仅需进行 22000 次比较。习题习题一、解答题1 证明：在结点数大于 1 的哈夫曼树中不存在度为 1 的结点。 2 假设用于通讯的电文仅由 8 个字母组成，字母在电文中出现的频率分别为 7、19、2、6、32、3、21、10。试为这 8 个字母设计哈夫曼编码。如果用 07 这 8 个数的二进制数表示这 8 个字母也是一种编码方案，试比较这两种方法的 优劣。 3 有 7 个带权结点 a,b,c,d,e,f,g
10、分别带权 3、7、8、2、5、8、4，试以它们为 叶子结点构造一棵哈夫曼树（请按照左子树根节点的权小于等于右子树根节点 的权的次序构造） 。二、编写程序题文件压缩 compress江苏省青少年信息学奥林匹克集训队第一轮函授 B4 226001 南通中学 岳军 164【问题描述】 假设有一张黑白的二进制位图，M 行 N 列（0M,N2048） ，将位图用文件存储时 0 表示白、1 表示黑，这样的存储的文件很大，最大达 2048*2048Byte。 我们知道八位二进制可以跟有相同 ASCII 码值的一个字符的建立起对应关系，如果 将位图以字符的方式存储，理想状态下存储空间变以原来的 1/8。但这样
11、仍然很大，我 们刚刚学习了哈夫曼编码，可以先统计各字符出现的频率，然后依此进行哈夫曼编码， 这样存储又将节省不少空间。其实 JPEG 图形格式就有类似的处理方式。 现在请你对于输入的由 0、1 构成的文件，以八位为基础，先统计频率然后构造哈 夫曼树，从而进行压缩处理。处理的过程中如果出现频率相同的情况，先考虑序号小的 （即左子树节点的权小于等于右子树节点的权） 。 【输入】compress.in 第一行两个数 M、N，表示图形共有 M 行、每行 N 列，N mod 8=0。 接下是 M 行，每行有 N 个 0 或 1。 【输出】compress.out 就一行，表示压缩后形成的编码的字节数（所需存储空间，8 个二进制位为一个字 节，如果总的二进制位数 b 除以 8 有余数，则输出 b div 8+1） 。 【样例】 compress.in 8 16 0000001111000000 0000001111000000 0000001111000000 0000001111000000 0000001111000000 0000001111000000 0000001111000000 0000001111000000 compress.out 2说明：哈夫曼编码为 0101010101010101
