樹(shù)、森林、二叉樹(shù)

將樹(shù)轉(zhuǎn)換成二叉樹(shù)加線(xiàn)：在兄弟之間加一連線(xiàn)抹線(xiàn)：對(duì)每個(gè)結(jié)點(diǎn)，除了其左孩子外，去除其與其余孩子之間的關(guān)系旋轉(zhuǎn)：以樹(shù)的根結(jié)點(diǎn)為軸心，將整樹(shù)順時(shí)針轉(zhuǎn)45°ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI樹(shù)轉(zhuǎn)換成的二叉樹(shù)其右子樹(shù)一定為空將二叉樹(shù)轉(zhuǎn)換成樹(shù)加線(xiàn)：若p結(jié)點(diǎn)是雙親結(jié)點(diǎn)的左孩子，則將p的右孩子，右孩子的右孩子，……沿分支找到的所有右孩子，都與p的雙親用線(xiàn)連起來(lái)抹線(xiàn)：抹掉原二叉樹(shù)中雙親與右孩子之間的連線(xiàn)調(diào)整：將結(jié)點(diǎn)按層次排列，形成樹(shù)結(jié)構(gòu)ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI森林轉(zhuǎn)換成二叉樹(shù)將各棵樹(shù)分別轉(zhuǎn)換成二叉樹(shù),形成有若干二叉樹(shù)的森林按森林中樹(shù)的先后次序，依次將后邊一棵二叉樹(shù)作為前邊一棵二叉樹(shù)根結(jié)點(diǎn)的右子樹(shù)，這樣整個(gè)森林就成了一棵二叉樹(shù)ABCDEFGHIJABCDEFGHIJABCDEFABCDEFGHIJABCDEFGHIJ二叉樹(shù)轉(zhuǎn)換成森林抹線(xiàn)：將二叉樹(shù)中根結(jié)點(diǎn)與其右孩子連線(xiàn)，及沿右分支搜索到的所有右孩子間連線(xiàn)全部抹掉，使之變成孤立的二叉樹(shù)還原：將孤立的二叉樹(shù)還原成樹(shù)ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ樹(shù)和森林的遍歷樹(shù)的遍歷遍歷——按一定規(guī)律走遍樹(shù)的各個(gè)頂點(diǎn)，且使每一頂點(diǎn)僅被訪(fǎng)問(wèn)一次，即找一個(gè)完整而有規(guī)律的走法，以得到樹(shù)中所有結(jié)點(diǎn)的一個(gè)線(xiàn)性排列常用方法按層次遍歷（廣度優(yōu)先遍歷）：先訪(fǎng)問(wèn)第一層上的結(jié)點(diǎn)，然后依次遍歷第二層，

……第n層的結(jié)點(diǎn)樹(shù)的前序遍歷（樹(shù)的先根遍歷）若樹(shù)非空，則樹(shù)的前序遍歷順序如下：①

訪(fǎng)問(wèn)樹(shù)的根結(jié)點(diǎn)；②

前序遍歷根的第一棵子樹(shù)；③

前序遍歷根的其余子樹(shù)。（2）樹(shù)的后序遍歷（樹(shù)的后根遍歷）若樹(shù)非空，則樹(shù)的前序遍歷順序如下：①

后序遍歷根的第一棵子樹(shù)；②

后序遍歷根的其他子樹(shù)；③

訪(fǎng)問(wèn)樹(shù)的根結(jié)點(diǎn)。ABCDEFGHIJKLMNO先序遍歷：后序遍歷：層次遍歷：ABEFIGCDHJKLNOMEIFGBCJKNOLMHDAABCDEFGHIJKLMNO討論：若采用“先轉(zhuǎn)換，后遍歷”方式，結(jié)果是否一樣？abdec先序遍歷：后序遍歷：中序遍歷：decbaabdecabcdebdcea1.

