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

《数据结构第15讲赫夫曼树及其应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6章树和二叉树6.1树的定义和基本术语6.2二叉树6.3遍历二叉树和线索二叉树6.4树和森林6.6赫夫曼树及其应用6.6赫夫曼树及其应用1.基本术语1）路径和路径长度若一棵树中存在一个结点序列k1,k2,…,kj，使得ki是kj的双亲（0

2、c的路径长度为2，其WPL=2*9=182）结点的权和带权路径长度树中所有叶子结点的带权路径长度之和。通常记为：其中n表示叶子结点的数目，wi和li分别表示叶子结点ki的权值和根到ki之间的路径长度。acbd73983）树的带权路径长度4）赫夫曼（Huffman）树又称最优二叉树。它是n个带权叶子结点构成的所有二叉树中，带权路径长度WPL最小的二叉树。例：有四个叶子结点a,b,c,d，分别带权为9、4、5、2，由它们构成三棵不同的二叉树。acbd4952bcda4952abcd9245a）WPL=9×2+4×2＋5×2＋2×2＝40b）WPL=4×1＋2×

3、2＋5×3＋9×3＝50c）WPL=9×1＋5×2＋4×3＋2×3＝37abc1）根据给定的n个权值{w1,w2,…,wn}，构造n棵二叉树的集合F={T1,T2,…,Tn}，其中每棵二叉树中均只含一个带权值为wi的根结点,其左、右子树为空树；4)重复(2)和(3)两步，直至F中只含一棵树为止。3)从F中删去这两棵树，同时加入刚生成的新树；2)在F中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和;2.构造最优树赫夫曼算法：第一步：abcd9254ac9bd2456第二

4、步：abcd9245第三步：611第四步：a9bcd245611203.判定树(赫夫曼树的应用之一)在解决某些判定问题时，利用赫夫曼树可以得到最佳判定算法。例：编制一将学生百分成绩按分数段分级的程序。若学生成绩分布是均匀的，可用图(a)二叉树结构来实现。a<60a<70a<80a<90不及格中等良好优秀及格YNYNYNYN(a)输入10000个数据，则需进行31500次比较。分数0—5960—6970—7980—8990—99比例0.050.150.40.30.1学生成绩分布不是均匀的情况：a<60a<70a<80a<90不及格中等良好优秀及格YNYNYN

5、YN(a)有没有一种更好的办法来减少比较次数呢？70≤a<80a<60及格中等良好80≤a<9060≤a<70不及格优秀YNYYYNNN(b)不及格Ya<90a<80a<70a<60优秀中等及格良好YNNN(c)YYY以比例数为权构造一棵哈夫曼树，如（b)判断树所示。再将每一比较框的两次比较改为一次，可得到（c)判定树。输入10000个数据，仅需进行22000次比较。分数0—5960—6970—7980—8990—99比例0.050.150.40.30.14.赫夫曼编码（赫夫曼树的应用之二）1）二进制编码通信中，可以采用0、1的不同排列来表示不同的字符，称

6、为二进制编码。发送端需要将电文中的字符序列转换成二进制的0、1序列，即编码；接受端需要把接受的0、1序列转换成对应的字符序列，即译码。字符：ABACCDA电文：00010010101100ABCD的编码分别为：00、01、10、11电文总长度为：14如何能缩短传送电文的总长度，从而节省传送时间呢？若采用不等长编码，让出现频率高的字符具有较短的编码，让出现频率低的字符具有较长的编码，这样有可能缩短传送电文的总长度。字符：ABACCDAABCD的编码分别为：0、00、1、01电文：000011010电文总长度为：9?无法译码！为此引入前缀编码的概念2）前缀编码

7、若对某一字符集进行不等长编码，则要求字符集中任一字符的编码都不能是其他字符编码的前缀。符合此要求的编码叫做前缀编码。如何设计前缀编码？利用二叉树设计二进制的前缀编码如何得到电文总长最短的二进制前缀编码呢？01abcd1100假设有一棵如左图所示的二叉树，四个叶结点分别表示A、B、C、D四个字符，且约定左分支表示字符‘0’，右分支表示字符‘1’，则可以从根结点到叶子结点的路径上以分支字符组成的字符串作为该叶子结点的编码。可以证明，如此得到的必为二进制前缀编码。3）赫夫曼编码设计电文总长最短的二进制前缀编码即：以n种字符出现的频率作权，设计一棵赫夫曼树的问题，

8、由此得到的二进制前缀编码称赫夫曼编码。例：设通信用的电文由字符集{