数据结构之赫夫曼编码教学提纲.ppt

《数据结构之赫夫曼编码教学提纲.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构之赫夫曼编码2已知二叉树结构如图所示，求求先、中、后序遍历结果画出顺序存储和链式存储结果练习adebfgchijk6.6赫夫曼树最优二叉树赫夫曼树又称为最优树，是一类带权路径长度最短的树树的路径和路径长度路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径路径长度：路径上的分支数目树的路径长度：从树根到每个结点的路径长度之和树路径长度为：2*1+3*2+1*3=11ADBFCGE36.6赫夫曼树最优二叉树带权路径长度：从结点到树根之间的路径长度与结点上权的乘积树的带权路径长度(WPL)：树中所有叶子结点的带权路径长

2、度之和WPL=2*5+3*3+2*4=27ADBFCGE5３４46.6赫夫曼树最优二叉树具有n个叶子结点(每个结点的权值为wi)的二叉树不止一棵，但在所有的这些二叉树中，必定存在一棵WPL值最小的树，称这棵树为Huffman树(或称最优树)如图是权值分别为2、3、6、7，具有4个叶子结点的二叉树236736726723(a)(b)(c)具有相同叶子结点，不同带权路径长度的二叉树56.6赫夫曼树最优二叉树它们的带权路径长度分别为：(a)WPL=22+32+62+72=36(b)WPL=21+32+63+73=47(c)WP

3、L=71+62+23+33=34其中(c)的WPL值最小，称这棵树为最优二叉树或Huffman树66.6赫夫曼树最优二叉树赫夫曼树的简单应用——百分制转五级制将0～100分转变为不及格、及格、中等、良好、优良五个级别普通方法用四次判断语句不同成绩的分布规律构造赫夫曼树，通过赫夫曼树进行判定，大大减少判断次数构造二叉树的思路：把分布比例数作为叶子权值，每个结点包含一个判断，把高权值结点放在路径短的地方，低权值放在路径长的地方76.6赫夫曼树最优二叉树赫夫曼树的简单应用——百分制转五级制将0～100分转变为不及格、及格、中等、良好、

4、优良五个级别分数的分布比例为：86.6赫夫曼树最优二叉树赫夫曼树的简单应用——百分制转五级制采用普通方法用四次判断语句若有10000个输入数据，根据分数分布比例需要31500次80%以上数据需要经过3次以上的比较才能得到结果96.6赫夫曼树最优二叉树赫夫曼树的简单应用——百分制转五级制把高比例数据先做比较，程序调整如下，106.6赫夫曼树最优二叉树赫夫曼树的简单应用——百分制转五级制改进方法中每个比较有包含两次判断，再做细化，得到如下的判定树10000个输入数据需要22000次判断116.6赫夫曼树最优二叉树赫夫曼树的简单应用——百分制

5、转五级制以5、15、40、30和10为权值，构造一颗有5个叶子的赫夫曼树，也就得到同样的这颗二叉树126.6赫夫曼树赫夫曼树的构造在Huffman树中，权值最大的结点离根最近，权值最小的结点离根最远构造算法根据给定的n个权值(w1,w2,…,wn)构成n棵二叉树的集合F={T1,T2,…,Tn}，其中每棵二叉树Ti中只有一个带树为Ti的根结点在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置其根结点的权值为其左右子树权值之和在F中删除这两棵树，同时将新得到的二叉树加入F中重复2,3，直到F只含一棵树为止136.6赫夫

6、曼树赫夫曼树的构造举例F:{7}{5}{2}{4}F:{7}{5}{6}F:{7}{11}7524初始合并{2}{4}75246F:{18}1175246合并{5}{6}5合并{7}{11}27461118146.6赫夫曼树赫夫曼编码通过赫夫曼树把电文缩短，减少传送时间编码前GOOD_G设给出一段报文：GOOD_GOOD_GOOD_GOOOOOOOO_OFF字符集合是{O,G,_,D,F}，各个字符出现的频度(次数)是W＝{15,4,4,3,2}。若给每个字符以等长编码O:000G:001_:010D:011F:100则总编码长度为(1

7、5+4+4+3+2)*3=84.156.6赫夫曼树赫夫曼编码编码后若按各个字符出现的概率不同而给予不等长编码，可望减少总编码长度。各字符{O,G,_,D,F}出现概率为{15/28,4/28,4/28,3/28,2/28},化整为{15,4,4,3,2}各字符出现概率[取整数]为{15,4,4,3,2}如果规定，Huffman树的左子树小于右子树，则可构成右图所示Huffman树415423G_FDO166.6赫夫曼树赫夫曼编码编码后令左孩子分支为编码‘0’，右孩子分支为编码‘1’将根结点到叶子结点路径上的分支编码，组合起来，作为该字符

8、的Huffman码，则可得到：O:1_:011G:010D:001F:00041542300001111G_FDO176.6赫夫曼树赫夫曼编码则总编码长度为15*1+(2+3+4+4)*3=54<84Huf