數(shù)據(jù)結(jié)構(gòu)哈夫曼樹與編碼本資料課件

第六章哈夫曼樹及應(yīng)用本講內(nèi)容1.哈夫曼樹的定義2.哈夫曼樹的構(gòu)建及算法實現(xiàn)3.哈夫曼編碼及算法實現(xiàn)哈夫曼樹的定義帶權(quán)路徑長度最小的二叉樹，稱為“最優(yōu)二叉樹”，或哈夫曼樹。？如何計算樹的帶權(quán)路徑長度？樹中所有葉子結(jié)點的帶權(quán)路徑長度之和。記作，WPL=wklk

。？如何計算葉子結(jié)點的帶權(quán)路徑長度？結(jié)點的權(quán)值乘以該結(jié)點的路徑長度。從根結(jié)點到該結(jié)點的路徑上的分支數(shù)目。路徑長度27975492WPL(T)=72+52+23+43+92=60WPL(T)=74+94+53+42+21=8954哈夫曼樹的構(gòu)建如何構(gòu)建哈夫曼樹？問題：根據(jù)給定的n個權(quán)值{w1,w2,…,wn}，構(gòu)造一棵以這些權(quán)值為葉子的哈夫曼樹。哈夫曼算法思想①根據(jù)給定的n個權(quán)值{w1,w2,…,wn}構(gòu)成n棵二叉樹的集合F={T1,T2,…,Tn},其中每棵二叉樹Ti只有權(quán)值為Wi的根結(jié)點，其左右子樹為空。②在F中選取兩棵根結(jié)點的權(quán)值最小的二叉樹作為左右子樹構(gòu)造一棵新二叉樹，新二叉樹根結(jié)點的權(quán)值為其左右子樹上根結(jié)點的權(quán)值之和。③在F中刪除這兩棵二叉樹，同時將新得到的二叉樹加入F中。④重復②和③

，直到F中只剩一棵二叉樹為止。9例如:已知權(quán)值W={5,6,2,9,7}5627527697671395276713952795271667132900001111000110110111哈夫曼編碼前綴編碼任何一個字符的編碼都不是同一字符集中另一個字符的編碼的前綴。a:110b:00c:111d:10e:01前綴編碼利用哈夫曼樹可以構(gòu)造一種不等長的二進制編碼，并且構(gòu)造所得的哈夫曼編碼是一種最優(yōu)前綴編碼。從根到葉子的路徑構(gòu)成葉子的前綴編碼。哈夫曼編碼有八種字符：abcdefgh，其在通信聯(lián)絡(luò)中出現(xiàn)的概率分別為：0.050.290.070.080.140.230.030.11,試設(shè)計哈夫曼遍碼。設(shè)權(quán)值w={5,29,7,8,14,23,3,11}n=8

構(gòu)造過程：52978142331153829781423117815292311141119291423142929232342295810000000001111111a:0000b:11c:1000d:1001e:101f:01g:0001h:001算法演示例：字符及權(quán)值如下，A(6),B(7),C(1),D(5),E(2),F(8)，構(gòu)建哈夫曼樹并計算哈夫曼編碼，求WPL。icweightparentlchildrchildcode1234567891011ABCDEF671528000000000000000000000000000000000000000000000000033577847881312991668101029910111101001011011338CEABD16F290100101101從根到葉子結(jié)點的路徑上編碼序列構(gòu)成葉子結(jié)點的哈夫曼編碼。A:00B:01C:1110D:110E:1111F:10打印葉子結(jié)點的哈夫曼編碼時，逆序（從根到葉子）打印哈夫曼樹中每個結(jié)點的編碼。哈夫曼算法實現(xiàn)n個字符c[1..n]權(quán)值分別為w[1..n]weight[1..2n-1]為各結(jié)點的權(quán)值parent[1..2n-1]為各結(jié)點的雙親lchild[1..2n-1]為各結(jié)點的左孩子rchild[1..2n-1]為各結(jié)點的右孩子code[1..2n-1]為各結(jié)點最后一位編碼（左孩子為0，右孩子為1）含有n個葉子結(jié)點的哈夫曼樹共有（2*n-1）個結(jié)點。voidhuffman(charc[],intw[],intn,intweight[],intparent[],intlchild[],intrchild[],intcode[]){ if(n<2)return;

//初始化

for(i=1;i<2*n;i++)weight[i]=(i<=n?w[i]:0); for(i=1;i<2*n;i++)parent[i]=lchild[i]=rchild[i]=0; for(i=1;i<2*n;i++)code[i]=0;

//構(gòu)造赫夫曼樹

//計算赫夫曼編碼

for(i=1;i<2*n;i++) if(parent[i]!=0) code[i]=lchild[parent[i]]==i?0:1;}……//構(gòu)造赫夫曼樹for(i=n+1;i<2*n;i++){

//在weight[1..i-1]中選擇兩個根結(jié)點權(quán)值最小的二叉樹l和r

select2min(weight,parent,i,l,r);

//以l和r分別作為左右子樹構(gòu)造根結(jié)點為i的二叉樹

weight[i]=weight[l]+weight[r]; lchild[i]=l; rchild[i]=r; parent[l]=parent[r]=i;}

void

select2min(intweight[],intparent[],inti,int&l,int&r){intj;l=r=0;j=1;while(j<i&&parent[j]!=0) j++;l=j;for(j=j+1;j<i;j++)if(parent[j]==0&&weight[j]<weight[l])l=j;j=1;while(j<i&&(parent[j]!=0||j==l)) j++;r=j;for(j=j+1;j<i;j++)if(parent[j]==0&&j!=l&&weight[j]<weight[r])r=j;if(l>r){j=l;l=r;r=j;}}最小權(quán)值次小權(quán)值練習1、以數(shù)據(jù)集{2，5，7，9，13}為權(quán)值構(gòu)造一棵Huffman樹，并計算其帶權(quán)路徑長度。2、給定30個字符組成的電文:DD