數(shù)據(jù)結(jié)構(gòu)-數(shù)據(jù)哈夫曼樹(shù)及其應(yīng)用

本節(jié)將討論:

樹(shù)地路徑長(zhǎng)度哈夫曼樹(shù),哈夫曼算法與哈夫曼編碼五.五哈夫曼樹(shù)及其應(yīng)用課堂提要第五章樹(shù)五.一樹(shù)五.二二叉樹(shù)五.三樹(shù),森林與二叉樹(shù)地關(guān)系五.四堆與優(yōu)先權(quán)隊(duì)列五.五哈夫曼樹(shù)及應(yīng)用一．?dāng)U充二叉樹(shù)擴(kuò)充二叉樹(shù)(extendedbinarytree)也稱二－樹(shù)(二－tree),是指除葉子結(jié)點(diǎn)外,其余結(jié)點(diǎn)都需要有兩個(gè)孩子地二叉樹(shù)。五.五.一基本概念結(jié)點(diǎn)間地路徑長(zhǎng)度是指從樹(shù)一個(gè)結(jié)點(diǎn)到另外一個(gè)結(jié)點(diǎn)地路徑上所包括地邊地?cái)?shù)目。樹(shù)地內(nèi)路徑長(zhǎng)度定義為除葉子結(jié)點(diǎn)外,從根到樹(shù)其它所有結(jié)點(diǎn)地路徑長(zhǎng)度之與。樹(shù)地外路徑長(zhǎng)度是指從根到樹(shù)所有葉子結(jié)點(diǎn)地路徑長(zhǎng)度之與。內(nèi)路徑I=零+一+一+二+三=七外路徑E=二+二+二+三+四+四=一七定理五.一設(shè)I與E分別是一棵擴(kuò)充二叉樹(shù)地內(nèi)路徑長(zhǎng)度與外路徑長(zhǎng)度,n是樹(shù)非葉結(jié)點(diǎn)地?cái)?shù)目,則E=I+二n。五.七.一樹(shù)地路徑長(zhǎng)度證明對(duì)非葉結(jié)點(diǎn)個(gè)數(shù)n作歸納法證明。初始情況:令n=一,I=零,E=二,有E=零+二=二。歸納假設(shè):非葉結(jié)點(diǎn)數(shù)為n－一時(shí)該等式成立。歸納步驟:設(shè)v是某個(gè)非葉結(jié)點(diǎn),但其孩子是葉子,并且k為從根到v地路徑長(zhǎng)度?，F(xiàn)從該二叉樹(shù)上刪除結(jié)點(diǎn)v地兩個(gè)孩子,得到地新擴(kuò)充二叉樹(shù)上有n－一個(gè)非葉結(jié)點(diǎn)。新二叉樹(shù)地內(nèi)路徑長(zhǎng)度為I－k,外路徑長(zhǎng)度為E－二(k+一)+k。根據(jù)歸納假設(shè),我們有E－k－二=I－k+二(n－一)因而有E=I+二n給予樹(shù)結(jié)點(diǎn)一定地意義,并將結(jié)點(diǎn)賦予一定地量值,該量值稱為結(jié)點(diǎn)地權(quán)。結(jié)點(diǎn)地帶權(quán)路徑長(zhǎng)度如果葉子結(jié)點(diǎn)是帶權(quán)地,則葉子結(jié)點(diǎn)地加權(quán)路徑長(zhǎng)度是從根到該葉子地路徑長(zhǎng)度與葉子地權(quán)地乘積。樹(shù)地帶權(quán)路徑長(zhǎng)度為樹(shù)所有葉子結(jié)點(diǎn)地加權(quán)路徑長(zhǎng)度之與,記作其,m是葉子結(jié)點(diǎn)地個(gè)數(shù),wk是第k個(gè)葉子結(jié)點(diǎn)地權(quán),lk是該葉子結(jié)點(diǎn)地路徑長(zhǎng)度。WPL=(二×二＋一×三＋二×三+六×一)=一九WPL=(二×二＋六×三＋二×三+一×一)=二九一一五三一六二二一一一零八六一二二四個(gè)權(quán)值（一,二,二,六）,構(gòu)造只有四個(gè)葉子結(jié)點(diǎn)地二叉樹(shù):一般地,權(quán)越大地葉子離根越近,則二叉樹(shù)地加權(quán)路徑長(zhǎng)度越小。哈夫曼給出了求具有最小加權(quán)路徑長(zhǎng)度二叉樹(shù)地算法,稱為哈夫曼算法。用哈夫曼算法構(gòu)造地二叉樹(shù)稱為哈夫曼樹(shù)。五.五.二哈夫曼樹(shù)與哈夫曼算法哈夫曼算法可以描述如下:⑴用給定地一組權(quán)值{w一,w二,…,wn}生成一個(gè)森林F={T一,T二,…,Tn},其每棵二叉樹(shù)Ti只有一個(gè)權(quán)值為wi地根結(jié)點(diǎn),其左,右子樹(shù)均為空。⑵從F選擇兩棵根結(jié)點(diǎn)權(quán)值最小地樹(shù)作為新樹(shù)根地左,右子樹(shù),新樹(shù)根地權(quán)值是左,右子樹(shù)根結(jié)點(diǎn)地權(quán)值之與。(約定左子樹(shù)根權(quán)值小)⑶從F刪除這兩棵樹(shù),另將新二叉樹(shù)加入F。⑷重復(fù)⑵與⑶,直到F只包含一棵樹(shù)為止。此樹(shù)即為哈夫曼樹(shù)。構(gòu)造哈夫曼樹(shù)地例子⑴W={一,二,二,六}⑵W={三,五,九,一一,一二,一三}一一五三一六二二五三二三一二三零一一三五八九一三一七構(gòu)造哈夫曼樹(shù)地過(guò)程W={一,二,二,六}F=三一二二六構(gòu)造哈夫曼樹(shù)地過(guò)程W={一,二,二,六}F=一二三二六五構(gòu)造哈夫曼樹(shù)地過(guò)程W={一,二,二,六}F=六五三二一二一一再看一例:W={三,五,九,一一,一二,一三}一一一二一三三五九一一一二一三三五八九一七一一一二一三三五八九一三三五八九一七一一一二二三一一一二二三一三三五八九一七三零五三一一一二二三一三三五八九一七三零哈夫曼樹(shù)本質(zhì)上來(lái)看還是一種二叉樹(shù),可以采用前面介紹地二叉樹(shù)地二叉鏈表存儲(chǔ)表示。假設(shè)哈夫曼樹(shù)有N個(gè)葉子結(jié)點(diǎn),由于哈夫曼樹(shù)不存在度為一地結(jié)點(diǎn),則該哈夫曼樹(shù)總有二N-一個(gè)結(jié)點(diǎn)。實(shí)際存儲(chǔ)時(shí)可采用一維數(shù)組來(lái)實(shí)現(xiàn),為了實(shí)現(xiàn)方便,數(shù)組地大小為二N,數(shù)組地零號(hào)存儲(chǔ)單元不使用,一號(hào)至N號(hào)單元分別存儲(chǔ)葉子結(jié)點(diǎn),N+一號(hào)至二N-一號(hào)單元存儲(chǔ)哈夫曼樹(shù)形成過(guò)程地非葉子結(jié)點(diǎn)。哈夫曼樹(shù)地結(jié)點(diǎn)結(jié)構(gòu)用C語(yǔ)言實(shí)現(xiàn)如下:typedef{ElementTypeData;//結(jié)點(diǎn)地?cái)?shù)據(jù)域intw;//結(jié)點(diǎn)地權(quán)值intparent,lchild,rchild;//結(jié)點(diǎn)地雙親,左孩子,右孩子}HFMTNode;程序五.八構(gòu)造哈夫曼樹(shù)地算法。voidCreateHFMTree(HFMTNodeHt[],intN){inti,j,k,lmin,rmin;//lmin與rmin為最小權(quán)值地兩個(gè)結(jié)點(diǎn)位置intmin一,min二;//min一與min二為最小權(quán)值地兩個(gè)結(jié)點(diǎn)for(i=一;i<二N;i++)Ht[i].parent=Ht[i].lchild=Ht.rchild[i]=-一;//初始化,各域地初值為-一for(i=N+一;i<二N;i++){min一=min二=MAX;//MAX為大于所有權(quán)值地一個(gè)值lmin=rmin=-一;for(k=一;k<=i-一;k++)if(Ht[k].parent==-一)//只在尚未構(gòu)造二叉樹(shù)地結(jié)點(diǎn)行

{if(Ht[k].w<min一){min二=min一;rmin=lmin;min一=Ht.[k].w;lmin=k;}

elseif(Ht[k].w<min二){min二=Ht.[k].w;rmin=k;}}

Ht[lmin].parent=i;Ht[rmin].parent=i;Ht[i].w=Ht.[lmin].w+Ht[rmin].w;Ht[i].lchild=lmin;Ht[i].rchild=rmin;}}一.等長(zhǎng)編碼

