哈夫曼樹(shù)(Huffman)——帶權(quán)路徑長(zhǎng)度最短的樹(shù)定義路徑：從樹(shù)中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)間的~路徑長(zhǎng)度：路徑上的分支數(shù)樹(shù)的路徑長(zhǎng)度：從樹(shù)根到每一個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和樹(shù)的帶權(quán)路徑長(zhǎng)度：樹(shù)中所有帶權(quán)葉子結(jié)點(diǎn)的路徑長(zhǎng)度之和Huffman樹(shù)——設(shè)有n個(gè)權(quán)值{w1,w2,……wn}，構(gòu)造一棵有n個(gè)葉子結(jié)點(diǎn)的二叉樹(shù)，每個(gè)葉子的權(quán)值為wi,則wpl最小的二叉樹(shù)叫~第四講二叉樹(shù)的應(yīng)用例有4個(gè)結(jié)點(diǎn)，權(quán)值分別為7，5，2，4，構(gòu)造有4個(gè)葉子結(jié)點(diǎn)的二叉樹(shù)abcd7524WPL=7*2+5*2+2*2+4*2=36dcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=35Huffman樹(shù)應(yīng)用最佳判定樹(shù)等級(jí)分?jǐn)?shù)段比例ABCDE0~5960~6970~7980~8990~1000.050.150.400.300.10a<60a<90a<80a<70EYNDYNCYNBYNA70

a<80a<60CYNBYNDYNEYNA80

a<9060

a<70BACDEa<80a<70a<60a<90EYNDYNCYNBYNA構(gòu)造Huffman樹(shù)的方法——Huffman算法構(gòu)造Huffman樹(shù)步驟根據(jù)給定的n個(gè)權(quán)值{w1,w2,……wn}，構(gòu)造n棵只有根結(jié)點(diǎn)的二叉樹(shù)，令每個(gè)結(jié)點(diǎn)權(quán)值為wj在森林中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹(shù)作左右子樹(shù)，構(gòu)造一棵新的二叉樹(shù)，置新二叉樹(shù)根結(jié)點(diǎn)權(quán)值為其左右子樹(shù)根結(jié)點(diǎn)權(quán)值之和在森林中刪除這兩棵樹(shù)，同時(shí)將新得到的二叉樹(shù)加入森林中重復(fù)上述兩步，直到只含一棵樹(shù)為止，這棵樹(shù)即哈夫曼樹(shù)例a7b5c2d4a7b5c2d46a7b5c2d4611a7b5c2d461118例w={5,29,7,8,14,23,3,11}51429782331114297823113588715142923358111135819142923871511358192923148715292914871529113581923421135819234229148715295811358192342291487152958100Huffman算法實(shí)現(xiàn)一棵有n個(gè)葉子結(jié)點(diǎn)的Huffman樹(shù)有2n-1個(gè)結(jié)點(diǎn)采用順序存儲(chǔ)結(jié)構(gòu)——一維結(jié)構(gòu)數(shù)組結(jié)點(diǎn)類型定義typedefstruct{intdata;intpa,lc,rc;}JD;哈夫曼樹(shù)的存儲(chǔ)結(jié)構(gòu)#definen7#definem2*n-1typedefintdatatype;typedefstruct{floatweight;intlcjild,rchild,parent;}hufmtree;hufmtreetree[m];#defineM50#defineMAX100typedefstruct{intdata;intpa,lc,rc;}JD;voidhuffman(intn,intw[],JDt[]){inti,j,k,x1,x2,m1,m2;for(i=1;i<(2*n);i++){t[i].pa=t[i].lc=t[i].rc=0;if(i<=n)t[i].data=w[i];elset[i].data=0;}

for(i=1;i<n;i++){m1=m2=MAX;x1=x2=0;for(j=1;j<(n+i);j++){if((t[j].data<m1)&&(t[j].pa==0)){m2=m1;x2=x1;m1=t[j].data;x1=j;}elseif((t[j].data<m2)&&(t[j].pa==0)){m2=t[j].data;x2=j;}}k=n+i;t[x1].pa=t[x2].pa=k;t[k].data=m1+m2;t[k].lc=x1;t[k].rc=x2;}}Typedefstruct{Unsignedintweight;unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;//動(dòng)態(tài)分配數(shù)組存儲(chǔ)赫夫曼樹(shù)

typedefchar**HuffmanCode;//動(dòng)態(tài)分配數(shù)組存儲(chǔ)赫夫曼編碼表求赫夫曼編碼的算法如下：VoidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn){//w存放n個(gè)字符的權(quán)值（均>0），構(gòu)造赫夫曼樹(shù)HT，//并求出n個(gè)字符的赫夫曼編碼HCIf(n<=1)return;m=2*n-1;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));For(p=HT,I=1;I<=n;++i;,++p,++w)*p={*w,0,0,0};For(;I<=m;++I,++p)*p={0,0,0,0};For(I=n+1;I<=m;++I){//建赫夫曼樹(shù)

//在HT[1..I-1]選擇parent為0且weight最小的兩個(gè)結(jié)點(diǎn)，

//其序號(hào)分別為s1和s2select(HT,I=1,s1,s2);HT[s1].parent=I;HT[s2].parent=I;HT[I].lchild=s1;HT[I].rchild=s2;HT[I].weight=HT[s2].weight+HT[s2].weight;}//--從葉子到根逆向求每個(gè)字符的赫夫曼編碼—HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//分配n個(gè)字符編碼的頭指針向量Cd=(char*)malloc(n*sizeof(char));//分配求編碼的工作空間Cd[n-1]=“\0”;//編碼結(jié)束符For(I=1;I<=n;++I){//逐個(gè)字符求赫夫曼編碼

start=n-1;//編碼結(jié)束符位置

for(c=I,f=HT[I].parent;f!=0;c=f,f=HT[f].parent)//從葉子到根逆向求編碼

if(HT[f].lchild==c)cd[--start]=“0”;elsech[--start]=“1”;HT[I]=(char*)malloc(n-start)*sizeof(char));//為第I個(gè)字符編碼分配空間

strcpy(HC[I].&cd[start]);//從cd復(fù)制編碼（串）到HC}free(cd);}//HuffmanCodinglcdatarcpa12345670000000752400000000000000000(1)lcdatarcpa12345670000300752460000004000055000kx1=3,x2=4m1=2,m2=4(2)lcdatarcpa123456700003207524611000004500655600kx1=2,x2=5m1=5,m2=6(3)lcdatarcpa1234567000032175246111800004567655670kx1=1,x2=6m1=7,m2=11(4)Huffman編碼：數(shù)據(jù)通信用的二進(jìn)制編碼思想：根據(jù)字符出現(xiàn)頻率編碼，使電文總長(zhǎng)最短編碼：根據(jù)字符出現(xiàn)頻率構(gòu)造Huffman樹(shù)，然后將樹(shù)中結(jié)點(diǎn)引向其左孩子的分支標(biāo)“0”，引向其右孩子的分支標(biāo)“1”；每個(gè)字符的編碼即為從根到每個(gè)葉子的路徑上得到的0、1序列例要傳輸?shù)淖址疍={C,A,S,T,;}

字符出現(xiàn)頻率w={2,4,2,3,3}CS3364224814T;A00110110T:00;:01A:10C:110S:111譯碼：從Huffman樹(shù)根開(kāi)始，從待譯碼電文中逐位取碼。若編碼是“0”，則向左走；若編碼