数据结构教学课件：第六讲4二叉树_第1页
数据结构教学课件：第六讲4二叉树_第2页
数据结构教学课件：第六讲4二叉树_第3页
数据结构教学课件：第六讲4二叉树_第4页
数据结构教学课件：第六讲4二叉树_第5页
已阅读5页，还剩16页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、二叉树的应用哈夫曼树(Huffman)带权路径长度最短的树定义路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的路径长度：路径上的分支数树的路径长度：从树根到每一个结点的路径长度之和树的带权路径长度：树中所有带权结点的路径长度之和Huffman树设有n个权值w1,w2,wn，构造一棵有n个叶子结点的二叉树，每个叶子的权值为wi,则wpl最小的二叉树叫例 有4个结点，权值分别为7，5，2，4，构造有4个叶子结点的二叉树abcd7524WPL=7*2+5*2+2*2+4*2=36dcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4

2、*3=35构造Huffman树的方法Huffman算法构造Huffman树步骤根据给定的n个权值w1,w2,wn，构造n棵只有根结点的二叉树，令其权值为wj在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和在森林中删除这两棵树，同时将新得到的二叉树加入森林中重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树例a7b5c2d4a7b5c2d46a7b5c2d4611a7b5c2d461118哈夫曼编码编码：000 001 010 011 100 101这样会怎样？好处还是有的，解码方便！换个方法：目标是缩短电报文 a-0 b-1 c-

3、00 d-01 e-10 f -11 发送：abcd收到：010001 这样行吗？忽然想起一个事，上次课结束时那个例子当有多个条件判断串联起来的时候，哪种判别语句放在最前面？仔细看看，发现什么了？前缀码是变长码，比等长码形成的电报文要短，不会像一般变长码那样形成歧义。到哪找前缀码去？想要电报文短-变长码想要不产生歧义-前缀码前缀码多了，随便一个二叉树就能产生一个前缀码。关哈夫曼树什么事？哈夫曼树是二叉树，可以产生前缀码，而且可以是出现概率最大的字符离根节点越近，其编码就越短，从而导致电文短。树不一定都是二叉的，多叉的怎么处理？树确实可以用好多种方法存储起来，问题是每一种存储方式必然需要发展出一系列算法。那么前面二叉树已经研究够了，在研究多叉树似乎有点累了。好消息：所有树

人人文库> 全部分类> 行业资料 > 信息产业

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论