樹(shù)的先序遍歷與二叉樹(shù)的先序遍歷相同；2.樹(shù)的后序遍歷相當(dāng)于對(duì)應(yīng)二叉樹(shù)的中序遍歷；3.樹(shù)沒(méi)有中序遍歷，因?yàn)樽訕?shù)無(wú)左右之分。結(jié)論：先序遍歷若森林為空，返回；訪(fǎng)問(wèn)森林中第一棵樹(shù)的根結(jié)點(diǎn)；先序遍歷第一棵樹(shù)中根結(jié)點(diǎn)的子樹(shù)森林；先序遍歷除去第一棵樹(shù)之后剩余的樹(shù)構(gòu)成的森林。后序遍歷若森林為空，返回；后序遍歷森林中第一棵樹(shù)的根結(jié)點(diǎn)的子樹(shù)森林；后序遍歷除去第一棵樹(shù)之后剩余的樹(shù)構(gòu)成的森林。訪(fǎng)問(wèn)第一棵樹(shù)的根結(jié)點(diǎn)；森林的遍歷ABCDEFGHJI討論：若采用“先轉(zhuǎn)換，后遍歷”方式，結(jié)果是否相同？例如：ABCDEFGHJI先序序列：后序序列：ABCDEFGHIJBCDAFEHJIGABCDEFGHJI先序序列：中序序列：ABCDEFGHIJBCDAFEHJIG1.森林的先序遍歷與對(duì)應(yīng)二叉樹(shù)的先序遍歷相同；2.森林的后序遍歷相當(dāng)于對(duì)應(yīng)二叉樹(shù)的中序遍歷；結(jié)論：當(dāng)以二叉鏈表做樹(shù)的存儲(chǔ)結(jié)構(gòu)時(shí)，樹(shù)的先根序列和后根序列可借用二叉樹(shù)的先序遍歷和中序遍歷的算法實(shí)現(xiàn)之；對(duì)于森林也一樣。一、基本術(shù)語(yǔ)1．路徑和路徑長(zhǎng)度在一棵樹(shù)中，從一個(gè)結(jié)點(diǎn)往下可以達(dá)到的孩子或子孫結(jié)點(diǎn)之間的通路，稱(chēng)為路徑。通路中分支的數(shù)目稱(chēng)為路徑長(zhǎng)度。從樹(shù)的根結(jié)點(diǎn)到樹(shù)中每個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和稱(chēng)為樹(shù)的路徑長(zhǎng)度2．結(jié)點(diǎn)的權(quán)及帶權(quán)路徑長(zhǎng)度若將樹(shù)中結(jié)點(diǎn)賦給一個(gè)有著某種含義的數(shù)值，則這個(gè)數(shù)值稱(chēng)為該結(jié)點(diǎn)的權(quán)。結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度為：從根結(jié)點(diǎn)到該結(jié)點(diǎn)之間的路徑長(zhǎng)度與該結(jié)點(diǎn)的權(quán)的乘積。6.6哈夫曼樹(shù)3．樹(shù)的帶權(quán)路徑長(zhǎng)度樹(shù)的帶權(quán)路徑長(zhǎng)度規(guī)定為所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，記為:WPL=其中n為葉子結(jié)點(diǎn)數(shù)目，Wi為第i個(gè)葉子結(jié)點(diǎn)的權(quán)值，Li

為第i個(gè)葉子結(jié)點(diǎn)的路徑長(zhǎng)度。二、構(gòu)造哈夫曼樹(shù)1．哈夫曼樹(shù)的定義在一棵二叉樹(shù)中，若帶權(quán)路徑長(zhǎng)度達(dá)到最小，稱(chēng)這樣的二叉樹(shù)為最優(yōu)二叉樹(shù)，也稱(chēng)為哈夫曼樹(shù)(Huffmantree)。=W1L1+W2L2+…..+WnLn阮江南例有4個(gè)結(jié)點(diǎn)，權(quán)值分別為7，5，2，4，構(gòu)造有4個(gè)葉子結(jié)點(diǎn)的二叉樹(shù)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=352．哈夫曼樹(shù)的構(gòu)造假設(shè)有n個(gè)權(quán)值，則構(gòu)造出的哈夫曼樹(shù)有n個(gè)葉子結(jié)點(diǎn)。n個(gè)權(quán)值分別設(shè)為w1,w2,…,wn,則哈夫曼樹(shù)的構(gòu)造規(guī)則為：將w1,w2,…,wn按遞增次序排列成有n棵樹(shù)的森林

(每棵樹(shù)僅有一個(gè)結(jié)點(diǎn))；(2)在森林中選出兩個(gè)根結(jié)點(diǎn)的權(quán)值最小的樹(shù)合并，作為一棵新樹(shù)的左、右子樹(shù)，且新樹(shù)的根結(jié)點(diǎn)權(quán)值為其左、右子樹(shù)根結(jié)點(diǎn)權(quán)值之和；(3)從森林中刪除選取的兩棵樹(shù)，并將新樹(shù)加入森林；(4)重復(fù)(2)、(3)步，直到森林中只剩一棵樹(shù)為止，該樹(shù)即為我們所求得的哈夫曼樹(shù)。下面給出哈夫曼樹(shù)的構(gòu)造過(guò)程，假設(shè)給定的葉子結(jié)點(diǎn)的權(quán)分別為1,5,7,3，則構(gòu)造哈夫曼樹(shù)過(guò)程如圖7-24所示。

