数据结构第六章哈夫曼树电子教案.ppt

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

1、数据结构第六章哈夫曼树《数据结构》远程通信中的一个问题设有一段信息（报文）需要编码传输：CASTCASTSATEATATASA信道发送端（编码）对接收端（解码）001000011100001000011100011000…CASTCASTSATEATATASA解决方案1等长编码：CASTCASTSATEATATASAA:000,C:001,E:010,S:011,T:100信息编码如下：001000011100001000011100011000100010000100000100000011000总编码长度为：(7+2

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√Huffman树的一个实例《数据结构》最佳

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

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

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

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

8、储在一个一维数组中。结点结构weightparentlchildrchildtypedefstruct{unsignedintweight;unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;2.可以采用动态分配的一维数组存储编码表。typedefchar**Hu