數(shù)據(jù)結(jié)構(gòu)（雙語(yǔ)）18-哈夫曼樹(shù)的構(gòu)建及應(yīng)用-編碼譯碼

DataStructure

數(shù)據(jù)結(jié)構(gòu)計(jì)算機(jī)與信息技術(shù)系袁瑩QQ:10232828Addr:綜合樓401

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

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

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

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

電文（二進(jìn)制的0、1序列）

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

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

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

——百分制轉(zhuǎn)換成五級(jí)分制的程序可用判定樹(shù)來(lái)表示假設(shè)分布規(guī)律如下：假定以5,15,40,30,10為權(quán)構(gòu)造一棵有5個(gè)葉子節(jié)點(diǎn)的哈夫曼樹(shù)分?jǐn)?shù)0-5960-6970-7980-8990-100比例數(shù)0.050.150.400.300.10五級(jí)分制