第06章_樹與二叉樹C

1、目 錄1 教教 學學 內內 容容 1 1、樹和森林的概念、樹和森林的概念2 2、二叉樹的定義、性質及運算；、二叉樹的定義、性質及運算； 3 3、二叉樹的存儲結構、二叉樹的存儲結構 4 4、遍歷二叉樹、遍歷二叉樹5 5、線索二叉樹、線索二叉樹6 6、樹、森林、森林與二叉樹的轉換、樹、森林、森林與二叉樹的轉換7 7、哈夫曼樹、哈夫曼編碼、哈夫曼樹、哈夫曼編碼 2本周作業(yè) 習題集 第一次作業(yè)：6.7，6.8， 6.15, 6.16, 6.29, 6.42, 6.45. 第二次作業(yè)：第二次作業(yè)：6.26，6.27, 6.29, 6.44, 6.47，6.65樹和森林與二叉樹的轉換樹和森林的存儲方式樹和

2、森林的遍歷4方法：加線抹線旋轉 abeidfhgcabeidfhgc兄弟相連長兄為父孩子靠左回顧1：樹如何轉為二叉樹？左孩子右兄弟表示法5回顧回顧2 2：二叉樹怎樣還原為樹？二叉樹怎樣還原為樹？abeidfhgc要點：逆操作，把所有右孩子變?yōu)樾值埽?abdefhgic6法一：法一： 各森林先各自轉為二叉樹； 依次連到前一個二叉樹的右子樹上。討論1：森林如何轉為二叉樹？即F=T1, T2, ,Tm B=root, LB, RB法二：法二：森林直接變兄弟，再轉為二叉樹（參見教材P138圖6.17，兩種方法都有轉換示意圖）法一和法二得到的二叉樹是完法一和法二得到的二叉樹是完全相同的、惟一的。全相同的

3、、惟一的。7ABCDEFGHJIABCDEFGHJIBCDEFGHJI森林轉二叉樹舉例：森林轉二叉樹舉例：（用法二，森林直接變兄弟，再轉為二叉樹）（用法二，森林直接變兄弟，再轉為二叉樹）兄弟相連 長兄為父頭樹為根 孩子靠左8BCDEFGHJI討論討論2 2：二叉樹如何還原為森林？二叉樹如何還原為森林？要點：把最右邊的子樹變?yōu)樯郑溆嘤易訕渥優(yōu)樾值?即B=root, LB, RB F=T1, T2, ,TmABCDEFGHJIEFABCDGHJI9樹有三種常用存儲方式：雙親表示法 孩子表示法 孩子兄弟表示法 nextsiblingdatafirstchild指向左孩子指向右兄弟問：樹二叉樹的“

4、連線抹線旋轉” 如何由計算機自動實現？答：用“左孩子右兄弟”表示法來存儲即可。 10abecdfhgbacedfgh例如例如：11例如：abdec先根序列：后根序列：a b c d eb d c e a深度優(yōu)先遍歷（先根、后根）廣度優(yōu)先遍歷（層次）先根遍歷訪問根結點；依次先根遍歷根結點的每棵子樹。后根遍歷 依次后根遍歷根結點的每棵子樹； 訪問根結點。樹沒有中序遍歷（因子樹不分左右）12討論：樹若采用“先轉換，后遍歷”方式，結果是否一樣？abdec先序遍歷：后序遍歷：中序遍歷：d e c b aabdeca b c d eb d c e a1. 樹的先根遍歷與二叉樹的先序遍歷相同； 2. 樹的后

5、根遍歷相當于二叉樹的中序遍歷；3. 樹沒有中序遍歷，因為子樹無左右之分。結論：樹的先根序列：樹的先根序列：a b c d e樹的后根序列：樹的后根序列：b d c e a13先序遍歷若森林為空，返回；訪問森林中第一棵樹的根結點；先根遍歷第一棵樹的根結點的子樹森林；先根遍歷除去第一棵樹之后剩余的樹構成的森林。森林的遍歷森林的遍歷ABCDEFGHJI深度優(yōu)先遍歷（先序、中序）廣度優(yōu)先遍歷（層次）中序遍歷若森林為空，返回；中根遍歷森林中第一棵樹的根結點的子樹森林；訪問第一棵樹的根結點；中根遍歷除去第一棵樹之后剩余的樹構成的森林。14討論：若采用“先轉換，后遍歷”方式，結果是否相同？例如：先序序列：中

