版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
哈夫曼树
数据结构与算法1哈夫曼树与
哈夫曼编码
最优树的定义
如何构造最优树
前缀编码
2最优树的定义树的路径长度定义为:
树中每个结点的路径长度之和。
结点的路径长度定义为:
从根结点到该结点的路径上分支的数目。3
树的带权路径长度定义为:
树中所有叶子结点的带权路径长度之和
WPL(T)=wklk
(对所有叶子结点)。在所有含n个叶子结点、并带相同权值的m叉树中,必存在一棵其带权路径长度取最小值的树,称为“最优树”。例如:427975492WPL(T)=72+52+23+43+92=60WPL(T)=74+94+53+42+21=89545根据给定的n个权值{w1,w2,…,wn},构造n棵二叉树的集合
F={T1,T2,…,Tn},其中每棵二叉树中均只含一个带权值为wi
的根结点,其左、右子树为空树;二、如何构造最优树(1)(赫夫曼算法)以二叉树为例:6在F中选取其根结点的权值为最小的两棵二叉树,分别作为左、右子树构造一棵新的二叉树,并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和;(2)7从F中删去这两棵树,同时加入刚生成的新树;重复(2)
和(3)
两步,直至F中只含一棵树为止。(3)(4)8建立HuffmanTree(1)9HuffmanTreeConstruction(2)10指的是,任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。前缀编码
利用赫夫曼树可以构造一种不等长的二进制编码,并且构造所得的赫夫曼编码是一种最优前缀编码,即使所传电文的总长度最短。11编码及其用法LetterFreqCodeBitsC321110D42101E1200F241111K7111101L42110U37100Z211110012编码与解码CodeforDEED:Decode1011001110111101:如果一组代码中的任何一个代码都不是另一个代码的前缀,则称这组代码符合前缀特性prefixproperty.每个字母预期的空间开销:带权路径长度定义为:树中所有叶子结点的带权路径长度之和
WPL(T)=wklk
(对所有叶子结点)。13要点回顾树ADT的设计,包括树节点ADT和树
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 全球混凝土坝市场分析:市场收入将达到50.957亿美元
- 产品手绘与数字化表现 课程 三点透视(新)
- 四川省资阳市安岳中学2024-2025学年八年级上学期入学考试英语试卷(原卷版)
- 辽宁省地方标准 公共体育场馆服务规范 安全管理(报批稿)
- 科学教育活动中注重幼儿创新思维能力的培养
- 【作文指导】同课异构-学习抒情
- 第七单元测试卷-2024-2025学年统编版语文四年级上册
- 智能网联汽车技术 教案全套 赵晓敏 1.1-6.3 智能网联技术概述-高级驾驶辅助技术的主要应用
- 专题03 默写-2024年中考语文考前查缺补漏试题(深圳专用)(解析版)
- 外研新标准英语一年级起点三年级下册全册教案
- 阿片类药物课件
- 人工智能考试试题及答案
- 改革开放前后的交通变迁课件
- 人教PEP四年级上册Unit 2 My schoolbag 大单元整体教学设计
- 合奏重奏教学大纲
- 《乘法交换律和结合律》新完整版
- 2024年江苏苏豪国际集团股份有限公司招聘笔试参考题库含答案解析
- 银行同业对标分析报告
- 2024年中国华能集团有限公司招聘笔试参考题库附带答案详解
- 2024年母乳喂养ppt课件x完整版
- 《变压器结构与原》课件
评论
0/150
提交评论