哈夫曼树与其应用课件.pptVIP

6.1 树的定义和基本术语;6.6.1 最优二叉树的定义; 树的带权路径长度定义为： 树中所有叶子结点的带权路径长度之和 WPL(T) = ?wklk (对所有叶子结点);2;例如下面的程序： if(a 60) p = “bad”; else if(a 70) p = “pass”; else if(a 80) p = “general”; else if(a 90) p = “good”; else p = “excellent”;;a60;a80;那么如何构造赫夫曼树呢？赫夫曼最早给出了一个带有 一般规律的算法。算法如下： （1）根据给定的n个权值{w1,w2,…,wn}，构成n棵二叉树 的集合F={T1,T2,…,Tn}，其中每一棵二叉树Ti中只有一个 带权为wi的根结点，其左右子树为空。 （2）在F中选取两棵权值最小的树作为左右子树构造一 棵新的二叉树，且新二叉树的根结点的权值为其左右子 树是根结点权值之和。 （3）在F中删除这两棵树，同时将新 得到的二叉树加入F中。 （4）重复（2）和（3），直到F中只含一棵树为止。该树 即为赫夫曼树。;9;6;;;;;;?设计示例：;由Huffman树得Huffman编码为： T B A C S 00 01 10 110 111;在一个字符集中，任何一个字符的编码都不是另一个 字符编码的前缀，这种编码称为前缀编码。 我们可以利用二叉树来设计二进制的前缀编码。约定左分支表示字符‘0’，右分支便是字符‘1’，则可以用从根结点到叶子结点的路径上的分支字符串作为该叶子结点字符的编码。如此得到的编码比是前缀编码。 证明： 假设某一个叶子x结点的编码是另一个叶子结点y编码的前缀，说明从根结点到叶子结点y中间需经过结点x，从而说明x有左或右子树，这与x是叶子结点矛盾。 那么现在求最短的二进制编码实际上就是构造赫夫曼树的过程，由此得到的二进制编码，称赫夫曼编码。; 由于赫夫曼树中没有度为1的结点(这类树又称严格的(strict)(或正则的)二叉树), 则一棵有n个叶子结点的赫夫曼树共有2n-1个结点（因n2=n0-1)，可以存储在一个大小为2n-1的一维数组中。 如何选定结构类型？ （1）编码需要从叶子到根 （2）译码需要从根到叶子; ; ; ; ;　1. 掌握二叉树的结构特性，了解相应的证明方法。 　2. 熟悉二叉树的各种存储结构的特点及适用范围。 　3. 遍历二叉树是二叉树各种操作的基础。实现二叉树遍历的具体算法与所采用的存储结构有关。