6、序序列：A B C D E F G H I JB C D A F E H J I G先序序列：中序序列：A B C D E F G H I JB C D A F E H J I G結論：森林的先序和中序遍歷在兩種方式下的結果相同。15什么是帶權樹？什么是帶權樹？abdc7524即葉子帶有權值。例如：最優(yōu)二叉樹(哈夫曼樹)如果是帶權路徑長度最短的樹16一、Huffman樹的構建二、Huffman編碼三、算法實現最優(yōu)二叉樹Huffman樹Huffman編碼帶權路徑長度最短的樹不等長編碼是通信中最經典的壓縮編碼17樹的帶權路徑長樹的帶權路徑長度如何計算？度如何計算？WPL = wklk k=1nab

7、dc7524(a)cdab2457(b)bdac7524(c)WPL=WPL=WPL=Huffman樹是WPL 最小的樹樹中所有葉子結點的帶權路徑長度之和36463518構造構造Huffman樹的基本思想：樹的基本思想： 權值大的結點用短路徑，權值大的結點用短路徑， 權值小的結點用長路徑。權值小的結點用長路徑。一、一、 HuffmanHuffman樹樹（最優(yōu)二叉樹）（最優(yōu)二叉樹）路路 徑徑：路徑長度路徑長度：樹的路徑長度樹的路徑長度：帶權路徑長度帶權路徑長度：樹的帶權路徑長度樹的帶權路徑長度：HuffmanHuffman樹樹：由一結點到另一結點間的分支所構成。由一結點到另一結點間的分支所構成。

8、路徑上的分支數目。路徑上的分支數目。從樹根到從樹根到每一結點每一結點的路徑長度之和。的路徑長度之和。結點到根的路徑長度與結點上權的乘積（結點到根的路徑長度與結點上權的乘積（WPLWPL）debacf g即樹中所有即樹中所有葉子結點葉子結點的帶權路徑長度之和的帶權路徑長度之和帶權路徑長度最小的樹。帶權路徑長度最小的樹。例如：例如：aeae的路徑長度的路徑長度樹長度樹長度210Huffman常譯為赫夫曼、霍夫曼、哈夫曼等Weighted Path Length19構造構造HuffmanHuffman樹的步驟樹的步驟（即（即HuffmanHuffman算法）：算法）：(1) 由給定的由給定的 n 個

9、權值個權值 w1, w2, , wn 構成構成n棵二叉樹的集合棵二叉樹的集合F = T1, T2, , Tn （即森林）（即森林） ，其中每棵二叉樹，其中每棵二叉樹 Ti 中中只有一個帶權為只有一個帶權為 wi 的根結點，其左右子樹均空。的根結點，其左右子樹均空。(2) 在在F 中選取中選取兩棵根結點權值最小的樹兩棵根結點權值最小的樹 做為左右子樹構造做為左右子樹構造一棵新的二叉樹，且讓新二叉樹根結點的權值一棵新的二叉樹，且讓新二叉樹根結點的權值等于等于其左其左右子樹的根結點右子樹的根結點權值之和權值之和。(3) 在在F 中刪去這兩棵樹，同時將新得到的二叉樹加入中刪去這兩棵樹，同時將新得到的二

10、叉樹加入 F中中。(4) 重復重復(2) 和和(3) , 直到直到 F 只含一棵樹為止。這棵樹便是只含一棵樹為止。這棵樹便是Huffman樹。樹。20在權值集合7,5,2,4中，總是合并當前值最小的兩個權具體操作步驟：具體操作步驟：a. 初始b. 合并2 4c. 合并5 6d. 合并7 1121例題：已知權值例題：已知權值 W= 5, 6, 2, 9, 7 , 建立對應的建立對應的Huffman樹樹22Huffman樹的應用：樹的應用：設有設有4 4個字符個字符d,i,a,nd,i,a,n，出現的頻度分別為，出現的頻度分別為7,5,2,47,5,2,4，怎樣編碼才能使它們組成的報文長度最短？，

