资源描述
第六章 哈夫曼树及应用第六章 哈夫曼树及应用本讲内容1.哈夫曼树的定义哈夫曼树的定义2.哈夫曼树的构建及算法实现哈夫曼树的构建及算法实现3.哈夫曼编码及算法实现哈夫曼编码及算法实现本讲内容1.哈夫曼树的定义2.哈夫曼树的构建及算法实现3.哈哈夫曼树的定义带权路径长度最小带权路径长度最小的二叉树，称为的二叉树，称为“最优二叉树最优二叉树”，或，或哈夫曼树哈夫曼树。？如何计算树的带权路径长度？如何计算树的带权路径长度？树中所有树中所有叶子结点叶子结点的的带权路径长度之和带权路径长度之和。记作，记作，WPL=wklk。？如何计算叶子结点的带权路径长度？如何计算叶子结点的带权路径长度？结点的结点的权值权值乘以该结点的乘以该结点的路径长度路径长度。从根结点到该结点的路径上的分支数目。从根结点到该结点的路径上的分支数目。路径长度路径长度哈夫曼树的定义带权路径长度最小的二叉树，称为“最优二叉树”，27 9 75492WPL(T)=72+52+23+43+92 =60WPL(T)=74+94+53+42+21 =89 5427 9 75492WPL(T)=7哈夫曼树的构建如何构建哈夫曼树？如何构建哈夫曼树？问题：问题：根根据给定的据给定的n个权值个权值 w1,w2,wn，构造一，构造一棵以这些权值为叶子的哈夫曼树。棵以这些权值为叶子的哈夫曼树。哈夫曼算法思想哈夫曼算法思想根据给定的n个权值w1,w2,wn构成n棵二叉树的集合F=T1,T2,Tn,其中每棵二叉树Ti只有权值为Wi的根结点，其左右子树为空。在F中选取两棵根结点的权值最小的二叉树作为左右子树构造一棵新二叉树，新二叉树根结点的权值为其左右子树上根结点的权值之和。在F中删除这两棵二叉树，同时将新得到的二叉树加入F中。重复和，直到F中只剩一棵二叉树为止。哈夫曼树的构建如何构建哈夫曼树？问题：根据给定的n个权值 9例如:已知权值 W=5,6,2,9,7 5627527697671395279例如:已知权值 W=5,6,2,9,7 56713952795271667132900001111000110110111671395279527166713290000111100哈夫曼编码前缀编码前缀编码任何一个字符的编码都任何一个字符的编码都不是不是同一字符集中另一个字同一字符集中另一个字符的编码的符的编码的前缀前缀。a:110 b:00 c:111 d:10 e:01前缀编码前缀编码利用利用哈夫曼树哈夫曼树可以构可以构造一种造一种不等长不等长的的二进二进制编码制编码，并且构造所，并且构造所得的哈夫曼编码是一得的哈夫曼编码是一种种最优前缀编码最优前缀编码。从。从根到叶子的路径构成根到叶子的路径构成叶子的前缀编码。叶子的前缀编码。哈夫曼编哈夫曼编码码哈夫曼编码前缀编码任何一个字符的编码都不是同一字符集中另一个有八种字符：a b c d e f g h，其在通信联络中出现的概率分别为：0.05 0.29 0.07 0.08 0.14 0.23 0.03 0.11,试设计哈夫曼遍码。设权值 w=5,29,7,8,14,23,3,11 n=8 构造过程：构造过程：5297814 23311538297814 231178152923 11141119291423142929232342295810000000001111111a:0000 b:11c:1000 d:1001e:101 f:01g:0001 h:001有八种字符：a b c d e f g h，其在通信联络中算法演示例：字符及权值如下，例：字符及权值如下，A(6),B(7),C(1),D(5),E(2),F(8)，构建哈，构建哈夫曼树并计算哈夫曼编码，求夫曼树并计算哈夫曼编码，求WPL。icweightparentlchildrchildcode1234567891011ABCDEF67152800000000000000000000000000000000000000000000000003357784788131299166810102991011110100101101算法演示例：字符及权值如下，A(6),B(7),C(1),D1338CEABD16F290100101101从根到叶子结点的路径上编码序列构成叶子结点的哈夫曼编码。A:00 B:01 C:1110 D:110 E:1111F:10打印叶子结点的哈夫曼编码时，逆序（从根到叶子）打印哈夫曼树中每个结点的编码。1338CEABD16F290100101101从根到叶子结哈夫曼算法实现n个字符个字符c1.n权值分别为权值分别为w1.n weight1.2n-1为各结点的权值为各结点的权值parent1.2n-1为各结点的双亲为各结点的双亲lchild1.2n-1为各结点的左孩子为各结点的左孩子rchild1.2n-1为各结点的右孩子为各结点的右孩子code1.2n-1为各结点最后一位编码（左孩子为为各结点最后一位编码（左孩子为0，右孩子为，右孩子为1）含有含有n个叶子结点的哈夫曼树共有（个叶子结点的哈夫曼树共有（2*n-1）个结点。）个结点。哈夫曼算法实现n个字符c1.n权值分别为w1.nvoid huffman(char c,int w,int n,int weight,int parent,int lchild,int rchild,int code)if(n2)return;/初始化初始化for(i=1;i2*n;i+)weighti=(i=n?wi:0);for(i=1;i2*n;i+)parenti=lchildi=rchildi=0;for(i=1;i2*n;i+)codei=0;/构造赫夫曼树构造赫夫曼树/计算赫夫曼编码计算赫夫曼编码for(i=1;i2*n;i+)if(parenti!=0)codei=lchildparenti=i?0:1;void huffman(char c,int w/构造赫夫曼树for(i=n+1;i2*n;i+)/在weight1.i-1中选择两个根结点权值最小的二叉树l和rselect2min(weight,parent,i,l,r);/以l和r分别作为左右子树构造根结点为i的二叉树weighti=weightl+weightr;lchildi=l;rchildi=r;parentl=parentr=i;/构造赫夫曼树void select2min(int weight,int parent,int i,int&l,int&r)int j;l=r=0;j=1;while(j i&parentj!=0)j+;l=j;for(j=j+1;j i;j+)if(parentj=0&weightj weightl)l=j;j=1;while(j i&(parentj!=0|j=l)j+;r=j;for(j=j+1;j i;j+)if(parentj=0&j!=l&weightj r)j=l;l=r;r=j;最小权值最小权值次小权值次小权值void select2min(int weight,练习1、以数据集2，5，7，9，13为权值构造一棵Huffman树，并计算其带权路径长度。2、给定30个字符组成的电文:D D D D D A A A B E E A A F C D A A C A B B C C C B A A D D试为字符 A、B、C、D、E、F 设计哈夫曼(Huffman)编码。(1)画出相应的哈夫曼树；(2)分别列出 A、B、C、D、E、F 的哈夫曼码；(3)计算该树的带权路径长度WPL。练习
展开阅读全文