《第9周树和二叉树（下）第5讲-哈夫曼树.pdf》由会员分享，可在线阅读，更多相关《第9周树和二叉树（下）第5讲-哈夫曼树.pdf（15页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、设二叉树具有设二叉树具有n个带权值的个带权值的叶节点叶节点，那么从根节点到各个那么从根节点到各个叶叶 节点节点的路径长度与相应节点权值的乘积的和的路径长度与相应节点权值的乘积的和，叫做二叉树的叫做二叉树的带带 权路径长度权路径长度。 n i iil wWPL 1 具有具有最小带权路径长度的二叉树称为最小带权路径长度的二叉树称为哈夫曼树（也称最优哈夫曼树（也称最优 树）树）。 1 23 WPL的计算：的计算： WPL = (2+3)2 + 11=11 9 24 7 2 4 5 5 79 相同的相同的叶节点叶节点构造出不同的二叉树构造出不同的二叉树 WPL(T1) = 7 2+5 2+2 3+4
2、3+9 2 =60 WPL(T2) = 7 4+9 4+5 3+4 2+2 1=89 （1）给定的给定的n个权值个权值W1， ，W2， ，Wn构造构造n棵只有一个叶节点的二叉树棵只有一个叶节点的二叉树， 从而得到一个二叉树的集合从而得到一个二叉树的集合F=T1，T2，Tn。 （2）在在F中选取根节点的中选取根节点的权值最小和次小权值最小和次小的两棵二叉树作为左的两棵二叉树作为左、右子树右子树 构造一棵新的二叉树构造一棵新的二叉树，这棵新的二叉树根节点的权值为其左这棵新的二叉树根节点的权值为其左、右子树根节点右子树根节点 权值权值之之和和。 （3）在集合在集合F中删除作为左中删除作为左、右子树的
3、两棵二叉树右子树的两棵二叉树，并将新建立的二叉并将新建立的二叉 树加入到集合树加入到集合F中中。 （4）重复重复（2）、（3）两两步步，当当F中只剩下一棵二叉树中只剩下一棵二叉树时时，这这棵二叉树棵二叉树 便是所要建立的哈夫曼树便是所要建立的哈夫曼树。 构造哈夫曼构造哈夫曼树的树的过程过程： 8 W= 0.05, 0.29, 0.07, 0.08, 0.14, 0.23, 0.03, 0.11 529714 8 15 23311 8 35 19 15 78 29 42 58 100 建 立 哈 夫 曼 树 示 例 建 立 哈 夫 曼 树 示 例 的 演 示 的 演 示 创建完毕创建完毕 哈夫曼
4、树的特点哈夫曼树的特点：n1=0 所以：所以：n = n0+n1+n2 = n0+n2 = 2n0- -1 规定哈夫曼树中的规定哈夫曼树中的左分支为左分支为0，右分支为右分支为1，则从根节点到每个则从根节点到每个 叶节点所经过的分支对应的叶节点所经过的分支对应的0和和1组成的序列便为该节点对应字符的组成的序列便为该节点对应字符的 编码编码。这样的编码称为这样的编码称为哈夫曼编码哈夫曼编码。 哈夫曼编码属0、1二 进制编码 哈夫曼编码哈夫曼编码特点特点：权值越大的字符编码越短，反之越长。权值越大的字符编码越短，反之越长。 29 14 23 118 35 19 15 78 29 42 58 100
5、 3:00005:000111:0017:1000 8:111123:01 29:10 14:110 0 0 0 0 10 0 1 0 1 1 1 1 1 产生哈夫曼编码示产生哈夫曼编码示 例例的演示的演示 5：00 01 在一组字符的哈夫曼编码中，不可能出现一个字符的哈夫曼在一组字符的哈夫曼编码中，不可能出现一个字符的哈夫曼 编码是另一个字符哈夫曼编码的编码是另一个字符哈夫曼编码的前缀前缀。 例如，有例如，有4个字符的编码如下：个字符的编码如下： 100，001，0，1 这是哈夫曼编码吗？这是哈夫曼编码吗？ 哈夫曼编码也称为哈夫曼编码也称为前缀编码前缀编码。 【例例7- -13】5个字符有如
6、下个字符有如下4种编码方案，不是前缀编码的种编码方案，不是前缀编码的 是是。 A01,0000,0001,001,1 B011,000,001,010,1 C000,001,010,011,100 D0,100,110,1110,1100 说明：本题为说明：本题为2014年年全国考研题全国考研题 【例例7-14】 对对n（n2）个权值均不同的字符构成哈夫曼树，）个权值均不同的字符构成哈夫曼树， 关于该树的叙述中，错误的是关于该树的叙述中，错误的是。 说明：本题为说明：本题为2010年年全国考研题全国考研题 A.该树一定是一棵完全二叉树该树一定是一棵完全二叉树 B.该树中一定没有度为该树中一定没有度为1的节点的节点 C.树中两个权值最小的节点一定是兄弟节点树中两个权值最小的节点一定是兄弟节点 D.树中任一非叶子节点的权值一定不小于下一层任一节点的树中任一非叶子节点的权值一定不小于下一层任一节点的 权值权值 思考题：思考题： 哈夫曼哈夫曼编码用什么用途？编码用什么用途？ 本章完本章完