11、怎樣編碼才能使它們組成的報文長度最短？法法1 1：等長編碼等長編碼（如二進制編碼）（如二進制編碼）令令d=d=0000，i=i=0101，a=a=1010，n=n=1111，則：，則：WPLWPL1 12bit2bit(7(75 52 24 4）3636法法2 2：不等長編碼不等長編碼（如（如HuffmanHuffman編碼）編碼）令令d=d=0 0;i=;i=1010,a=,a=110110,n=,n=111111，則：，則：WPLWPL2 2= =1 1bitbit7 72 2bitbit5+35+3bitbit(2+4)=(2+4)=3535明確：要實現明確：要實現HuffmanHuff

12、man編碼，就要先構造編碼，就要先構造HuffmanHuffman樹樹討論：討論：HuffmanHuffman樹有什么用？樹有什么用？頻度高的信息用頻度高的信息用短碼，低的用長短碼，低的用長碼，傳輸效率肯碼，傳輸效率肯定高！定高！最小冗余編碼、信息高效傳輸最小冗余編碼、信息高效傳輸23按左“0”右“1” 對Huffman樹的所有分支編號dain111000Huffman編碼結果：d=0, i=10, a=110, n=111WPL=1bit72bit5+3bit(2+4)=35（小于等長碼的WPL=36）Huffman編碼也稱為24哈夫曼編碼哈夫曼編碼 哈夫曼樹的應用很廣，哈夫曼編碼就是其在電

13、訊通信中的應用之一。在電訊通信業(yè)務中，通常用二進制編碼來表示字母或其他字符，并用這樣的編碼來表示字符序列。 例：例：如果需傳送的電文為如果需傳送的電文為 ABACCDA，它只用到，它只用到四種字符，用兩位二進制編碼便可分辨。四種字符，用兩位二進制編碼便可分辨。假設假設 A, B, C, D 的編碼分別為的編碼分別為 00, 01, 10, 11，則上述電文便為，則上述電文便為 00010010101100（共（共 14 位），譯碼員按兩位進行位），譯碼員按兩位進行分組譯碼，便可恢復原來的電文。分組譯碼，便可恢復原來的電文。 能否使編碼總長度更短呢能否使編碼總長度更短呢？ 25實際應用中各字符的

14、出現頻度不相同實際應用中各字符的出現頻度不相同 用用（長長）編碼表示頻率）編碼表示頻率（小?。┑淖址┑淖址?使得編碼序列的總長度最小，使所需總空間量最少使得編碼序列的總長度最小，使所需總空間量最少 若假設若假設 A, B, C, D 的編碼分別為的編碼分別為 0，00，1，01，則電文則電文 ABACCDA 便為便為 000011010（共（共 9 位）。位）?？勺g為可譯為 BBCCDA、ABACCDA、AAAACCACA 存在多義性存在多義性26要求任一字符的編碼都不能是另一字符編碼的前綴！要求任一字符的編碼都不能是另一字符編碼的前綴！ 這種編碼稱為這種編碼稱為（其實是非前綴碼）。（其實是

15、非前綴碼）。 譯碼的惟一性問題譯碼的惟一性問題 利用最優(yōu)二叉樹可以很好地解決上述兩個問題利用最優(yōu)二叉樹可以很好地解決上述兩個問題 在編碼過程要考慮兩個問題在編碼過程要考慮兩個問題 數據的最小冗余編碼問題數據的最小冗余編碼問題 譯碼的惟一性問題譯碼的惟一性問題 27 以電文中的字符作為葉子結點構造二叉樹。以電文中的字符作為葉子結點構造二叉樹。然后將然后將二叉二叉樹樹中中 結點引向其左孩子的分支標結點引向其左孩子的分支標 0，引向其右孩子的分支標，引向其右孩子的分支標 1； 每每 個字符的編碼即為從根到每個葉子的路徑上得到的個字符的編碼即為從根到每個葉子的路徑上得到的 0, 1 序列。如序列。如

16、此此得到的即為二進制前綴編碼。得到的即為二進制前綴編碼。 用二叉樹設計二進制前綴編碼用二叉樹設計二進制前綴編碼 例：例： ABCD0 1 0 1 0 1 編碼編碼： A：0 B：10 C：110 D：111 任意一個葉子任意一個葉子 結點都不可能結點都不可能 在其它葉子結在其它葉子結 點的路徑中。點的路徑中。 28假設各個字符在電文中出現的假設各個字符在電文中出現的（或頻率）為（或頻率）為 wi ，其其為為 li，電文中只有，電文中只有 n 種字符，種字符，為：為： niiilw1葉子結點的權葉子結點的權 從根到葉子的路徑長度從根到葉子的路徑長度 WPL設計電文總長最短的編碼設計電文總長最短的

17、編碼 設計哈夫曼樹（以設計哈夫曼樹（以 n 種種 字符出現的頻率作權）字符出現的頻率作權） 用哈夫曼樹設計總長最短的二進制前綴編碼用哈夫曼樹設計總長最短的二進制前綴編碼 由哈夫曼樹得到的二進制前綴編碼稱為由哈夫曼樹得到的二進制前綴編碼稱為哈夫曼編碼哈夫曼編碼 29解：解： A CBD0 0 0 1 1 1 編碼編碼： A：0 C：10 B：110 D：111 例：例：如果需傳送的電文為如果需傳送的電文為 ABACCDA，即：，即：A, B, C, D 的頻率（即權值）分別為的頻率（即權值）分別為 0.43, 0.14, 0.29, 0.14，試構造哈夫曼編碼。試構造哈夫曼編碼。 則電文則電文

18、ABACCDA 便為便為 0110010101110（共（共 13 位）。位）。 30解：解： EBD編碼編碼： A：11 C：10 E：00 B：010 D：011 例：例：如果需傳送的電文為如果需傳送的電文為 ABCACCDAEAE， 即：即：A, B, C, D, E 的頻率（即權值）分別為的頻率（即權值）分別為 0.36, 0.1, 0.27, 0.1, 0.18，試構造哈夫曼編碼。，試構造哈夫曼編碼。 則電文則電文 ABCACCDAEAE 便為便為 110101011101001111001100 （共（共 24 位，比位，比 33 位短）。位短）。 C A 1 1 1 1 0 0

19、0 0 31 譯碼譯碼 從哈夫曼從哈夫曼樹根開始，對待譯碼電文逐位取碼。若樹根開始，對待譯碼電文逐位取碼。若編碼是編碼是“0”，則向左走；若編碼是，則向左走；若編碼是“1”，則向右走，則向右走，一旦到達葉子結點，則譯出一個字符；再重新從根出一旦到達葉子結點，則譯出一個字符；再重新從根出發(fā)，直到電文結束。發(fā)，直到電文結束。 1111 T ; A C S電文為電文為 “1101000” 譯文只能是譯文只能是“CAT” 32嚴習題集嚴習題集6.266.26：設通信用的電文由字符集設通信用的電文由字符集a,b,c,d,e,f,g,ha,b,c,d,e,f,g,h中的字母構成，這中的字母構成，這8 8個

20、字母在電個字母在電文中出現的概率分別為文中出現的概率分別為 0.07, 0.19, 0.02, 0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10 0.06, 0.32, 0.03, 0.21, 0.10 ，試為這，試為這8 8個字個字母設計哈夫曼編碼。母設計哈夫曼編碼。330.070.070.190.190.020.020.060.060.320.320.030.030.210.210.100.100.070.070.190.190.020.020.060.060.320.320.030.030.210.210.100.100.050.050.070

21、.07 0.190.190.020.020.060.060.320.320.030.030.210.21 0.100.100.050.050.110.110.070.070.190.190.020.020.060.060.320.320.030.030.210.210.100.100.050.050.110.110.170.17340.070.070.190.190.020.020.060.060.320.320.030.030.210.210.100.100.050.050.110.110.170.170.280.280.070.070.190.190.020.020.060.060.320

22、.320.030.030.210.210.100.100.050.050.110.110.170.170.280.280.400.40350.070.070.190.190.020.020.060.060.320.320.030.030.210.210.100.100.050.050.110.110.170.170.280.280.400.400.600.60a0.070.07b0.190.19c0.020.02d0.060.06e0.320.32f0.030.03g0.210.21h0.100.100.050.050.110.110.170.170.280.280.400.400.600.6

23、01.001.0000000001111111a a = = 1010 1010b b = = 00 00c c = = 10000 10000d d = = 1001 1001e e = = 11 11f f = = 10001 10001g g = = 01 01h h = = 1011 101136WPL = 2.61typedef struct typedef struct unsigned int weight;unsigned int weight;unsigned int parent,lchild,rchild;unsigned int parent,lchild,rchild

24、; HTNode, HTNode, * *HuffmanTree; /HuffmanTree; /動態(tài)分配數組存儲赫夫曼樹動態(tài)分配數組存儲赫夫曼樹typedef char typedef char * * *HuffmanCode; HuffmanCode; Huffman Huffman樹沒有度為樹沒有度為1 1的結點的結點 一棵有一棵有n n0 0個葉子結點的個葉子結點的HuffmanHuffman樹共有樹共有2n2n0 0-1-1個結點個結點設共有設共有n n個節(jié)點，則個節(jié)點，則n=nn=n0 0+n+n2 2;(;(沒有度為沒有度為1 1的節(jié)點，的節(jié)點，n n1 1=0)=0)度之和度

25、之和 = n-1 = 2n= n-1 = 2n2 2 n-1 = 2(n-n n-1 = 2(n-n0 0) ) n=2n n=2n0 0-1-1 可以存儲在一個大小為可以存儲在一個大小為2n-12n-1的一維數組中。的一維數組中。節(jié)點權值，父節(jié)點，左孩子節(jié)點和右孩子節(jié)點節(jié)點權值，父節(jié)點，左孩子節(jié)點和右孩子節(jié)點 37void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int * *w, int n)w, int n) /w/w存放存放n

