数据结构哈夫曼树与编码本.ppt

第六章哈夫曼树及应用

本讲内容1.哈夫曼树的定义2.哈夫曼树的构建及算法实现3.哈夫曼编码及算法实现

哈夫曼树的定义带权路径长度最小的二叉树，称为“最优二叉树”，或哈夫曼树。？如何计算树的带权路径长度？树中所有叶子结点的带权路径长度之和。记作，WPL=?wklk。？如何计算叶子结点的带权路径长度？结点的权值乘以该结点的路径长度。从根结点到该结点的路径上的分支数目。路径长度

27975492WPL(T)=7?2+5?2+2?3+4?3+9?2=60WPL(T)=7?4+9?4+5?3+4?2+2?1=8954

哈夫曼树的构建如何构建哈夫曼树？问题：根据给定的n个权值{w1,w2,…,wn}，构造一棵以这些权值为叶子的哈夫曼树。哈夫曼算法思想①根据给定的n个权值{w1,w2,…,wn}构成n棵二叉树的集合F={T1,T2,…,Tn},其中每棵二叉树Ti只有权值为Wi的根结点，其左右子树为空。②在F中选取两棵根结点的权值最小的二叉树作为左右子树构造一棵新二叉树，新二叉树根结点的权值为其左右子树上根结点的权值之和。③在F中删除这两棵二叉树，同时将新得到的二叉树参加F中。④重复②和③，直到F中只剩一棵二叉树为止。

9例如:权值W={5,6,2,9,7}562752769767139527

6713952795271667132900001111000110110111

哈夫曼编码前缀编码任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。a:110b:00c:111d:10e:01前缀编码利用哈夫曼树可以构造一种不等长的二进制编码，并且构造所得的哈夫曼编码是一种最优前缀编码。从根到叶子的路径构成叶子的前缀编码。哈夫曼编码

有八种字符：abcdefgh，其在通信联络中出现的概率分别为：0.050.290.070.080.140.230.030.11,试设计哈夫曼遍码。设权值w={5,29,7,8,14,23,3,11}n=8构造过程：52978142331153829781423117815292311141119291423142929232342295810000000001111111a:0000b:11c:1000d:1001e:101f:01g:0001h:001

算法演示例：字符及权值如下，A(6),B(7),C(1),D(5),E(2),F(8)，构建哈夫曼树并计算哈夫曼编码，求WPL。icweightparentlchildrchildcode1234567891011ABCDEF67152800000000000000000000000000000000000000000000000003357784788131299166810102991011110100101101

1338CEABD16F290100101101从根到叶子结点的路径上编码序列构成叶子结点的哈夫曼编码。A:00B:01C:1110D:110E:1111F:10打印叶子结点的哈夫曼编码时，逆序〔从根到叶子〕打印哈夫曼树中每个结点的编码。

哈夫曼算法实现n个字符c[1..n]权值分别为w[1..n]weight[1..2n-1]为各结点的权值parent[1..2n-1]为各结点的双亲lchild[1..2n-1]为各结点的左孩子rchild[1..2n-1]为各结点的右孩子code[1..2n-1]为各结点最后一位编码〔左孩子为0，右孩子为1〕含有n个叶子结点的哈夫曼树共有〔2*n-1〕个结点。

voidhuffman(charc[],intw[],intn,intweight[],intparent[],intlchild[],intrchild[],intcode[]){ if(n2)return; //初始化 for(i=1;i2*n;i++)weight[i]=(i=n?w[i]:0); for(i=1;i2*n;i++)p