3

7

51

5

7

3

41

(a)初如森林

(b)一次合并后的森林

注：

哈夫曼樹(shù)的不是唯一的！但其最小的WPL是一定的，且葉子權(quán)值越大的離根越近。從圖7-24可知，n個(gè)權(quán)值構(gòu)造哈夫曼樹(shù)需n-1次合并，每次合并，森林中的樹(shù)數(shù)目減1，最后森林中只剩下一棵樹(shù)，即為我們求得的哈夫曼樹(shù)。構(gòu)造哈夫曼樹(shù)的模擬演示3、哈夫曼樹(shù)構(gòu)造程序一棵有n個(gè)葉子結(jié)點(diǎn)的Huffman樹(shù)有2n-1個(gè)結(jié)點(diǎn)采用順序存儲(chǔ)結(jié)構(gòu)——一維結(jié)構(gòu)數(shù)組存儲(chǔ)結(jié)點(diǎn)信息結(jié)點(diǎn)類(lèi)型定義為：typedef

struct{intweight;

int

parent,lchild,rchild;}JD;#defineMAX100voidhuffman(int

n,intw[],JDt[]){inti,j,k,x1,x2,m1,m2;for(i=1;i<(2*n);i++){t[i].parent=t[i].lchild=t[i].rchild=-1;if(i<=n)t[i].weight=w[i];elset[i].weight=0;}

for(i=1;i<n;i++){m1=m2=MAX;x1=x2=0;for(j=1;j<(n+i);j++){if((t[j].weight<m1)&&(t[j].parent==0)){m2=m1;x2=x1;m1=t[j].weight;x1=j;}elseif((t[j].weight<m2)&&(t[j].parent==0)){m2=t[j].weight;x2=j;}}k=n+i;t[x1].parent=t[x2].parent=k;t[k].weight=m1+m2;

t[k].lchild=x1;

t[k].rchild=x2;}}哈夫曼樹(shù)的算法模擬演示在遠(yuǎn)程通訊中，要將待傳字符轉(zhuǎn)換成由二進(jìn)制組成的字符串：設(shè)要傳送的字符為：ABACCDA若編碼為：A—00B—01 C—10D---11

若將編碼設(shè)計(jì)為長(zhǎng)度不等的二進(jìn)制編碼，即讓待傳字符串中出現(xiàn)次數(shù)較多的字符采用盡可能短的編碼，則轉(zhuǎn)換的二進(jìn)制字符串便可能減少。00010010101100三、哈夫曼樹(shù)的應(yīng)用(哈夫曼編碼)設(shè)要傳送的字符為：ABACCDA若編碼為：A—0B—00 C—1D---01

關(guān)鍵：要設(shè)計(jì)長(zhǎng)度不等的編碼，則必須使任一字符的編碼都不是另一個(gè)字符的編碼的前綴。這種編碼稱(chēng)作前綴編碼。ABACCDA

000011010但：0000AAAAABABB重碼設(shè)要傳送的字符為：ABACCDA若編碼為：A—0B—110 C—10D---111

0110010101110ACBD000111采用二叉樹(shù)設(shè)計(jì)二進(jìn)制前綴編碼規(guī)定：左分支用“0”表示；右分支用“1”表示譯碼過(guò)程：分解接收字符串：遇“0”向左，遇“1”向右；一旦到達(dá)葉子結(jié)點(diǎn)，則譯出一個(gè)字符，反復(fù)由根出發(fā)，直到譯碼完成。

0110010101110ACBD000111ABACCDA求Huffman編碼：由根→葉子，若：（1）從左分支下去，則分支為“0”；（2）從右分支下去，則分支為“1”。

ACBD000111例：已知某系統(tǒng)在通訊時(shí)，只出現(xiàn)C，A，S，T，B五種字符，它們出現(xiàn)的頻率依次為2，4，2，3，3，試設(shè)計(jì)Huffman編碼。

W（權(quán)）={2，4，2，3，3}，葉子結(jié)點(diǎn)個(gè)數(shù)n=5148464220001113301構(gòu)造的H