欢迎来到三一办公! | 帮助中心 三一办公31ppt.com(应用文档模板下载平台)
三一办公
全部分类
  • 办公文档>
  • PPT模板>
  • 建筑/施工/环境>
  • 毕业设计>
  • 工程图纸>
  • 教育教学>
  • 素材源码>
  • 生活休闲>
  • 临时分类>
  • ImageVerifierCode 换一换
    首页 三一办公 > 资源分类 > PPT文档下载  

    数据结构第15讲赫夫曼树及其应用.ppt

    • 资源ID:6296871       资源大小:564KB        全文页数:30页
    • 资源格式: PPT        下载积分:15金币
    快捷下载 游客一键下载
    会员登录下载
    三方登录下载: 微信开放平台登录 QQ登录  
    下载资源需要15金币
    邮箱/手机:
    温馨提示:
    用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)
    支付方式: 支付宝    微信支付   
    验证码:   换一换

    加入VIP免费专享
     
    账号:
    密码:
    验证码:   换一换
      忘记密码?
        
    友情提示
    2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,就可以正常下载了。
    3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
    4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰。
    5、试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。

    数据结构第15讲赫夫曼树及其应用.ppt

    第6章 树和二叉树6.1 树的定义和基本术语6.2 二叉树6.3 遍历二叉树和线索二叉树6.4 树和森林6.6 赫夫曼树及其应用,6.6 赫夫曼树及其应用,1.基本术语1)路径和路径长度 若一棵树中存在一个结点序列k1,k2,kj,使得ki是kj的双亲(0ij),则称此结点序列是从ki kj的路径。从k1kj所经过的分支数称为这两点之间的路径长度,它等于路径上的结点数减1。,在许多应用中,常常将树中的结点赋上一个有着某种意义的实数,称其为该结点的权。结点的带权路径长度(WPL)规定为从树根到该结点之间的路径长度与该结点上权的乘积。,例:结点c的路径长度为2,其WPL=2*9=18,2)结点的权和带权路径长度,树中所有叶子结点的带权路径长度之和。通常记为:其中 n 表示叶子结点的数目,wi 和 li分别表示叶子结点ki的权值和根到ki之间的路径长度。,3)树的带权路径长度,4)赫夫曼(Huffman)树 又称最优二叉树。它是 n 个带权叶子结点构成的所有二叉树中,带权路径长度WPL最小的二叉树。,例:有四个叶子结点a,b,c,d,分别带权为9、4、5、2,由它们构成三棵不同的二叉树。,a)WPL=92+42522240b)WPL=4122539350c)WPL=9152432337,a,b,c,1)根据给定的n个权值w1,w2,wn,构造 n棵二叉树的集合 F=T1,T2,Tn,其中每棵二叉树中均只含一个带权值为wi的根结点,其左、右子树为空树;,4)重复(2)和(3)两步,直至F中只含一棵树为止。,3)从F中删去这两棵树,同时加入刚生成的新树;,2)在F中选取其根结点的权值为最小的两棵二叉树,分别作为左、右子树构造一棵新的二叉树,并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和;,2.构造最优树,赫夫曼算法:,3.判定树(赫夫曼树的应用之一),在解决某些判定问题时,利用赫夫曼树可以得到最佳判定算法。例:编制一将学生百分成绩按分数段分级的程序。若学生成绩分布是均匀的,可用图(a)二叉树结构来实现。,输入10000个数据,则需进行31500次比较。,学生成绩分布不是均匀的情况:,有没有一种更好的办法来减少比较次数呢?,(b),以比例数为权构造一棵哈夫曼树,如(b)判断树所示。,再将每一比较框的两次比较改为一次,可得到(c)判定树。,输入10000个数据,仅需进行22000次比较。,4.赫夫曼编码(赫夫曼树的应用之二),1)二进制编码 通信中,可以采用0、1的不同排列来表示不同的字符,称为二进制编码。发送端需要将电文中的字符序列转换成二进制的0、1序列,即编码;接受端需要把接受的0、1序列转换成对应的字符序列,即译码。,字符:A B A C C D A,电文:,A B C D的编码分别为:00、01、10、11,电文总长度为:14,如何能缩短传送电文的总长度,从而节省传送 时间呢?,若采用不等长编码,让出现频率高的字符具有较短的编码,让出现频率低的字符具有较长的编码,这样有可能缩短传送电文的总长度。,字符:A B A C C D AA B C D的编码分别为:0、00、1、01电文:0 0 0 0 1 1 0 1 0电文总长度为:9,?,无法译码!为此引入前缀编码的概念,2)前缀编码,若对某一字符集进行不等长编码,则要求字符集中任一字符的编码都不能是其他字符编码的前缀。符合此要求的编码叫做前缀编码。,如何设计前缀编码?,利用二叉树设计二进制的前缀编码,如何得到电文总长最短的二进制前缀编码呢?,0,1,假设有一棵如左图所示的二叉树,四个叶结点分别表示A、B、C、D四个字符,且约定左分支表示字符0,右分支表示字符1,则可以从根结点到叶子结点的路径上以分支字符组成的字符串作为该叶子结点的编码。可以证明,如此得到的必为二进制前缀编码。,3)赫夫曼编码,设计电文总长最短的二进制前缀编码即:以 n种字符出现的频率作权,设计一棵赫夫曼树的问题,由此得到的二进制前缀编码称赫夫曼编码。,例:设通信用的电文由字符集a,b,c,d,e,f,g,h中的字母构成,这8个字母在电文中出现的概率分别为 0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10,试为这8个字母设计哈夫曼编码。,a=1010b=00c=10000d=1001e=11f=10001g=01h=1011,b g e d a h c f,typedef struct unsigned int weight;unsigned int parent,lchild,rchild;HTNode,*HuffmanTree;/动态分配数组存储赫夫曼树typedef char*HuffmanCode;,建立赫夫曼树及求赫夫曼编码的算法,赫夫曼树没有度为1的结点,则一棵有n个叶子结点的赫夫曼树共有2n-1个结点,可以存储在一个大小为2n-1的一维数组中。由于在构造赫夫曼树之后,为求编码需从叶子结点出发走一条从叶子到根的路径;而为译码需从根出发走一条从根到叶子的路径。所以,每个结点既需知道双亲的信息,又需知道孩子结点的信息。,void HuffmanCoding(HuffmanTree,for(;iweight=0;p-parent=0;p-lchild=0;p-rchild=0;/*p=0,0,0,0;初始化HT中的内部结点 for(i=n+1;i=m;+i)/建赫夫曼树,(建立HT静态链表中的链)Select(HT,i-1,s1,s2);/在HT1i-1中选择parent/为0且weight最小的两个结点,序号分别为s1和s2 HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;,/从叶子到根逆向求赫夫曼编码 HC=(HuffmanCode)malloc(n+1)*sizeof(char*);cd=(char*)malloc(n*sizeof(char);cdn-1=0;/编码结束符 for(i=1;i=n;+i)/逐个字符求赫夫曼编码 start=n-1;/编码结束符位置 for(c=i,f=HTc.parent;f!=0;c=f,f=HTf.parent)/从叶子到根逆向求编码 if(HTf.lchild=c)cd-start=0;else cd-start=1;HCi=(char*)malloc(n-start)*sizeof(char);strcpy(HCi,/释放工作空间/HuffanCoding,例:已知某系统在通信联络中只可能出现八种字符,其概率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11,试设计Huffman编码。设权w=(5,29,7,8,14,23,3,11),n=8,则m=15 存储结构的初始状态为:,23,11,5,3,29,14,7,8,HC,0,1,0,0,0,0,0,0,1,1,1,1,1,1,cd,0,本章小结1.熟练掌握二叉树的结构特性2.熟练二叉树的各种存储结构的特点和适用范围3.遍历二叉树是二叉树各种操作的基础。要能灵 活运用遍历算法实现对二叉树的其他操作4.熟练掌握二叉树的线索化过程以及在中序线索 化树中找出给定结点的前驱和后继的方法5.熟悉树的各种存储结构及其特点,掌握数与二 叉树的转换方法6.了解最优树的特性,掌握建立最优树和哈夫曼 编码的方法。,

    注意事项

    本文(数据结构第15讲赫夫曼树及其应用.ppt)为本站会员(牧羊曲112)主动上传,三一办公仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知三一办公(点击联系客服),我们立即给予删除!

    温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。




    备案号:宁ICP备20000045号-2

    经营许可证:宁B2-20210002

    宁公网安备 64010402000987号

    三一办公
    收起
    展开