- 1、本文档共88页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
2015_SHI_DS_树和二叉树要点
操作要点1:对权值的合并、删除与替换 ——在权值集合{7,5,2,4}中,总是合并当前值最小的两个权 构造Huffman树的步骤: 注:方框表示外结点(叶子,字符对应的权值), 圆框表示内结点(合并后的权值)。 操作要点2:按左0右1对Huffman树的所有分支编号! d a i n 1 1 1 0 0 0 Huffman编码结果:d=0, i=10, a=110, n=111 WPL=1bit×7+2bit×5+3bit(2+4)=35 特点:每一码都不是另一码的前缀,绝不会错译! 称为前缀码 ——将 Huffman树 与 Huffman编码 挂钩 例2(严题集6.26③):假设用于通信的电文仅由8个字母 {a, b, c, d, e, f, g, h} 构成,它们在电文中出现的概率分别为{ 0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10},试为这8个字母设计哈夫曼编码。如果用0~7的二进制编码方案又如何? 霍夫曼编码的基本思想是:概率大的字符用短码,概率小的用长码。由于霍夫曼树的WPL最小,说明编码所需要的比特数最少。这种编码已广泛应用于网络通信中。 解:先将概率放大100倍,以方便构造哈夫曼树。权值集合 w={7, 19, 2, 6, 32, 3, 21, 10}, 按哈夫曼树构造规则(合并、删除、替换),可得到哈夫曼树。 w4={19, 21, 28, 32} 为清晰起见,重新排序为:w={2, 3, 6, 7, 10, 19, 21, 32} 2 3 5 6 w1={5, 6, 7, 10, 19, 21, 32} w2={7, 10, 11, 19, 21, 32} w3={11, 17, 19, 21, 32} 11 10 7 17 28 21 19 40 w5={28,32,40} 32 60 w6={40,60} w7={100} 100 b c a d e g f h 哈夫曼树 × × × × × × × × × × × × × × 对应的哈夫曼编码(左0右1): 2 3 5 6 11 10 7 32 17 28 21 19 40 60 100 b c a d e g f h 0 0 0 0 0 1 1 1 1 1 1 1 0 0 符 编码 频率 a 0.07 b 0.19 c 0.02 d 0.06 e 0.32 f 0.03 g 0.21 h 0.10 符 编码 频率 a 0.07 b 0.19 c 0.02 d 0.06 e 0.32 f 0.03 g 0.21 h 0.10 Huffman码的WPL=2(0.19+0.32+0.21) + 4(0.07+0.06+0.10) +5(0.02+0.03) =1.44+0.92+0.25=2.61 WPL=3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3 1100 00 11110 1110 10 11111 01 1101 000 001 010 011 100 101 110 111 二进制码 另一种结果表示: 例3:设字符集为26个英文字母,其出现频度如下表所示。 51 48 1 15 63 57 20 32 5 1 频度 z y x w v u t 字符 1 16 1 18 8 23 80 频度 p 21 f q 15 g r 47 h s o n m l k j 字符 57 103 32 22 13 64 186 频度 i e d c b a 空格 字符 先建哈夫曼树,再利用此树对报文“This program is my favorite”进行编码和译码。 要求编程实现: 提示1:霍夫曼树中各结点的结构可以定义为如下5个分量: char weight parent lchild Rchild 将整个霍夫曼树的结点存储在一个数组中:HT[1..n]; 将结点的编码存储在HC[1..n]中。 提示3:霍夫曼树如何构造?构造好之后又如何求得各结点对应的霍夫曼编码?——算法参见教材P147。 提示2:霍夫曼树的存储结构可采用顺序存储结构: 二叉树小结 1、定义和性质 2、存储结构 3、遍历 4、线索化:线索树 顺序结构 链式结构 二叉链表 三叉链表 先序线索树 中序线索树 后序线索树 树 二叉树 森林 中序遍历 后序遍历 先序遍历 霍夫曼树 霍夫曼编码 6.4 树和森林 1. 树和森林与二叉树的转换 2. 树和森林的存储方式 3. 树和森林的遍历 1. 树和森林与二叉树的转换 转换步骤: step1: 将树中同一结点的兄弟相连; step2: 保留结点的
您可能关注的文档
- DBS手术护理.ppt
- 2015-4多重序列比对及Clustal应用.ppt
- 综合性实验-食品毒理学与安全性评价.ppt
- D8_1向量及其线性运算.ppt
- 2015-2016高三英语学年度第一学期期末检测试题1.ppt
- DCS基础知识.ppt
- 2015-药物难治性癫痫.ppt
- 2015.11.C语言半期考试卷及答案副本.docx
- 综合性学习“我也追星”课件.ppt
- DCS模拟机对电站的技术支持经验介绍.pptx
- 2025年演出经纪人之演出经纪实务考试题库附参考答案【a卷】.docx
- 2024年河南省商丘市永城市马牧乡招聘社区工作者真题及答案详解1套.docx
- 心理培训课件.pptx
- 2025年演出经纪人之演出经纪实务考试题库附参考答案(实用).docx
- 2025年廉政准则试题及答案.docx
- 2025年浙江省温州市鹿城区上戍乡国民经济和社会发展第十五个五年规划.docx
- 2025年廉政准则知识竞赛试题及答案.docx
- 2024年河南省商丘市永城市马牧乡招聘社区工作者真题及答案详解一套.docx
- 2025年甘肃省嘉峪关市市辖五一街道国民经济和社会发展第十五个五年规划.docx
- 2024年河南省商丘市永城市马牧乡招聘社区工作者真题及参考答案详解一套.docx
最近下载
- 学生公寓管理年终总结.pptx
- 信息学奥赛一本通·初赛真题解析 第1章:计算机基础知识.docx VIP
- 2023《浅析徐福记食品公司的财务状况》.docx VIP
- 中级java工程师面试题及答案.doc VIP
- java中级工程师面试题及答案.doc VIP
- 冰雪旅游服务规范 .pdf VIP
- DB22_T 3073-2019 旅行社冰雪旅游接待安全管理规范.docx VIP
- 导游在冰雪旅游中的安全要求与服务技巧.pptx VIP
- 三年(2022–2024)高考数学真题分类汇编(全国通用)专题05 平面解析几何(选择题、填空题)(解析版) .pdf VIP
- DB22_T3073-2019_旅行社冰雪旅游接待安全管理规范_吉林省.docx VIP
文档评论(0)