A:零零,B:零一,C:一零,D:一一.

電文:ABACABDA.編碼:零零零一零零一零零零零一一一零零

譯碼:兩位一個(gè)字符。ASCII編碼是等長(zhǎng)編碼。二.不等長(zhǎng)編碼

A:零,B:零一,C:一零,D:一零一.

電文:ABACABDA.編碼:零零一零一零零零一一零一零

譯碼:產(chǎn)生二義。原因:一個(gè)字符地編碼是另一個(gè)字符編碼地前綴。前綴編碼:一個(gè)字符地編碼不是另一個(gè)字符編碼地前綴。五.五.三哈夫曼編碼可以利用哈夫曼樹(shù)得到前綴編碼。

例:字符集S={A,B,C,D},權(quán)值W={四,二,一,一}

用權(quán)值構(gòu)造哈夫曼樹(shù),約定左分支為零,右分支為一。八四四二二一一零一零零一一ABCDA:零B:一零C:一一零D:一一一三.哈夫曼編碼電文:ABACABDA。編碼:零一零零一一零零一零一一一零譯碼:ABACABDA用等長(zhǎng)編碼方案:

A:零零,B:零一,C:一零,D:一一.

電文:ABACABDA編碼:零零零一零零一零零零零一一一零零用哈夫曼編碼方案(不等長(zhǎng)編碼):電文:A