安陽一中oi7月24日夫曼樹

1、樹一、樹的含義：樹是一種帶權(quán)路徑長度最短的樹。所謂路徑長度就是某個(gè)端結(jié)點(diǎn)到樹的根結(jié)點(diǎn)的距離，等于該端結(jié)點(diǎn)的祖先數(shù)，或該結(jié)點(diǎn)所在層數(shù)減 1，用 lk 表示。二叉樹中每個(gè)端結(jié)點(diǎn)對(duì)應(yīng)的一個(gè)實(shí)數(shù)稱為該結(jié)點(diǎn)的權(quán)，用Wk 表示。定義各端結(jié)點(diǎn)的權(quán)Wk 與相應(yīng)的路徑長度lk 乘積的代數(shù)和為該二叉樹的帶權(quán)路徑長度，用 WPL 表示，即：可以證明，樹是最優(yōu)二叉樹。如給定權(quán)值5，4，7，2，3，可以生成很多棵二叉樹，其中的（A（B（7，5），C（4，D（3，2）是樹。注意： 葉子上的權(quán)值均相同時(shí)，完全二叉樹一定是最優(yōu)二叉樹，否則完全二叉樹不一定是最優(yōu)二叉樹。 最優(yōu)二叉樹中，大的葉子離根越近。 最優(yōu)二叉樹的形態(tài)不唯一

2、，WPL 最小二、樹的構(gòu)造算法：1、（1）根據(jù)給定的n 個(gè)權(quán)值W1，W2，Wnn 棵二叉樹的森林：FT1，T2，Tn。其中每棵二叉樹Ti 只有一個(gè)帶權(quán)為Wi 的根結(jié)點(diǎn)，其左右為空。（2）在F 中選取兩棵結(jié)點(diǎn)的權(quán)值最小的樹作為左右一棵新的二叉樹，且置新的二叉樹的根結(jié)點(diǎn)的權(quán)值為其左右上根結(jié)點(diǎn)的權(quán)值之和。在F 中刪除這兩棵樹，同時(shí)，將新得到的二叉樹加入F 中。重復(fù)（2）、（3），直到F 只含一棵樹為止。最后的這棵樹便是曼樹。思考題 1：假如權(quán)值為5，4，7，2，5，試據(jù)此畫出構(gòu)造樹的過程。2、算法描述為了上述算法，選用數(shù)組型的鏈表作為結(jié)構(gòu)，其類型設(shè)計(jì)如下：Type tnode=RECORD weig

3、ht：real；Lc，Rc： END；eger；tree=ARRAY1.2*n-1 of tnode; node=RECORDweight：real；adr： END；eger；A=ARRAY1.n of node;下面是在這個(gè)結(jié)構(gòu)上實(shí)現(xiàn)的構(gòu)造樹的算法：Procedure Huffmantree（VAR W：ARRAY1.nOF real;VAR TR:tree）；VAR AT:A; BENGINFOR i:=1 TO n DO實(shí)現(xiàn)第(1)步BEGINTRi.weight:=Wi;將權(quán)值放在樹葉中 TRi.Lc：=0；TRi.Rc：=0；ATi.weight:=TRi.weight;用 AT

4、存放當(dāng)前森林的根 ATi.adr:=i;END;num:=n;森林中結(jié)點(diǎn)個(gè)數(shù)K:=num+1;形成的新結(jié)點(diǎn)在TR 數(shù)組中的位置 WHILE (num=2) DO 重復(fù)實(shí)現(xiàn)第(2)、(3)步 BEGINSORTING(AT,num);按根值大小對(duì)森林中的樹進(jìn)行升序排列TRk.weight:=AT1.weigh2.weight;選擇兩棵結(jié)點(diǎn)權(quán)值最小的樹構(gòu)造新二叉樹 TRk.Lc:=AT1.adr; 樹：權(quán)值最小的樹TRk.Rc:=AT2.adr; 右：權(quán)值次小的樹AT1.weight:=TRk.weight; 新樹賦予第一AT1.adr:=k;新樹結(jié)點(diǎn)標(biāo)號(hào)AT2.weight:=ATnum.wei

5、ght;原最后樹賦予第二AT2.adr:=ATnum.adr;跟進(jìn)結(jié)點(diǎn)標(biāo)號(hào)num:=num-1; k:=k+1;END; END;刪除原最后樹增加結(jié)點(diǎn)標(biāo)號(hào)思考題 2：假如以權(quán)值5，4，7，2，5執(zhí)行上述算法，試寫出構(gòu)造樹時(shí)其結(jié)構(gòu)的變化情況。三、應(yīng)用：編碼利用樹構(gòu)造的用于通信的二進(jìn)制編碼，稱為編碼。在上世紀(jì)五十年代初就提出這種編碼時(shí)，根據(jù)字符出現(xiàn)的概率來構(gòu)造平均長度最短的編碼。它是一種變長的編碼。在編碼中，若各碼字長度嚴(yán)格按照碼字所對(duì)應(yīng)符號(hào)出現(xiàn)概率的大小的逆序排列，則編碼的平均長度是最小的。（注：碼字即為符號(hào)經(jīng)編碼后得到的編碼，其長度是因符號(hào)出現(xiàn)的概率而不同，所以說編碼是變長的編碼。）例一段電文CASTA SA，統(tǒng)計(jì)電文中字母的頻度，f(C)=1,f(S)=2,f(T)=3,f( )=3,f(A)=4，可用其頻度1，2，3，3，4為權(quán)值生成 Huffman 樹，并在每個(gè)葉子上注明對(duì)應(yīng)的字符。樹中從根到每個(gè)葉子都有一條路徑，若對(duì)路徑上的各分支進(jìn)行約定，指向樹根的分支用“0”碼表