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

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

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

，直到F中只剩一棵二叉樹為止。9例如:已知權(quán)值W={5,6,2,9,7}5627527697671395276713952795271667132900001111000110110111哈夫曼編碼前綴編碼任何一個(gè)字符的編碼都不是同一字符集中另一個(gè)字符的編碼的前綴。a:110b:00c:111d:10e:01前綴編碼利用哈夫曼樹可以構(gòu)造一種不等長的二進(jìn)制編碼，并且構(gòu)造所得的哈夫曼編碼是一種最優(yōu)前綴編碼。從根到葉子的路徑構(gòu)成葉子的前綴編碼。哈夫曼編碼有八種字符：abcdefgh，其在通信聯(lián)絡(luò)中出現(xiàn)的概率分別為：0.050.290.070.080.140.230.030.11,試設(shè)計(jì)哈夫曼遍碼。設(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)建哈夫曼樹并計(jì)算哈夫曼編碼，求WPL。icweightparentlchildrchildcode1234567891011ABCDEF671528000000000000000000000000000000000000000000000000033577847881312991668101029910111101001011011338CEABD16F290100101101從根到葉子結(jié)點(diǎn)的路徑上編碼序列構(gòu)成葉子結(jié)點(diǎn)的哈夫曼編碼。A:00B:01C:1110D:110E:1111F:10打印葉子結(jié)點(diǎn)的哈夫曼編碼時(shí)，逆序（從根到葉子）打印哈夫曼樹中每個(gè)結(jié)點(diǎn)的編碼。哈夫曼算法實(shí)現(xiàn)n個(gè)字符c[1..n]權(quán)值分別為w[1..n]weight[1..2n-1]為各結(jié)點(diǎn)的權(quán)值parent[1..2n-1]為各結(jié)點(diǎn)的雙親lchild[1..2n-1]為各結(jié)點(diǎn)的左孩子rchild[1..2n-1]為各結(jié)點(diǎn)的右孩子code[1..2n-1]為各結(jié)點(diǎn)最后一位編碼（左孩子為0，右孩子為1）含有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹共有（2*n-1）個(gè)結(jié)點(diǎn)。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)造赫夫曼樹

//計(jì)算赫夫曼編碼

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]中選擇兩個(gè)根結(jié)點(diǎn)權(quán)值最小的二叉樹l和r

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

//以l和r分別作為左右子樹構(gòu)造根結(jié)點(diǎn)為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)值練習(xí)1、以數(shù)據(jù)集{2，5，7，9，13}為權(quán)值構(gòu)造一棵Huffman樹，并計(jì)算其帶權(quán)路徑長度。2、給定30個(gè)字符組成的電文:DD