![大学《数据结构》第五章:树和二叉树-第六节-哈夫曼树及其应用_第1页](http://file4.renrendoc.com/view11/M00/1B/2E/wKhkGWVxqHuAeWkIAAGNRQZWw5U805.jpg)
![大学《数据结构》第五章:树和二叉树-第六节-哈夫曼树及其应用_第2页](http://file4.renrendoc.com/view11/M00/1B/2E/wKhkGWVxqHuAeWkIAAGNRQZWw5U8052.jpg)
![大学《数据结构》第五章:树和二叉树-第六节-哈夫曼树及其应用_第3页](http://file4.renrendoc.com/view11/M00/1B/2E/wKhkGWVxqHuAeWkIAAGNRQZWw5U8053.jpg)
![大学《数据结构》第五章:树和二叉树-第六节-哈夫曼树及其应用_第4页](http://file4.renrendoc.com/view11/M00/1B/2E/wKhkGWVxqHuAeWkIAAGNRQZWw5U8054.jpg)
![大学《数据结构》第五章:树和二叉树-第六节-哈夫曼树及其应用_第5页](http://file4.renrendoc.com/view11/M00/1B/2E/wKhkGWVxqHuAeWkIAAGNRQZWw5U8055.jpg)
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
第六节哈夫曼树及其应用一、最优二叉树(哈夫曼树)1.树的路径长度树的路径长度是从树根到树中每一结点的路径长度之和。在结点数目相同的二叉树中,完全二叉树的路径长度最短。2.树的带权路径长度(WPL)结点的权:在一些应用中,赋予树中结点的一个有某种意义的实数。结点的带权路径长度:结点到树根之间的路径长度与该结点上权的乘积。树的带权路径长度(WPL):定义为树中所有叶结点的带权路径长度之和。3.最优二叉树或哈夫曼树带权路径长度WPL最小的二叉树称为最优二叉树或哈夫曼树。【例】给定4个叶子结点a,b,c和d,分别带权8,5,4和2。构造如下图所示的三棵二叉树(还有许多棵),它们的带权路径长度分别为:(a):WPL=8×3+5×3+2×1+4×2=49(b):WPL=8×3+5×2+2×3+4×1=44(c):WPL=8×1+5×2+2×3+4×3=36其中(c)树的WPL最小,可以验证,它就是哈夫曼树。二、哈夫曼算法1、构造哈夫曼树的方法:①将给定的权值按照从小到大排列成{W1,W2,…,Wm},并且构造出树林F={Tl,T2,…,Tm}。此时,其中的每棵树Ti(1≤i≤m)为左、右子树均为空的二叉树,二叉树的根结点的权值为Wi
。②把F中树根结点的权值最小的两棵二叉树T1和T2合并为一棵新的二叉树T(T的左子树为T1,右子树为T2),并令T的根结点的权值为T1和T2的根结点的权值之和,然后将T按其根结点的权值大小依次加入到树林F中。同时,从F中删去T1和T2这两棵二叉树。③重复步骤②,直到构造成一棵哈夫曼树。【真题选解】(例题•填空题)用6个权值分别为6、13、18、30、7和16的结点构造一棵哈夫曼(Huffman)树,该树的带权路径长度为_________。隐藏答案【解析】用6个权值构造的过程如下图构造的哈夫曼树的带权路径长度=(16+18+30)*2+13*3+(6+7)*4=2192、哈夫曼树的特点:①在哈夫曼树中,权值越大的叶子离根结点越近。②若有n0个权值,需要进行n0-1次合并,构造成为哈夫曼树。③哈夫曼树没有度为1的结点。④由n0个权值构成的哈夫曼树,叶结点数为n0,度为2的结点数为n0-1,结点总数为n0+n2=n0+n0-1=2n0-1。⑤给定一组权值,构造出的哈夫曼树的形态可能不唯一,但它们的带权路径长度都一样。三、哈夫曼编码1、编码的概念(1)编码和解码数据压缩过程称为编码。即将文件中的每个字符均转换为一个唯一的二进制位串。数据解压过程称为解码。即将二进制位串转换为对应的字符。(2)前缀码方案对字符集进行编码时,要求字符集中任一字符的编码都不是其它字符的编码的前缀,这种编码称为前缀(编)码。【真题选解】(例题•单选题)下述编码中不是前缀码的是()A.(00,01,10,11)B.(0,1,00,11)C.(0,10,110,111)D.(1,01,000,001)隐藏答案【答案】B【解析】四个选项中除选项B外,其它三个选项的编码满足任一字符的编码都不是其它字符的编码的前缀。2、哈夫曼编码设计电文总长最短的二进制前缀编码,就是以n种字符出现的频率作为权构造一棵哈夫曼树,由哈夫曼树求得的编码就是哈夫曼编码。【真题选解】(例题•算法题)假设通信电文使用的字符集为{a,b,c,d,e,f,g,h},各字符在电文中出现的频度分别为:7,26,2,28,13,10,3,11,试为这8个字符设计哈夫曼编码。要求:(1)画出你所构造的哈夫曼树(要求树中左孩子结点的权值不大于右孩子结点的权值);(2)按左分支为0和右分支为1的规则,分别写出与每个字符对应的编码。隐藏答案【解析】先按照权值构造哈夫曼树,注意要满足题目的要求:树中左孩子结点的权值不大于右孩子结点的权值。构造过程如下图:到这里就很容易写出每个字符的哈夫曼编码了。【答案】(1)(2)各字符的编码:a(0101),b(10),c(01000),d(11),e(011),f(000)g(01001)h(001)注意:每个字符的编码都不是另外一个编码的前缀。当前讲授本章小结本章首先介绍了一般树和二叉树的基本概念。主要介绍了四种不同的遍历二叉树算法,前三种算法的主要区别在
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 《买水果》教案含反思
- iOS程序员面试分类模拟11
- 《行政职业能力测验》2022年公务员考试哈尔滨市通河县巅峰冲刺试卷含解析
- 2024年医用磁共振成像设备项目合作计划书
- 2024年跑道磨擦系数测试设备合作协议书
- 2024年基础外科手术器械项目合作计划书
- 2024年医用基础设备器具项目合作计划书
- 2024年阻沙固沙网项目发展计划
- 2024年电子脂肪秤项目建议书
- 教学计划(模板六篇)
- 2024年武汉离婚协议标准模板(二篇)
- GB/T 43928-2024宇航用商业现货(COTS)器件保证指南
- 标准的中央空调保养合同范文 2024
- 口腔牙体牙髓病的护理
- 2024年广东广州市荔湾区社区开展专职工作人员招聘笔试冲刺题(带答案解析)
- 超星尔雅学习通《中国近现代史纲要(首都师范大学)》2024章节测试答案
- 地下矿山春节复工安全培训
- 因式分解100题及答案
- DMAIC项目改进报告
- 思想政治教育的检测评估方法.ppt
- JJG 577-2012 膜式燃气表检定规程
评论
0/150
提交评论