樹、森林、二叉樹

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

……第n層的結點樹的前序遍歷（樹的先根遍歷）若樹非空，則樹的前序遍歷順序如下：①

訪問樹的根結點；②

前序遍歷根的第一棵子樹；③

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

后序遍歷根的第一棵子樹；②

后序遍歷根的其他子樹；③

訪問樹的根結點。ABCDEFGHIJKLMNO先序遍歷：后序遍歷：層次遍歷：ABEFIGCDHJKLNOMEIFGBCJKNOLMHDAABCDEFGHIJKLMNO討論：若采用“先轉換，后遍歷”方式，結果是否一樣？abdec先序遍歷：后序遍歷：中序遍歷：decbaabdecabcdebdcea1.

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

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

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

3

7

51

5

7

3

41

(a)初如森林

(b)一次合并后的森林

注：

哈夫曼樹的不是唯一的！但其最小的WPL是一定的，且葉子權值越大的離根越近。從圖7-24可知，n個權值構造哈夫曼樹需n-1次合并，每次合并，森林中的樹數(shù)目減1，最后森林中只剩下一棵樹，即為我們求得的哈夫曼樹。構造哈夫曼樹的模擬演示3、哈夫曼樹構造程序一棵有n個葉子結點的Huffman樹有2n-1個結點采用順序存儲結構——一維結構數(shù)組存儲結點信息結點類型定義為：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;}}哈夫曼樹的算法模擬演示在遠程通訊中，要將待傳字符轉換成由二進制組成的字符串：設要傳送的字符為：ABACCDA若編碼為：A—00B—01 C—10D---11

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

關鍵：要設計長度不等的編碼，則必須使任一字符的編碼都不是另一個字符的編碼的前綴。這種編碼稱作前綴編碼。ABACCDA

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

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

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

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

W（權）={2，4，2，3，3}，葉子結點個數(shù)n=5148464220001113301構造的H