26、 n個字符的權值，構造赫夫曼樹個字符的權值，構造赫夫曼樹HT,HT,并求出并求出n n個字符的赫夫曼編碼個字符的赫夫曼編碼HCHC if (n=1) return; if (n=1) return; / n/ n為字符數目，為字符數目， m=2m=2* *n-1; n-1; / m/ m為結點數目為結點數目 HT = (HuffmanTree)malloc(m+1)HT = (HuffmanTree)malloc(m+1)* *sizeof(HTNodesizeof(HTNode);); /HT /HT存放存放HuffmanHuffman樹結構，樹結構，0 0號單元未用號單元未用, ,其余前其

27、余前n n個單元個單元 /存放樹的葉子結點，存放樹的葉子結點，n-1n-1個單元存放內部結點個單元存放內部結點 for (p=HT, i=1; i=n; +i,+p,+w) for (p=HT, i=1; iweight = p-weight = * *w; p-parent=0;w; p-parent=0; p-lchild=0; p-rchild=0; p-lchild=0; p-rchild=0; / / * *p=p=* *w,0,0,0w,0,0,0；初始化；初始化HTHT中的葉結點循環(huán)退出時中的葉結點循環(huán)退出時i=n+1;i=n+1;38 for (; i=m;+i,+p) for

28、 (; iweight = 0; p-parent=0; p-weight = 0; p-parent=0; p-lchild=0; p-rchild=0; p-lchild=0; p-rchild=0; / / * *p=0,0,0,0; p=0,0,0,0; 初始化初始化HTHT中的內部結點中的內部結點 for (i=n+1; i=m;+i) for (i=n+1; i=m;+i) / / 建赫夫曼樹，建赫夫曼樹，( (建立建立HTHT靜態(tài)鏈表中的鏈靜態(tài)鏈表中的鏈) ) Select(HT,i-1,s1,s2); Select(HT,i-1,s1,s2);/在在HT1HT1i-1i-1中選

29、擇中選擇parentparent / / 為為0 0且且weightweight最小的兩個結點，序號分別為最小的兩個結點，序號分別為s1s1和和s2s2 HTs1.parent=i; HTs2.parent = i; HTs1.parent=i; HTs2.parent = i; HTi.lchild = s1; HTi.rchild = s2; HTi.lchild = s1; HTi.rchild = s2; HTi.weight = HTs1.weight + HTs2.weight; HTi.weight = HTs1.weight + HTs2.weight; 39 /從葉子到根逆向

30、求赫夫曼編碼從葉子到根逆向求赫夫曼編碼1. HC= (HuffmanCode)(n+1)*sizeof(char *);2. cd = ( *)n * (char) ); 3. cdn-1=0; /編碼結束符編碼結束符4. (i=1;i=n;+i) /逐個字符求赫夫曼編碼逐個字符求赫夫曼編碼5. start = n-1; /編碼結束符位置編碼結束符位置6. (c=i,f=HTc.parent; f!=0; c=f,f=HTf.parent) /從葉子到根逆向求編碼從葉子到根逆向求編碼7. (HTf.lchild =c) cd-start=0;8. cd-start=1;9. HCi=(char

31、 *)(n-start)*(char); 10. strcpy(HCi,&cdstart); /從從cd復制編碼串到復制編碼串到HC11. (cd); /釋放工作空間釋放工作空間 /HuffanCoding40HuffmanHuffman編碼舉例編碼舉例解：先將概率放大100倍，以方便構造哈夫曼樹。放大后的權值集合 w= 7, 19, 2, 6, 32, 3, 21, 10 ，按哈夫曼樹構造規(guī)則（合并、刪除、替換），可得到哈夫曼樹。例1【嚴題集6.26】：假設用于通信的電文僅由8個字母 a, b, c, d, e, f, g, h 構成，它們在電文中出現的概率分別為 0.07, 0.19, 0

32、.02, 0.06, 0.32, 0.03, 0.21, 0.10 ，試為這8個字母設計哈夫曼編碼。如果用07的二進制編碼方案又如何？ 【類同P148例2】0000002810010717000000000000000-00000000r0010002100300320060020019007lpw13121011987654321116235211940bc adegfh5991110104917284060100361811111212101132602713131515141451213141415w= 7, 19, 2, 6, 32, 3, 21, 10 請注意：哈夫曼樹樣式不惟一！w= 7, 19, 2, 6, 32, 3, 21, 10 在機內存儲形式為在機內存儲形式為:2810010717000000000000000-00000000r0010002100300320060020019007lpw13121011987654321116235211940badegfh5991110104917284060100361811111212101