数据结构第六章哈夫曼树.ppt

《数据结构第六章哈夫曼树.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、6.6Huffman树及其应用王玲教学内容《数据结构》远程通信中的一个问题1最优二叉树——Huffman树2Huffman编码及其实现3《数据结构》远程通信中的一个问题设有一段信息（报文）需要编码传输：CASTCASTSATEATATASA信道发送端（编码）对接收端（解码）001000011100001000011100011000…CASTCASTSATEATATASA解决方案1等长编码：CASTCASTSATEATATASAA:000,C:001,E:010,S:011,T:100信息编码如下：0010000111000010000111000

2、11000100010000100000100000011000总编码长度为：(7+2+1+4+5)*3=57（bits）《数据结构》解决方案2不等长编码，例如：A:0,C:1,E:10,S:11,T:100信息编码如下（34bits）：1011100101110011010010010001000110出现了二义问题。采用前缀码。Huffman编码是最优前缀码，要借助Huffman树来完成编码和解码。《数据结构》《数据结构》最优二叉树——Huffman树带权路径长度WPL达到最小的二叉树即为Huffman树（最优二叉树）。1.结点的路径长度2.树

3、的路径长度：树中结点的路径长度之和3．结点的权及带权路径长度若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。4．树的带权路径长度（WPL）树的带权路径长度规定为所有叶子结点的带权路径长度之和。《数据结构》最优二叉树——Huffman树最优二叉树(Huffman树）：给定n个权值{w1,w2,…，wn},构造一棵有n个结点的二叉树，使每个叶结点带权为wi，则其中带权路径长度WPL最小的二叉树称为最优二叉树。2475(b)7524(c)754(a)2√Huffma

4、n树的一个实例《数据结构》最佳判定树考试成绩分布表Huffman树的一个实例《数据结构》不及格及格中良优<60?<70?<80?<90?0.100.150.250.350.15≥≥≥≥<<<

5、优<60?<70?<80?<90?0.100.150.250.350.15≥≥≥≥<<<

6、571213（2）457（3）2135477213745712（4）213745712（5）19以{7，2，1，4，5}为权值集合构造Huffman树。13练习：以｛9,3,7,6,12,5｝为权值构造一棵Huffman树，并计算它的WPL。《数据结构》Huffman编码及其实现回到最初的问题，传输：CASTCASTSATEATATASAA：7T：5C：2E：1S：4CE3AST7121972145《数据结构》Huffman编码及其实现将Huffman树的左子树置0，右子树置1，这样每个叶子都获得一个码字：A(7)：0T(5)：10C(2)：110

7、0E(1)：1101S(4)：111WPL=7×1+5×2+2×4+1×4+4×3=41这里的WPL就是编码的总长度。CE3AST712190000111172145解码算法：《数据结构》CE3AST71219000011117214511000111101100011110111010110101001001110CASTCASTSATEATATASA《数据结构》17Huffman编码算法实现1.有n个叶结点的Huffman树中共有m＝2n－1个结点，可将这些结点存储在一个一维数组中。结点结构weightparentlchildrchildtyp

8、edefstruct{unsignedintweight;unsignedintparent,lchild,rchild;