![8哈夫曼树与哈夫曼编码课件_第1页](http://file4.renrendoc.com/view/1cfef4a203725283afcf7d9c0f8ed3c1/1cfef4a203725283afcf7d9c0f8ed3c11.gif)
![8哈夫曼树与哈夫曼编码课件_第2页](http://file4.renrendoc.com/view/1cfef4a203725283afcf7d9c0f8ed3c1/1cfef4a203725283afcf7d9c0f8ed3c12.gif)
![8哈夫曼树与哈夫曼编码课件_第3页](http://file4.renrendoc.com/view/1cfef4a203725283afcf7d9c0f8ed3c1/1cfef4a203725283afcf7d9c0f8ed3c13.gif)
![8哈夫曼树与哈夫曼编码课件_第4页](http://file4.renrendoc.com/view/1cfef4a203725283afcf7d9c0f8ed3c1/1cfef4a203725283afcf7d9c0f8ed3c14.gif)
![8哈夫曼树与哈夫曼编码课件_第5页](http://file4.renrendoc.com/view/1cfef4a203725283afcf7d9c0f8ed3c1/1cfef4a203725283afcf7d9c0f8ed3c15.gif)
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
6.8哈夫曼树与
哈夫曼编码
最优树的定义
如何构造最优树
前缀编码
赫夫曼编码
6.8哈夫曼树与
哈夫曼编码1
一、最优树的定义树的路径长度定义为:
树中每个结点的路径长度之和。结点的路径长度定义为:
从根结点到该结点的路径上分支的数目。一、最优树的定义树的路径长度定义为:结点的路径长度定义为2树的带权路径长度定义为:
树中所有叶子结点的带权路径长度之和WPL(T)=wklk(对所有叶子结点)。假设有n个权值{w1,w2,…wn},构造一棵有n个叶子结点的二叉树,每个叶子结点带权为Wi,则其中带权路径长度取最小值的二叉树称为“最优树”。例如:树的带权路径长度定义为:假设有n个权值{w1,w2,…w327975492WPL(T)=72+52+23+43+92=60WPL(T)=74+94+53+42+21=895427975492WPL(T)=74
根据给定的n个权值{w1,w2,…,wn},构造n棵二叉树的集合
F={T1,T2,…,Tn},其中每棵二叉树中均只含一个带权值为wi的根结点,其左、右子树为空树;二、如何构造最优树(1)(赫夫曼算法)以二叉树为例:根据给定的n个权值{w1,w2,…,5在F中选取其根结点的权值为最小的两棵二叉树,分别作为左、右子树构造一棵新的二叉树,并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和;(2)在F中选取其根结点的权值为最(2)6从F中删去这两棵树,同时加入刚生成的新树;重复
(2)
和
(3)
两步,直至F中只含一棵树为止。(3)(4)从F中删去这两棵树,同时加入重复(279例如:已知权值W={5,6,2,9,7}5627527697671395279例如:已知权值W={5,6,2,9,7}586713952795271667132900001111000110110111从根结点到叶子结点的路径上分支字符组成的字符串,可以作为每个叶子结点编码。约定左分支表示字符‘0’,右分支表示字符‘1’。6713952795271667132900001111009若要设计不等长的编码,则必须任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀,这种编码称为前缀编码。三、前缀编码以传送的电文为例比较等长编码和不等长编码方法:一、等长编码:电文中所需传送的字符有A、B、C、D,编码分别为00、01、10、11,若要发送‘ABACCDA’电文,则以字符串‘00010010101100’发送,根据字符对应的编码,在接收端能知道发送的电文为‘ABACCDA’。二、不等长编码:当A、B、C、D的编码分别为0、00、1、10,要发送上述电文以电文‘ABACCDA’,相应的字符串为‘000011100’,在接收端,对于子串’0000’的译法就有多种,可以是’AAAA‘、’BB’、‘ABA’、‘BAA’等等。若要设计不等长的编码,则必须任何一个字符的编码都不是同一10四、赫夫曼编码如何得到使电文总长最短的二进制前缀编码呢?假设每种字符在电文中出现的次数为wi,其编码长度为li,电文中只有n种字符,则电文总长为wili。
对应到二叉树上,置wi为叶子结点的权,li为根到叶子的路径长度,则wili恰为二叉树上带权路径长度。设计电文总长最短的二进制前缀编码即为以n种字符出现的频率作权,设计一棵赫夫曼树的问题,由此得到的二进制前缀编码称为赫夫曼编码。
四、赫夫曼编码如何得到使电文总长最短的二进11利用赫夫曼树可以构造一种不等长的二进制编码,并且构造所得的赫夫曼编码是一种最优前缀编码,即使所传电文的总长度最短。例6-2:利用赫夫曼树可以构造一种不等长的二进制编码,12
1.熟练掌握二叉树的结构特性,了解相应的证明方法。2.熟悉二叉树的各种存储结构的特点及适用范围。3.遍历二叉树是二叉树各种操作的基础。实现二叉树遍历的具体算法与所采用的存储结构有关。掌握各种遍历策略的递归算法,灵活运用遍历算法实现二叉树的其它操作。层次遍历是按另一种搜索策略进行的遍历。1.熟练掌握二叉树的结构特性,了解相应的证明方法。134.理解二叉树线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系,熟练掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。二叉树的线索化过程是基于对二叉树进行遍历,而线索二叉树上的线索又为相应的遍历提供了方便。4.理解二叉树线索化的实质是建立结点与其在相应序列中的145.熟悉树的各种存储结构及其特点,掌握树和森林与二叉树的转换方法。建立存储结构是进行其它操作的前提,因此读者应掌握1至2种建立二叉树和树的存储结构的方法。6.学会编写实现树的各种操作的算法。7.了解最优树的特性,掌握建立最优树和哈夫曼编码的方法。5.熟悉树的各种存储结构及其特点,掌握树和森林与二叉树的15复习题一棵完全二叉树上有1001个结点,其中叶子结点的个数是()。250500254505以上答案都不是答案:E复习题一棵完全二叉树上有1001个结点,其中叶子结点的个数是16以下说法错误的是()存在这样的二叉树,对它采用任何次序遍历其结点访问序列均相同。二叉树是树的特殊情形。由树转换成二叉树,其根结点的右子树总是空的。在二叉树只有一棵子树的情况下,也要明确指出该子树是左子树还是右子树。答案:B以下说法错误的是()17树的基本遍历策略可分为先根遍历和后根遍历,二叉树的基本遍历策略分为先序、中序和后序三种遍历。我们把由树转化得到的二叉树称该树对应的二叉树,则下面()是正确的。树的先根遍历序列与其对应的二叉树先序遍历序列相同。树的后根遍历序列与其对应的二叉树后序遍历序列相同。树的先根遍历序列与其对应的二叉树中序遍历序列相同。以上均不对。答案:A树的基本遍历策略可分为先根遍历和后根遍历,二叉树的基本遍历策18下面几个符号串编码集合中,不是前缀编码的是()。{0,10,110,1111}{11,10,001,101,0001}{00,010,0110,1000}{b,c,aa,ac,aba,abb,abc}答案:B下面几个符号串编码集合中,不是前缀编码的是()。19对于前序遍历与中序遍历结果相同的二叉树为(),对于前序遍历和后序遍历结果相同的二叉树为()。一般二叉树只有根结点的二叉树根结点无左孩子的二叉树根结点无右孩子的二叉树所有结点只有左子树的二叉树所有结点只有右子树的二叉树答案:F,B对于前序遍历与中序遍历结果相同的二叉树为(),对于前序遍历和20一、已知一棵完全二叉树共有892个结点,试求:1、树的高度。2、叶子结点数3、单支结点数4、最后一个非终端结点的序号。1.102.4463.14.4461.102.4463.1216.8哈夫曼树与
哈夫曼编码
最优树的定义
如何构造最优树
前缀编码
赫夫曼编码
6.8哈夫曼树与
哈夫曼编码22
一、最优树的定义树的路径长度定义为:
树中每个结点的路径长度之和。结点的路径长度定义为:
从根结点到该结点的路径上分支的数目。一、最优树的定义树的路径长度定义为:结点的路径长度定义为23树的带权路径长度定义为:
树中所有叶子结点的带权路径长度之和WPL(T)=wklk(对所有叶子结点)。假设有n个权值{w1,w2,…wn},构造一棵有n个叶子结点的二叉树,每个叶子结点带权为Wi,则其中带权路径长度取最小值的二叉树称为“最优树”。例如:树的带权路径长度定义为:假设有n个权值{w1,w2,…w2427975492WPL(T)=72+52+23+43+92=60WPL(T)=74+94+53+42+21=895427975492WPL(T)=725
根据给定的n个权值{w1,w2,…,wn},构造n棵二叉树的集合
F={T1,T2,…,Tn},其中每棵二叉树中均只含一个带权值为wi的根结点,其左、右子树为空树;二、如何构造最优树(1)(赫夫曼算法)以二叉树为例:根据给定的n个权值{w1,w2,…,26在F中选取其根结点的权值为最小的两棵二叉树,分别作为左、右子树构造一棵新的二叉树,并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和;(2)在F中选取其根结点的权值为最(2)27从F中删去这两棵树,同时加入刚生成的新树;重复
(2)
和
(3)
两步,直至F中只含一棵树为止。(3)(4)从F中删去这两棵树,同时加入重复(2289例如:已知权值W={5,6,2,9,7}5627527697671395279例如:已知权值W={5,6,2,9,7}5296713952795271667132900001111000110110111从根结点到叶子结点的路径上分支字符组成的字符串,可以作为每个叶子结点编码。约定左分支表示字符‘0’,右分支表示字符‘1’。67139527952716671329000011110030若要设计不等长的编码,则必须任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀,这种编码称为前缀编码。三、前缀编码以传送的电文为例比较等长编码和不等长编码方法:一、等长编码:电文中所需传送的字符有A、B、C、D,编码分别为00、01、10、11,若要发送‘ABACCDA’电文,则以字符串‘00010010101100’发送,根据字符对应的编码,在接收端能知道发送的电文为‘ABACCDA’。二、不等长编码:当A、B、C、D的编码分别为0、00、1、10,要发送上述电文以电文‘ABACCDA’,相应的字符串为‘000011100’,在接收端,对于子串’0000’的译法就有多种,可以是’AAAA‘、’BB’、‘ABA’、‘BAA’等等。若要设计不等长的编码,则必须任何一个字符的编码都不是同一31四、赫夫曼编码如何得到使电文总长最短的二进制前缀编码呢?假设每种字符在电文中出现的次数为wi,其编码长度为li,电文中只有n种字符,则电文总长为wili。
对应到二叉树上,置wi为叶子结点的权,li为根到叶子的路径长度,则wili恰为二叉树上带权路径长度。设计电文总长最短的二进制前缀编码即为以n种字符出现的频率作权,设计一棵赫夫曼树的问题,由此得到的二进制前缀编码称为赫夫曼编码。
四、赫夫曼编码如何得到使电文总长最短的二进32利用赫夫曼树可以构造一种不等长的二进制编码,并且构造所得的赫夫曼编码是一种最优前缀编码,即使所传电文的总长度最短。例6-2:利用赫夫曼树可以构造一种不等长的二进制编码,33
1.熟练掌握二叉树的结构特性,了解相应的证明方法。2.熟悉二叉树的各种存储结构的特点及适用范围。3.遍历二叉树是二叉树各种操作的基础。实现二叉树遍历的具体算法与所采用的存储结构有关。掌握各种遍历策略的递归算法,灵活运用遍历算法实现二叉树的其它操作。层次遍历是按另一种搜索策略进行的遍历。1.熟练掌握二叉树的结构特性,了解相应的证明方法。344.理解二叉树线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系,熟练掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。二叉树的线索化过程是基于对二叉树进行遍历,而线索二叉树上的线索又为相应的遍历提供了方便。4.理解二叉树线索化的实质是建立结点与其在相应序列中的355.熟悉树的各种存储结构及其特点,掌握树和森林与二叉树的转换方法。建立存储结构是进行其它操作的前提,因此读者应掌握1至2种建立二叉树和树的存储结构的方法。6.学会编写实现树的各种操作的算法。7.了解最优树的特性,掌握建立最优树和哈夫曼编码的方法。5.熟悉树的各种存储结构及其特点,掌握树和森林与二叉树的36复习题一棵完全二叉树上有1001个结点,其中叶子结点的个数是()。250500254505以上答案都不是答案:E复习题一棵完全二叉树上有1001个结点,其中叶子结点的个数是37以下说法错误的是()存在这样的二叉树,对它采用任何次序遍历其结点访问序列均相同。二叉树是树的特殊情形。由树转换成二叉树,其
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- +第三单元章节综合学练习题 统编版高中语文必修上册
- 2024标准合法借款合同样式
- 2024年幼儿园国庆节主题活动实施方案
- DB1505T 20-2024 医疗保障定点医药机构协议管理规范
- 第11课+応援+导学案 高中日人教版初中日语第一册
- 2024年注册监理工程师《合同管理》热身练习题
- 2024音像制品复制加工合同
- 河南省平顶山市42中学2025届初三第一次诊断考试英语试题理试题含答案
- 2024土地抵押个人借贷合同
- 2024“画廊-艺术家”代理合同的样本纲要
- 最新编教科版小学四年级科学上册实验报告单
- 养老机构常用物品清洁消毒方法和要求
- 公益性岗位人员年度考核表
- 英语书法课教学教案(共9页)
- 硫化氢——亚甲基蓝分光光度法
- 防火门安装施工组织设计方案
- 名家教语文——王君又湖心亭看雪教学实录
- 高级微观经济学数学准备.
- 保险公司的三年经营规划
- 副研究馆员个人总结.doc
- 空气潜水作业指导价格
评论
0/150
提交评论