數據結構（雙語）18-哈夫曼樹的構建及應用-編碼譯碼

DataStructure

數據結構計算機與信息技術系袁瑩QQ:10232828Addr:綜合樓401

2016年05月04日*Huffmantree一、哈夫曼樹的定義及建立

結點的路徑長度（lengthofpath）就是從根結點到每個結點的路徑長度，其值為路經上的邊數。賦予了權值的結點的路徑長度與該結點權值的乘積即為結點的帶權路徑長度（WeightedPathLengthofNode）。樹的帶權路徑長度（WeightedPathLengthofTree，縮寫為WPL）定義為：樹中所有葉子結點的帶權路徑長度之和，記為：其中n表示葉子結點數，wi表示第i個葉子結點的權值，li代表第i個葉子結點的路徑長度。WPLa=2×2+3×2+6×2+8×2=38WPLb=8×1+6×2+2×3+3×3=35WPLc=2×1+6×3+8×3+3×2=50WPLd=8×1+2×3+3×3+6×2=35哈夫曼樹（HuffmanTree）又稱最優(yōu)二叉樹，是在含有n個葉子結點，權值分別為w1，w2，……，wn的所有二叉樹中，帶權路徑長度WPL最小的二叉樹。哈夫曼（D.A.Huffman）在上世紀五十年代初便提出了一個非常簡單的算法來建立哈夫曼樹，其算法描述如下：（1）將給定的n個權值{w1，w2，...，wn}作為n個根結點的權值，構造一個具有n棵二叉樹的森林{T1，T2，...，Tn}，其中每棵二叉樹只有一個根結點；（2）在森林中選取兩棵根點權值最小的二叉樹分別作為左、右子樹，增加一個新結點作為根，從而將兩棵樹合并成一棵樹，新根結點的權值為左右子樹根結點權值之和。森林中因此也減少了一棵樹；（3）重復上面步驟（2）的處理過程，直到森林中只有一棵二叉樹為止，這棵二叉樹就是哈夫曼樹。Huffmantree從哈夫曼樹構造過程和生成結果可知，哈夫曼樹具有以下特點：（1）哈夫曼樹不唯一。（2）哈夫曼樹中只包含度為0和度為2的結點。（3）樹中權值越大的葉子結點離根結點越近。例

假設樹中葉子結點的權值為{5,29,7,8,14,23,3,11}，構造一棵哈夫曼樹。（1）將給定的8個權值作為根結點，構造具有8棵樹的森林（2）從森林中選取根點權值最小的兩棵二叉樹3、5，分別作為左右子樹，構造一棵新的二叉樹，新樹根點權值為8，森林中減少一棵樹。（3）重復步驟（2），直到森林中只剩一棵二叉樹為止。Huffmantree方便查找雙親，將哈夫曼樹的存儲結構設計為三叉鏈表。每個結點包含四個域：weight為結點的權值，lchild、rchild、parent分別為左、右孩子和雙親結點的指針。含有N個葉子結點的哈夫曼樹共有2N-1個結點，由此可定義一個長度為2N-1的數組tree來存儲哈夫曼樹，下標從1開始，0代表指針空（NULL）。weightparentlchildrchildtypedefstruct /*哈夫曼樹結點的存儲結構*/{ floatweight; /*結點的權值*/ intparent; /*雙親在數組中的下標*/ intlchild,rchild;/*左右孩子在數組中的下標*/}HufmTree;HufmTreetree[2N];在上述存儲結構上實現哈夫曼算法的過程如下：（1）將哈夫曼樹數組tree中的2N-1個結點初始化：即將各結點的權值、雙親、左孩子、右孩子均置為0。（2）讀入N個葉子結點的權值，分別存入數組tree[i]（1≤i≤N）的權值域中，構造包含N棵樹的初始森林，森林中的每棵樹只有一個根結點。（3）循環(huán)N-1次，對森林中的樹進行N-1次合并，產生N-1個新結點，依次放入數組tree[i]中（N+1≤i≤2N-1）。每次合并的步驟是：1）在當前森林的所有結點tree[j]（1≤j≤i-1）中，選取具有最小權值和次小權值的兩個根結點（parent域為0的結點），分別用p1和p2記住這兩個根結點在數組tree中的下標。2）將根為tree[p1]和tree[p2]的兩棵樹合并，使其成為新結點tree[i]的左、右孩子，得到一棵以新結點tree[i]為根的二叉樹即將tree[i].weight賦值為tree[p1].weight和tree[p2].weight之和tree[i]的左指針賦值為p1；tree[i]的右指針賦值為p2；同時將tree[p1]和tree[p2]的雙親域均賦值為i，使其指向新結點tree[i]即它們在當前森林中已不再是根結點。

