數(shù)據(jù)結構課件第六章第四講

哈夫曼樹(Huffman)——帶權路徑長度最短的樹定義路徑：從樹中一個結點到另一個結點之間的分支構成這兩個結點間的~路徑長度：路徑上的分支數(shù)樹的路徑長度：從樹根到每一個結點的路徑長度之和樹的帶權路徑長度：樹中所有帶權葉子結點的路徑長度之和Huffman樹——設有n個權值{w1,w2,……wn}，構造一棵有n個葉子結點的二叉樹，每個葉子的權值為wi,則wpl最小的二叉樹叫~第四講二叉樹的應用例有4個結點，權值分別為7，5，2，4，構造有4個葉子結點的二叉樹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ù)段比例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構造Huffman樹的方法——Huffman算法構造Huffman樹步驟根據(jù)給定的n個權值{w1,w2,……wn}，構造n棵只有根結點的二叉樹，令每個結點權值為wj在森林中選取兩棵根結點權值最小的樹作左右子樹，構造一棵新的二叉樹，置新二叉樹根結點權值為其左右子樹根結點權值之和在森林中刪除這兩棵樹，同時將新得到的二叉樹加入森林中重復上述兩步，直到只含一棵樹為止，這棵樹即哈夫曼樹例a7b5c2d4a7b5c2d46a7b5c2d4611a7b5c2d461118例w={5,29,7,8,14,23,3,11}51429782331114297823113588715142923358111135819142923871511358192923148715292914871529113581923421135819234229148715295811358192342291487152958100Huffman算法實現(xiàn)一棵有n個葉子結點的Huffman樹有2n-1個結點采用順序存儲結構——一維結構數(shù)組結點類型定義typedefstruct{intdata;intpa,lc,rc;}JD;哈夫曼樹的存儲結構#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;//動態(tài)分配數(shù)組存儲赫夫曼樹

typedefchar**HuffmanCode;//動態(tài)分配數(shù)組存儲赫夫曼編碼表求赫夫曼編碼的算法如下：VoidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn){//w存放n個字符的權值（均>0），構造赫夫曼樹HT，//并求出n個字符的赫夫曼編碼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){//建赫夫曼樹

//在HT[1..I-1]選擇parent為0且weight最小的兩個結點，

//其序號分別為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;}//--從葉子到根逆向求每個字符的赫夫曼編碼—HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//分配n個字符編碼的頭指針向量Cd=(char*)malloc(n*sizeof(char));//分配求編碼的工作空間Cd[n-1]=“\0”;//編碼結束符For(I=1;I<=n;++I){//逐個字符求赫夫曼編碼

start=n-1;//編碼結束符位置

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個字符編碼分配空間

strcpy(HC[I].&cd[start]);//從cd復制編碼（串）到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ù)字符出現(xiàn)頻率編碼，使電文總長最短編碼：根據(jù)字符出現(xiàn)頻率構造Huffman樹，然后將樹中結點引向其左孩子的分支標“0”，引向其右孩子的分支標“1”；每個字符的編碼即為從根到每個葉子的路徑上得到的0、1序列例要傳輸?shù)淖址疍={C,A,S,T,;}

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