二、哈夫曼編碼及譯碼在進行文字傳輸時，數據通信的發(fā)送方需要將原文中的每一個文字轉換成對應的二進制0、1序列（編碼）進行發(fā)送，接收方接收到二進制的0、1串后再還原成原文（譯碼）。其編碼和譯碼的過程如下所示：原文

電文（二進制的0、1序列）

原文常用的編碼方式有兩種：等長編碼和不等長編碼。等長編碼：ASCⅡ碼，其特點是每個字符的編碼長度相同。編碼簡單且具有唯一性，當字符集中的字符在電文中出現的頻度相等時，它是最優(yōu)的編碼。不等長編碼：字符的編碼長度不等，因此稱這種編碼方式為不等長編碼。為了使譯碼唯一，則要求字符集中任一字符的編碼都不是其他字符編碼的前面一部分，這種編碼叫做前綴（編）碼。二、哈夫曼編碼及譯碼利用二叉樹來對葉子結點進行編碼，所得的編碼一定為前綴碼。若要使報文總長最短，則利用哈夫曼樹對葉子結點進行編碼一定是最優(yōu)的編碼。哈夫曼編碼的實現方法如下：（1）利用字符集中每個字符的使用頻度作為權值構造一個哈夫曼樹；（2）從根結點開始，與左孩子的連線標上0，與右孩子的連線標上1；（3）由根到某葉子結點的路經上的0、1序列組成該葉子結點的編碼。例

假設有一個字符集包含8個字符：{a,b,c,d,e,f,g,h}，每個字符的使用頻度（權值）分別為{5,29,7,8,14,23,3,11}，為每個字符設計哈夫曼編碼。字符編碼a0001b10c1110d1111e110f01g0000h001哈夫曼編碼的實現算法首先根據字符的權值構建哈夫曼樹，然后從每個葉子結點開始不斷的向上搜索雙親結點，直到根點為止，得出字符的哈夫曼編碼。編碼的存儲結構及實現算法的C函數描述如下：typedefstruct /*哈夫曼編碼的存儲結構*/{ charbits[N]; /*保存編碼的數組*/intstart; /*編碼的有效起始位置*/charch; /*字符*/}CodeType;CodeTypecode[N+1];/*字符編碼數組*/

huffmanCode(HufmTreetree[],CodeTypecode[]) /*利用哈夫曼樹求字符的哈夫曼編碼*/{inti,c,p;for(i=1;i<=N;i++)/*N次循環(huán)，分別得到N個字符的編碼*/{ code[i].start=N;c=i;p=tree[i].parent; /*獲取字符的雙親*/while(p!=0) /*一直往上層查找，直到根結束*/{code[i].start—;if(tree[p].lchild==c)code[i].bits[code[i].start]='0';elsecode[i].bits[code[i].start]='1';c=p;p=tree[p].parent;}}}哈夫曼譯碼的實現算法與編碼過程相反，譯碼過程是從哈夫曼樹的根結點出發(fā)，逐個讀入電文中的二進制碼，若讀入0，則走向左孩子，否則走向右孩子，一旦達到葉結點，便譯出相應的字符。然后，重新從根結點出發(fā)繼續(xù)譯碼，直到二進制電文結束。decode(HufmTreetree[],CodeTypecode[]) { /*已知哈夫曼樹和哈夫曼編碼，對輸入的01碼進行譯碼*/inti=m,b; /*i=m表示從根點出發(fā)進行譯碼*/intendflag=-1; /*標識是否結束*/intyiflag; /*標識是否剛好譯出一個字符*/scanf("%d",&b); /*獲取輸入的第一個01碼*/while(b!=endflag) /*依次輸出譯出的字符，直到遇到結束符為止*/{ yiflag=0;if(b==0) i=tree[i].lchild; /*讀入0往左走*/else i=tree[i].rchild; /*讀入1往右走*/if(tree[i].lchild==0) /*走到葉子結點，譯出字符*/{printf("%c",code[i].ch);i=m; /*重新從根點出發(fā)，準備譯下一個字符*/yiflag=1;}scanf("%d",&b);}if(yiflag!=1)printf(“\nERROR\n”); /*輸入錯誤*/}if(a<60)b=“bad”;elseif(a<70)b=“pass”; elseif(a<80)b=“general”; elseif(a<90)b=“good”; elseb=“excellent”;哈夫曼樹的應用

——百分制轉換成五級分制的程序可用判定樹來表示假設分布規(guī)律如下：假定以5,15,40,30,10為權構造一棵有5個葉子節(jié)點的哈夫曼樹分數0-5960-6970-7980-8990-100比例數0.050.150.400.300.10五級分制