1、1 of 118.第第8 8章章 樹和二叉樹樹和二叉樹樹樹二叉樹二叉樹二叉樹設(shè)計二叉樹設(shè)計二叉樹遍歷二叉樹遍歷線索二叉樹線索二叉樹哈夫曼樹哈夫曼樹等價問題等價問題樹與二叉樹的轉(zhuǎn)換樹與二叉樹的轉(zhuǎn)換樹的遍歷樹的遍歷主要知識點主要知識點2 of 118.3 of 118.8.1 8.1 樹樹直觀上：直觀上：樹是由樹是由n(n0)個數(shù)據(jù)組成的有限集合，個數(shù)據(jù)組成的有限集合， 其中僅有一個沒有直接前驅(qū)的數(shù)據(jù)，稱之為根結(jié)點其中僅有一個沒有直接前驅(qū)的數(shù)據(jù)，稱之為根結(jié)點, 若干沒有后繼的數(shù)據(jù)，稱之為若干沒有后繼的數(shù)據(jù)，稱之為 葉結(jié)點，葉結(jié)點， 其他的數(shù)據(jù)只有一個前驅(qū)數(shù)據(jù)，且至少有一個后繼數(shù)據(jù)。其他的數(shù)據(jù)只有一

2、個前驅(qū)數(shù)據(jù)，且至少有一個后繼數(shù)據(jù)。ABCGEIDHFJFLK4 of 118.8.1 8.1 樹樹樹是由樹是由n(n0)個結(jié)點組成的有限集合個結(jié)點組成的有限集合T。n=0的樹稱為空樹；的樹稱為空樹；對對n0的樹，有的樹，有: (1)僅有僅有一個特殊的結(jié)點稱為根結(jié)點一個特殊的結(jié)點稱為根結(jié)點，根結(jié)點沒有前驅(qū)，根結(jié)點沒有前驅(qū) 結(jié)點；結(jié)點； (2)當(dāng)當(dāng)n1時，除根結(jié)點外其余的結(jié)點分為時，除根結(jié)點外其余的結(jié)點分為m(m0)個個互互 不相交不相交的有限集合的有限集合T1,T2，Tm，其中每個集合，其中每個集合Ti 本身又是一棵結(jié)構(gòu)和樹類似的子樹。本身又是一棵結(jié)構(gòu)和樹類似的子樹。注：注：樹的定義具有樹的定義

3、具有遞歸性遞歸性，即，即“樹中還有樹樹中還有樹”。 n=0=+n1空樹，樹根結(jié)點 若干樹，5 of 118.結(jié)點：結(jié)點：由數(shù)據(jù)元素和構(gòu)造數(shù)據(jù)元素之由數(shù)據(jù)元素和構(gòu)造數(shù)據(jù)元素之 間關(guān)系的指針組成間關(guān)系的指針組成ABCGEIDHFJFLK結(jié)點的度結(jié)點的度：結(jié)點所擁有的子樹的個數(shù)結(jié)點所擁有的子樹的個數(shù) 葉結(jié)點葉結(jié)點：度為度為0 0的結(jié)點，也稱作的結(jié)點，也稱作 終端結(jié)點終端結(jié)點 分支結(jié)點分支結(jié)點：度不為度不為0 0的結(jié)點的結(jié)點 ABCGEIDHFJFLK6 of 118.孩子結(jié)點孩子結(jié)點：樹中一個結(jié)點的子樹的根結(jié)點樹中一個結(jié)點的子樹的根結(jié)點 雙親結(jié)點雙親結(jié)點：若樹中某結(jié)點有孩子結(jié)點，則這個結(jié)點就若樹中某

4、結(jié)點有孩子結(jié)點，則這個結(jié)點就 稱作它的孩子結(jié)點的雙親結(jié)點稱作它的孩子結(jié)點的雙親結(jié)點 兄弟結(jié)點兄弟結(jié)點：具有相同的雙親結(jié)點的結(jié)點具有相同的雙親結(jié)點的結(jié)點 樹的度樹的度：樹中所有結(jié)點的度的最大值樹中所有結(jié)點的度的最大值 結(jié)點的層次：結(jié)點的層次：從根結(jié)點到樹中某結(jié)點所經(jīng)路徑上的分支數(shù)從根結(jié)點到樹中某結(jié)點所經(jīng)路徑上的分支數(shù) 樹的深度：樹的深度：樹中所有結(jié)點的層次的最大值樹中所有結(jié)點的層次的最大值 ABCGEIDHFJFLK0 01 12 23 37 of 118.無序樹：無序樹：樹中任意一個結(jié)點的各孩子結(jié)點之間的次序樹中任意一個結(jié)點的各孩子結(jié)點之間的次序 構(gòu)成無關(guān)緊要的樹構(gòu)成無關(guān)緊要的樹 有序樹：有序

5、樹：樹中任意一個結(jié)點的各孩子結(jié)點有嚴(yán)格排列樹中任意一個結(jié)點的各孩子結(jié)點有嚴(yán)格排列 次序的樹次序的樹森林：森林：m（m0）棵樹的集合）棵樹的集合 (1)(1)直觀表示法直觀表示法 (2)(2)形式化表示法形式化表示法 (3)(3)凹入表示法凹入表示法 ( (描述樹的邏輯結(jié)構(gòu)描述樹的邏輯結(jié)構(gòu)) )8 of 118.T=（D，R） DF = D1D2Dm （1i,jm, DiDj=）R=, i=1,2,n-1A AB BC CD DE EF FG GH HI IJ JK KL L形式化表示形式化表示凹凹進(jìn)進(jìn)表表示示( (樹的理論討論樹的理論討論) )( (樹的屏幕顯示樹的屏幕顯示和打印機(jī)輸出和打印機(jī)

6、輸出) )9 of 118.數(shù)據(jù)集合數(shù)據(jù)集合: 樹的結(jié)點集合，每個結(jié)點由數(shù)據(jù)元素和構(gòu)造數(shù)樹的結(jié)點集合，每個結(jié)點由數(shù)據(jù)元素和構(gòu)造數(shù) 據(jù)元素之間關(guān)系的指針組成。據(jù)元素之間關(guān)系的指針組成。操作集合操作集合: （1）初始化）初始化Initiate(T) （2）撤消）撤消DestroyTree(T) （3）雙親結(jié)點）雙親結(jié)點Parent(T, curr) （4）左孩子結(jié)點）左孩子結(jié)點LeftChild(T, curr) （5）右兄弟結(jié)點）右兄弟結(jié)點RightSibling(T, curr) （6）遍歷樹）遍歷樹Traverse(T, Visit()10 of 118. 樹的結(jié)點之間的邏輯關(guān)系主要有雙親樹

7、的結(jié)點之間的邏輯關(guān)系主要有雙親- -孩子關(guān)系，孩子關(guān)系，兄弟關(guān)系。因此，從結(jié)點之間的邏輯關(guān)系分，樹的存兄弟關(guān)系。因此，從結(jié)點之間的邏輯關(guān)系分，樹的存儲結(jié)構(gòu)主要有：儲結(jié)構(gòu)主要有：雙親表示法、孩子表示法、雙親孩子雙親表示法、孩子表示法、雙親孩子表示法和孩子兄弟表示法表示法和孩子兄弟表示法四種組合。四種組合。 指針有指針有常規(guī)指針常規(guī)指針和和仿真指針仿真指針指向內(nèi)存單元地址的指針；指向內(nèi)存單元地址的指針；靜態(tài)鏈表形式的指針；靜態(tài)鏈表形式的指針；結(jié)點的數(shù)據(jù)元素信息結(jié)點的數(shù)據(jù)元素信息結(jié)點之間邏輯關(guān)系結(jié)點之間邏輯關(guān)系11 of 118.4H2G1F1E1D0C0B-1AI4data parentdata

8、parent0 01 12 23 34 45 56 67 78 8ABDEFHICG(1)(1)雙親表示法雙親表示法(a)一棵樹一棵樹（b)仿真指針的雙親表示法存儲結(jié)構(gòu)仿真指針的雙親表示法存儲結(jié)構(gòu)樹及其使用仿真指針的雙親表示法樹及其使用仿真指針的雙親表示法12 of 118.(2)(2)孩子表示法孩子表示法A AC CG GB BD DE EF FI IH H rootroot常規(guī)指針的孩子表示法常規(guī)指針的孩子表示法ABDEFHICG13 of 118.雙親孩子表示法存儲結(jié)構(gòu)雙親孩子表示法存儲結(jié)構(gòu)(3)(3)雙親孩子表示法雙親孩子表示法4H2G1F1E1D0C0B-1AI4data paren

9、t head012345678child next87123456ABDEFHICG14 of 118.(4)(4)孩子兄弟表示法孩子兄弟表示法常規(guī)指針的孩子兄弟表示法常規(guī)指針的孩子兄弟表示法rootBCDEFGHIAABDEFHICG15 of 118.8.2 8.2 二叉樹二叉樹u二叉樹：二叉樹：是是n(n0)個結(jié)點的有限集合。個結(jié)點的有限集合。n=0的樹稱為空的樹稱為空二叉樹；二叉樹；n0的二叉樹由一個根結(jié)點以及兩棵互不相交的二叉樹由一個根結(jié)點以及兩棵互不相交的、分別稱為的、分別稱為左子樹和右子樹左子樹和右子樹的二叉樹組成的二叉樹組成 。 邏輯結(jié)構(gòu)：邏輯結(jié)構(gòu)： 一對二（一對二（1:2）

10、基本特征基本特征: 每個結(jié)點最多只有兩棵子樹（不存在度大于每個結(jié)點最多只有兩棵子樹（不存在度大于2的結(jié)點）；的結(jié)點）； 左子樹和右子樹左子樹和右子樹次序不能顛倒次序不能顛倒。所以下面是兩棵不同。所以下面是兩棵不同的樹的樹16 of 118.BACEDFGBACEDFGu滿二叉樹：滿二叉樹：在一棵二叉樹中，如果所有分支結(jié)點都存在左在一棵二叉樹中，如果所有分支結(jié)點都存在左 子樹和右子樹，并且所有葉子結(jié)點都在同一層上，這樣的子樹和右子樹，并且所有葉子結(jié)點都在同一層上，這樣的 二叉樹稱為滿二叉樹。二叉樹稱為滿二叉樹。u完全二叉樹：完全二叉樹：如果一棵深度為如果一棵深度為k k，有，有n n個結(jié)點的二叉

11、樹結(jié)構(gòu)與個結(jié)點的二叉樹結(jié)構(gòu)與深度為深度為k k的滿二叉樹的前的滿二叉樹的前n n個結(jié)點的結(jié)構(gòu)相同，那么該二叉樹個結(jié)點的結(jié)構(gòu)相同，那么該二叉樹稱為完全二叉樹。如下圖所示稱為完全二叉樹。如下圖所示左子樹左子樹右子樹右子樹17 of 118.BACEDFGHIJKLMNO(a)滿二叉樹滿二叉樹 BACEDFGHIJ(b)完全二叉樹完全二叉樹 問題問題: :一個深度為一個深度為h h的完全二叉的完全二叉樹最多有多少個結(jié)點樹最多有多少個結(jié)點? ?最少有最少有多少個結(jié)點多少個結(jié)點? ?BACEDFGHIJJ J( C)不是不是完全二叉樹完全二叉樹 18 of 118.數(shù)據(jù)集合：數(shù)據(jù)集合：二叉樹的結(jié)點集合，

12、每個結(jié)點由數(shù)據(jù)元素和構(gòu)造數(shù)二叉樹的結(jié)點集合，每個結(jié)點由數(shù)據(jù)元素和構(gòu)造數(shù)據(jù)元素之間關(guān)系的指針組成。據(jù)元素之間關(guān)系的指針組成。操作集合：操作集合：（1 1）初始化）初始化InitiateInitiate(T) (T) （2 2）撤消）撤消DestroyTree(T)DestroyTree(T)（3 3）左插入結(jié)點）左插入結(jié)點InsertLeftNode(curr, x) InsertLeftNode(curr, x) （4 4）右插入結(jié)點）右插入結(jié)點InsertRightNode(currInsertRightNode(curr, x) , x) （5 5）左刪除子樹）左刪除子樹DeleteLef

13、tTree(curr) DeleteLeftTree(curr) （6 6）右刪除子樹）右刪除子樹DeleteRightTree(curr) DeleteRightTree(curr) （7 7）遍歷二叉樹）遍歷二叉樹Traverse(T, Visit()19 of 118.3.3.二叉樹的性質(zhì)二叉樹的性質(zhì)性質(zhì)性質(zhì)1 1 在一棵非空二叉樹的第在一棵非空二叉樹的第i i層上至多有層上至多有2 2i i個結(jié)點（個結(jié)點（i i00）。）。性質(zhì)性質(zhì)2 2 深度為深度為k k的二叉樹至多有的二叉樹至多有2 2k k+1+1-1-1個結(jié)點。個結(jié)點。 說明：深度說明：深度k k=-1=-1，表示沒有一個結(jié)點

14、；深度，表示沒有一個結(jié)點；深度k k=0=0，表示只，表示只有一個根結(jié)點。有一個根結(jié)點。100011nniiaqa qq首項為首項為a a0 0公比為公比為q q的等比數(shù)列的前的等比數(shù)列的前n n項和為：項和為：20 of 118.性質(zhì)性質(zhì)3 對于一棵非空的二叉樹，如果葉結(jié)點個數(shù)為對于一棵非空的二叉樹，如果葉結(jié)點個數(shù)為n0，度，度為為1的結(jié)點數(shù)為的結(jié)點數(shù)為n1，度為，度為2的結(jié)點數(shù)為的結(jié)點數(shù)為n2，結(jié)點總數(shù)為，結(jié)點總數(shù)為n,分分支總數(shù)為支總數(shù)為M，則有下列結(jié)論成立，則有下列結(jié)論成立， (1) n=n0+n1+n2 ; (2) M=n-1; (3) M=n1+2n2; (4) n0= n2+1。

15、 （除根結(jié)點外都有惟一的進(jìn)入分支）（除根結(jié)點外都有惟一的進(jìn)入分支）21 of 118.性質(zhì)性質(zhì)4 4 具有具有n n個結(jié)點的完全二叉樹的深度個結(jié)點的完全二叉樹的深度k k為大于或等于為大于或等于lb(n+1)-1lb(n+1)-1的最小整數(shù)。的最小整數(shù)。證明：由性質(zhì)證明：由性質(zhì)2 2和完全二叉樹的定義可知，對于有和完全二叉樹的定義可知，對于有n n個結(jié)點的深個結(jié)點的深度為度為k k的完全二叉樹有：的完全二叉樹有：2 2k k-1 n 2-1 n 2k+1k+1-1-1移項有：移項有：2 2k k n+1 2 n+1 2k+1k+1對不等式求對數(shù)，有：對不等式求對數(shù)，有：k lb(n+1) k+

16、1k lb(n+1) k+1 因為因為lb(n+1)lb(n+1)介于介于k k和和k+1k+1之間且大于之間且大于k k，而二叉樹的深度，而二叉樹的深度又只能是整數(shù)，所以必有又只能是整數(shù)，所以必有k k為大于或等于為大于或等于lb(n+1)-1lb(n+1)-1的最小整數(shù)。的最小整數(shù)。 可簡寫為可簡寫為k=k= lb(n+1)-1lb(n+1)-1 。 例如，例如， =2=2， =3=3。22 of 118. 若結(jié)點個數(shù)若結(jié)點個數(shù)n=0n=0，則有深度，則有深度k=-1k=-1，滿足，滿足k=k= lb(0+1)-1lb(0+1)-1 =-1=-1； 若結(jié)點個數(shù)若結(jié)點個數(shù)n=1n=1，則有深

17、度，則有深度k=0k=0，滿足，滿足k=k= lb(1+1)-1lb(1+1)-1 =0=0； 若結(jié)點個數(shù)若結(jié)點個數(shù)n=2n=2，則有深度，則有深度k=1k=1，滿足，滿足k=k= lb(2+1)-1lb(2+1)-1 = = =1=1； 若結(jié)點個數(shù)若結(jié)點個數(shù)n=3n=3，則有深度，則有深度k=1k=1，滿足，滿足k=k= lb(3+1)-1lb(3+1)-1 =1=1。 23 of 118.對于一棵有對于一棵有n n個結(jié)點的完全二叉樹，按照從上至下和個結(jié)點的完全二叉樹，按照從上至下和從左至右的順序?qū)λ薪Y(jié)點從從左至右的順序?qū)λ薪Y(jié)點從0 0開始順序編號開始順序編號, ,則對于序號為則對于序號

18、為i i的結(jié)點的結(jié)點(0i n),(0i 0i0，則其雙親是結(jié)點，則其雙親是結(jié)點(i-1)/2(“/”(i-1)/2(“/”表示整除）表示整除） ；如果如果i=0i=0，則結(jié)點，則結(jié)點i i是根結(jié)點，無雙親。是根結(jié)點，無雙親。 (2)(2)如果如果2i+12i+1n n ，其左孩子是結(jié)點，其左孩子是結(jié)點2i+12i+1；如果；如果2i+1n2i+1n，則，則結(jié)點結(jié)點i i無左孩子。無左孩子。 (3)(3)如果如果2i2i2 2n n，其右孩子是結(jié)點，其右孩子是結(jié)點2i2i2 2；如果；如果2i2i2n2n，則結(jié)點則結(jié)點i i無右孩子。無右孩子。結(jié)論：如果完全二叉樹按照從上到下和從左到右的順序?qū)?/p>

19、所有結(jié)論：如果完全二叉樹按照從上到下和從左到右的順序?qū)λ薪Y(jié)點順序編號，則可以用一維數(shù)組存儲完全二叉樹。結(jié)點順序編號，則可以用一維數(shù)組存儲完全二叉樹。二叉樹的順序存儲結(jié)構(gòu)二叉樹的順序存儲結(jié)構(gòu)24 of 118. 二叉樹的存儲結(jié)構(gòu)主要有三種：順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Χ鏄涞拇鎯Y(jié)構(gòu)主要有三種：順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)和仿真指針存儲結(jié)構(gòu)。結(jié)構(gòu)和仿真指針存儲結(jié)構(gòu)。1. 1. 二叉樹的順序存儲結(jié)構(gòu)二叉樹的順序存儲結(jié)構(gòu) 完全二叉樹的結(jié)點可按從上至下和從左至右的次序存儲完全二叉樹的結(jié)點可按從上至下和從左至右的次序存儲在一維數(shù)組中，其結(jié)點之間的關(guān)系可由公式計算得到，這就在一維數(shù)組中，其結(jié)點之間的關(guān)系可由公式

20、計算得到，這就是二叉樹的順序存儲結(jié)構(gòu)。下面兩棵樹在數(shù)組中的存儲結(jié)構(gòu)是二叉樹的順序存儲結(jié)構(gòu)。下面兩棵樹在數(shù)組中的存儲結(jié)構(gòu)分別為：分別為：25 of 118.ABCDEF0 01 12 23 34 45 5A AB BC CD DE EF F0 01 12 23 34 45 5數(shù)據(jù)數(shù)據(jù)雙親雙親左孩子左孩子右孩子右孩子0 01 12 23 34 45 5A AB BC CD DE EF F12i21i22i和和n=6n=6比較比較和和0 0比較比較-1-11 12 20 03 34 4i i0 05 51 11 12 226 of 118.BACEDFGHIJKLMNOA BCDONMLKJIHGF

21、E1204357611810912 13 1427 of 118. 對于一般的非完全二叉樹對于一般的非完全二叉樹顯然不能直接使用二叉樹的順序存顯然不能直接使用二叉樹的順序存儲結(jié)構(gòu)。可以首先在非完全二叉樹中增添一些并不存在的空結(jié)點儲結(jié)構(gòu)。可以首先在非完全二叉樹中增添一些并不存在的空結(jié)點使之變成完全二叉樹的形態(tài)，然后再用順序存儲結(jié)構(gòu)存儲。使之變成完全二叉樹的形態(tài)，然后再用順序存儲結(jié)構(gòu)存儲。 BACEDFGHIJA BCDJIHGFE120435768928 of 118.BACDEGFBACDEGF(a)一般二叉樹一般二叉樹 (b)完全二叉樹形態(tài)完全二叉樹形態(tài)(c) 在數(shù)組中的存儲形式在數(shù)組中的存

22、儲形式 A BC GFED1204357611810912數(shù)組數(shù)組下標(biāo)下標(biāo)29 of 118.2. 二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu) 二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)是用指針建立二叉樹中結(jié)點之間的關(guān)系。二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)是用指針建立二叉樹中結(jié)點之間的關(guān)系。二叉樹最常用的的鏈?zhǔn)酱鎯Y(jié)構(gòu)是二叉鏈。二叉樹最常用的的鏈?zhǔn)酱鎯Y(jié)構(gòu)是二叉鏈。二叉鏈存儲結(jié)構(gòu)的每二叉鏈存儲結(jié)構(gòu)的每個結(jié)點包含三個域，分別是數(shù)據(jù)域個結(jié)點包含三個域，分別是數(shù)據(jù)域data、左孩子指針域、左孩子指針域leftChild和右孩子指針域和右孩子指針域rightChild。二叉鏈存儲結(jié)構(gòu)中每個結(jié)點的圖示。二叉鏈存儲結(jié)構(gòu)中每個結(jié)點的圖示結(jié)構(gòu)為：

23、結(jié)構(gòu)為： rightChild dataleftChild 二叉鏈存儲結(jié)構(gòu)的二叉樹也有不帶頭結(jié)點和帶頭結(jié)點兩種。二叉鏈存儲結(jié)構(gòu)的二叉樹也有不帶頭結(jié)點和帶頭結(jié)點兩種。帶頭結(jié)點的二叉鏈存儲結(jié)構(gòu)的二叉樹見下圖帶頭結(jié)點的二叉鏈存儲結(jié)構(gòu)的二叉樹見下圖(b)(b)，不帶頭結(jié)點的，不帶頭結(jié)點的二叉鏈存儲結(jié)構(gòu)的二叉樹如下圖二叉鏈存儲結(jié)構(gòu)的二叉樹如下圖(a)(a)所示。所示。30 of 118.圖圖8-10 8-10 二叉鏈存儲結(jié)構(gòu)的二叉樹二叉鏈存儲結(jié)構(gòu)的二叉樹rootABC DEFGrootABC DEFG(a)(a)不帶頭結(jié)點的二叉樹不帶頭結(jié)點的二叉樹(b)(b)帶頭結(jié)點的二叉樹帶頭結(jié)點的二叉樹31 of

24、118.3.3.二叉樹的仿真指針二叉樹的仿真指針 二叉樹的仿真指針存儲二叉樹的仿真指針存儲結(jié)構(gòu)結(jié)構(gòu)是用數(shù)組存儲二叉樹中的結(jié)點，是用數(shù)組存儲二叉樹中的結(jié)點，數(shù)組中每個結(jié)點除數(shù)據(jù)元素域外，再增加仿真指針域用于仿數(shù)組中每個結(jié)點除數(shù)據(jù)元素域外，再增加仿真指針域用于仿真常規(guī)指針建立二叉樹中結(jié)點之間的關(guān)系。真常規(guī)指針建立二叉樹中結(jié)點之間的關(guān)系。二叉樹的仿真二叉鏈存儲結(jié)構(gòu)二叉樹的仿真二叉鏈存儲結(jié)構(gòu)rootABC DEFG32 of 118.8.3.2 8.3.2 二叉鏈結(jié)構(gòu)的二叉樹設(shè)計二叉鏈結(jié)構(gòu)的二叉樹設(shè)計rootABC DEFG帶頭結(jié)點的二叉樹帶頭結(jié)點的二叉樹數(shù)據(jù)數(shù)據(jù)域域右孩子右孩子指針指針結(jié)點結(jié)點于是，

25、一棵二叉樹就可以用一個指向根于是，一棵二叉樹就可以用一個指向根節(jié)點上述結(jié)構(gòu)體的指針變量表示。節(jié)點上述結(jié)構(gòu)體的指針變量表示。用一個變量表示用一個變量表示結(jié)構(gòu)體變量結(jié)構(gòu)體變量結(jié)構(gòu)體指針結(jié)構(gòu)體指針整體看待整體看待左孩子左孩子指針指針首先：定義相應(yīng)的結(jié)點結(jié)構(gòu)體首先：定義相應(yīng)的結(jié)點結(jié)構(gòu)體33 of 118.二叉樹結(jié)點結(jié)構(gòu)體定義二叉樹結(jié)點結(jié)構(gòu)體定義typedef struct Node DataType data; struct Node *leftChild; struct Node *rightChild;BiTreeNode;數(shù)據(jù)數(shù)據(jù)域域右孩子右孩子指針指針左孩子左孩子指針指針34 of 118.初

26、始化：對于給定的二叉樹化為空樹。初始化：對于給定的二叉樹化為空樹。void Initiate(BiTreeNode *root) *root = (BiTreeNode *)malloc(sizeof(BiTreeNode); (*root)-leftChild = NULL; (*root)-rightChild = NULL; rootABC DEFG給定：給定：BiTreeNode BiTreeNode * *root;root;35 of 118./ /* *左子樹插入結(jié)點左子樹插入結(jié)點* */ /功能：在當(dāng)前結(jié)點處插入一個新的結(jié)點作為當(dāng)前結(jié)點的左子功能：在當(dāng)前結(jié)點處插入一個新的結(jié)點作

27、為當(dāng)前結(jié)點的左子樹；而當(dāng)前結(jié)點的原來左子樹變成新插入結(jié)點的左子樹。樹；而當(dāng)前結(jié)點的原來左子樹變成新插入結(jié)點的左子樹。rootABC DEFGcurrcurr(1)(1)確定當(dāng)前結(jié)點是否存在確定當(dāng)前結(jié)點是否存在(2)(2)斷其左子樹斷其左子樹( (引入新的指針引入新的指針) )(3)(3)創(chuàng)建新的結(jié)點創(chuàng)建新的結(jié)點s s(4)s(4)s添加數(shù)據(jù)添加數(shù)據(jù)x xt ts sx x(5)(5)確定確定s s的左右孩子的左右孩子(6)(6)確定當(dāng)前結(jié)點確定當(dāng)前結(jié)點currcurr的左孩子的左孩子(7)(7)還回插入結(jié)點的指針還回插入結(jié)點的指針36 of 118./ /* *左子樹插入結(jié)點左子樹插入結(jié)點*

28、*/ /BiTreeNode *InsertLeftNode(BiTreeNode *curr, DataType x) BiTreeNode *s, *t; if(curr = NULL) return NULL; t = curr-leftChild; s = (BiTreeNode *)malloc(sizeof(BiTreeNode); s-data = x; s-leftChild = t; s-rightChild = NULL; curr-leftChild = s; return curr-leftChild;37 of 118./ /* *右子樹插入結(jié)點右子樹插入結(jié)點* */

29、-/-思想和左子樹插入相同思想和左子樹插入相同BiTreeNode *InsertRightNode(BiTreeNode *curr, DataType x) BiTreeNode *s, *t; if(curr = NULL) return NULL; t = curr-rightChild; s = (BiTreeNode *)malloc(sizeof(BiTreeNode); s-data = x; s-rightChild = t; s-leftChild = NULL; curr-rightChild = s; return curr-rightChild;38 of 118./

30、 /* *刪除當(dāng)前結(jié)點的左子樹刪除當(dāng)前結(jié)點的左子樹* */ /BiTreeNode *DeleteLeftTree(BiTreeNode *curr) if(_) return NULL; Destroy(&curr-leftChild); curr-leftChild =_; return curr;rootABC DEFGcurrcurr存在否？存在否？存在否？存在否？curr = NULL | curr-leftChild = NULL NULL39 of 118./ /* *刪除當(dāng)前結(jié)點的右子樹刪除當(dāng)前結(jié)點的右子樹* */ /BiTreeNode *DeleteRightTre

31、e(BiTreeNode *curr) if(curr = NULL | curr-rightChild = NULL) return _; Destroy(&curr-rightChild); curr-rightChild = NULL; return _;rootABC DEFGcurrcurr存在否？存在否？存在否？存在否？NULLcurr40 of 118.例例8-1 8-1 編寫一個建立如圖編寫一個建立如圖8-108-10（b b）所示的帶頭結(jié)點的二）所示的帶頭結(jié)點的二叉鏈存儲結(jié)構(gòu)二叉樹的程序。叉鏈存儲結(jié)構(gòu)二叉樹的程序。#include #include typedef c

32、har DataType;#include Bitree.h“Void main(void) BiTreeNode *root, *p; Initiate(&root); p = InsertLeftNode(root, A); p = _(p, B); p = InsertLeftNode(_, D); p = InsertRightNode(p, _); p = InsertRightNode( _, C); InsertLeftNode(p, E); InsertRightNode(p, F);InsertLeftNodepGroot-leftChildrootABC DEFG4

33、1 of 118. 8.4 8.4 二叉樹遍歷二叉樹遍歷1.1.二叉樹遍歷的基本方法二叉樹遍歷的基本方法 從二叉樹的定義知，一棵二叉樹由三部分組成：根結(jié)點、從二叉樹的定義知，一棵二叉樹由三部分組成：根結(jié)點、左子樹和右子樹。若規(guī)定左子樹和右子樹。若規(guī)定D,L,RD,L,R分別代表分別代表“訪問根結(jié)點訪問根結(jié)點”、“遍歷根結(jié)點的左子樹遍歷根結(jié)點的左子樹”和和“遍歷根結(jié)點的右子樹遍歷根結(jié)點的右子樹”，根據(jù)，根據(jù)遍歷算法對訪問根結(jié)點處理的位置，稱下面三種遍歷算法分遍歷算法對訪問根結(jié)點處理的位置，稱下面三種遍歷算法分別為別為前序遍歷（前序遍歷（DLRDLR）、中序遍歷（）、中序遍歷（LDRLDR）和后序

34、遍歷）和后序遍歷（LRDLRD）。 8.4.1 8.4.1 二叉樹遍歷二叉樹遍歷42 of 118.前序遍歷（前序遍歷（DLRDLR）遞歸算法為：）遞歸算法為：若二叉樹為空則算法結(jié)束；否則：若二叉樹為空則算法結(jié)束；否則：（1 1）訪問根結(jié)點；）訪問根結(jié)點；（2 2）前序遍歷根結(jié)點的左子樹；）前序遍歷根結(jié)點的左子樹；（3 3）前序遍歷根結(jié)點的右子樹。）前序遍歷根結(jié)點的右子樹。對于圖對于圖8-78-7（b b）所示的二叉樹，前序遍歷訪問結(jié)點的次序為：）所示的二叉樹，前序遍歷訪問結(jié)點的次序為：A B D G C E FA B D G C E FrootABC DEFG43 of 118.中序遍歷（中

35、序遍歷（LDRLDR）遞歸算法為：）遞歸算法為：若二叉樹為空則算法結(jié)束；否則：若二叉樹為空則算法結(jié)束；否則：（1 1）中序遍歷根結(jié)點的左子樹；）中序遍歷根結(jié)點的左子樹；（2 2）訪問根結(jié)點；）訪問根結(jié)點；（3 3）中序遍歷根結(jié)點的右子樹。）中序遍歷根結(jié)點的右子樹。對于圖對于圖8-78-7（b b）所示的二叉樹，中序遍歷訪問結(jié)點）所示的二叉樹，中序遍歷訪問結(jié)點的次序的次序為：為：D G B A E C FD G B A E C FrootABC DEFG44 of 118.后序遍歷（后序遍歷（LRDLRD）遞歸算法為：）遞歸算法為：若二叉樹為空則算法結(jié)束；否則：若二叉樹為空則算法結(jié)束；否則：（1

36、 1）后序遍歷根結(jié)點的左子樹；）后序遍歷根結(jié)點的左子樹；（2 2）后序遍歷根結(jié)點的右子樹；）后序遍歷根結(jié)點的右子樹；（3 3）訪問根結(jié)點。）訪問根結(jié)點。對于圖對于圖8-78-7（b b）所示的二叉樹，后序遍歷訪問結(jié)點的）所示的二叉樹，后序遍歷訪問結(jié)點的次序為：次序為：G D B E F C AG D B E F C ArootABC DEFG45 of 118. 此外，二叉樹還有此外，二叉樹還有層序遍歷層序遍歷。層序遍歷的要求是：按。層序遍歷的要求是：按二叉樹的層序次序（即二叉樹的層序次序（即從根結(jié)點層至葉結(jié)點層從根結(jié)點層至葉結(jié)點層），同一層），同一層中按中按先左子樹再右子樹先左子樹再右子樹的

37、次序遍歷二叉樹。的次序遍歷二叉樹。 它的特點是，在所有未被訪問結(jié)點的集合中，排列在它的特點是，在所有未被訪問結(jié)點的集合中，排列在已訪問結(jié)點集合中最前面結(jié)點的左子樹的根結(jié)點將最先被已訪問結(jié)點集合中最前面結(jié)點的左子樹的根結(jié)點將最先被訪問，然后是該結(jié)點的右子樹的根結(jié)點。這樣，如果把已訪問，然后是該結(jié)點的右子樹的根結(jié)點。這樣，如果把已訪問的結(jié)點放在一個隊列中，那么，所有未被訪問結(jié)點的訪問的結(jié)點放在一個隊列中，那么，所有未被訪問結(jié)點的訪問次序就可以由存放在隊列中的已訪問結(jié)點的出隊列次訪問次序就可以由存放在隊列中的已訪問結(jié)點的出隊列次序決定。因此序決定。因此可以借助隊列實現(xiàn)二叉樹的層序遍歷可以借助隊列實現(xiàn)

38、二叉樹的層序遍歷。46 of 118.二叉樹的層序遍歷算法如下：二叉樹的層序遍歷算法如下：（1 1）初始化設(shè)置一個隊列；）初始化設(shè)置一個隊列；（2 2）把根結(jié)點指針入隊列；）把根結(jié)點指針入隊列；（3 3）當(dāng)隊列非空時，循環(huán)執(zhí)行步驟（）到步驟（）；）當(dāng)隊列非空時，循環(huán)執(zhí)行步驟（）到步驟（）； （）出隊列取得一個結(jié)點指針，訪問該結(jié)點；（）出隊列取得一個結(jié)點指針，訪問該結(jié)點； （）若該結(jié)點的左子樹非空，則將該結(jié)點的左子樹指（）若該結(jié)點的左子樹非空，則將該結(jié)點的左子樹指 針入隊列；針入隊列； （）若該結(jié)點的右子樹非空，則將該結(jié)點的右子樹指（）若該結(jié)點的右子樹非空，則將該結(jié)點的右子樹指 針入隊列；針入隊

39、列；（4 4）結(jié)束。）結(jié)束。47 of 118.2.2.二叉樹的遍歷方法和二叉樹的結(jié)構(gòu)二叉樹的遍歷方法和二叉樹的結(jié)構(gòu) 二叉樹是非線性結(jié)構(gòu)，每個結(jié)點會有零個、一個或兩個二叉樹是非線性結(jié)構(gòu)，每個結(jié)點會有零個、一個或兩個孩子結(jié)點，一個二叉樹的遍歷序列不能決定一棵二叉樹，但孩子結(jié)點，一個二叉樹的遍歷序列不能決定一棵二叉樹，但某些不同的遍歷序列組合可以惟一確定一棵二叉樹。可以證某些不同的遍歷序列組合可以惟一確定一棵二叉樹。可以證明，明，給定一棵二叉樹的前序遍歷序列和中序遍歷序列可以惟給定一棵二叉樹的前序遍歷序列和中序遍歷序列可以惟一確定一棵二叉樹的結(jié)構(gòu)一確定一棵二叉樹的結(jié)構(gòu)。 當(dāng)對一個二叉樹用一種特定的

40、遍歷方法來遍歷時，當(dāng)對一個二叉樹用一種特定的遍歷方法來遍歷時，其遍歷序列一定是線性的，且是惟一的。其遍歷序列一定是線性的，且是惟一的。 48 of 118.8.4.2 8.4.2 二叉鏈存儲結(jié)構(gòu)下二叉樹遍歷的實現(xiàn)二叉鏈存儲結(jié)構(gòu)下二叉樹遍歷的實現(xiàn)(1/4)(1/4) rootABC DEFG前序遍歷思想：先根，再左子樹，最后右子樹前序遍歷思想：先根，再左子樹，最后右子樹前序遍歷思想前序遍歷思想遍歷左子樹遍歷左子樹前序遍歷思想前序遍歷思想遍歷右子樹遍歷右子樹函數(shù)實現(xiàn)：函數(shù)名函數(shù)實現(xiàn)：函數(shù)名PreOrderPreOrder函數(shù)函數(shù)PreOrderPreOrder的調(diào)用問題的調(diào)用問題函數(shù)函數(shù)PreOr

41、derPreOrder的調(diào)用問題的調(diào)用問題什么時候停止重復(fù)操作？什么時候停止重復(fù)操作？!=NULL!=NULL49 of 118.8.4.2 8.4.2 二叉鏈存儲結(jié)構(gòu)下二叉樹遍歷的實現(xiàn)二叉鏈存儲結(jié)構(gòu)下二叉樹遍歷的實現(xiàn)(2/4)(2/4) void PreOrder(BiTreeNode *t, void Visit(DataType item)/*前序遍歷二叉樹前序遍歷二叉樹t，訪問操作為，訪問操作為Visit()函數(shù)函數(shù)*/ if(t != NULL) Visit(t-data); _ (t-leftChild, Visit); PreOrder(t-rightChild, Visit);

42、 為了通用性，把對結(jié)點的訪問操作設(shè)計成前序遍歷二叉為了通用性，把對結(jié)點的訪問操作設(shè)計成前序遍歷二叉樹函數(shù)的一個函數(shù)虛參樹函數(shù)的一個函數(shù)虛參 Visit()。PreOrder50 of 118.ABDG GCEF51 of 118.void InOrder(BiTreeNode *t, void Visit(DataType item) /*中序中序t */ if(t != NULL) InOrder(t-leftChild, Visit);Visit(t-data);InOrder(t-rightChild, Visit); void PostOrder(BiTreeNode *t, void

43、 Visit(DataType item) /*后序后序 */ if(t != NULL) PostOrder(t-leftChild, Visit);PostOrder(t-rightChild, Visit);Visit(t-data); 52 of 118.二叉樹撤消操作函數(shù)二叉樹撤消操作函數(shù)二叉樹的撤消操作實際上是二叉樹遍歷操作的一個具二叉樹的撤消操作實際上是二叉樹遍歷操作的一個具體應(yīng)用。由于二叉樹中每個結(jié)點允許有左孩子結(jié)點和右孩體應(yīng)用。由于二叉樹中每個結(jié)點允許有左孩子結(jié)點和右孩子結(jié)點，所以在釋放某個結(jié)點的存儲空間前必須先釋放該子結(jié)點，所以在釋放某個結(jié)點的存儲空間前必須先釋放該結(jié)點左孩

44、子結(jié)點的存儲空間和右孩子結(jié)點的存儲空間，因結(jié)點左孩子結(jié)點的存儲空間和右孩子結(jié)點的存儲空間，因此，二叉樹撤消操作必須是此，二叉樹撤消操作必須是后序遍歷后序遍歷的具體應(yīng)用。撤消操的具體應(yīng)用。撤消操作算法實現(xiàn)如下：作算法實現(xiàn)如下：53 of 118.void Destroy(BiTreeNode *root) if(*root) != NULL & (*root)-leftChild != NULL) Destroy(&(*root)-leftChild); if(*root) != NULL & (*root)-rightChild != NULL) Destroy(&am

45、p;(*root)-rightChild); free(*root);rootrootrootroot存在否？存在否？左子樹存在否？左子樹存在否？右子樹存在否？右子樹存在否？撤銷撤銷撤銷撤銷釋放根結(jié)點釋放根結(jié)點撤銷撤銷54 of 118.8.4.3 8.4.3 二叉樹遍歷的應(yīng)用二叉樹遍歷的應(yīng)用 1 1 打印二叉樹打印二叉樹 把二叉樹逆時針旋轉(zhuǎn)把二叉樹逆時針旋轉(zhuǎn)90900 0C C，按照二叉樹的凹入表，按照二叉樹的凹入表示法打印二叉樹。可把此函數(shù)設(shè)計成遞歸函數(shù)。由于示法打印二叉樹。可把此函數(shù)設(shè)計成遞歸函數(shù)。由于把二叉樹逆時針旋轉(zhuǎn)把二叉樹逆時針旋轉(zhuǎn)90900 0C C后，在屏幕上方的首先是右后，在

46、屏幕上方的首先是右子樹，然后是根結(jié)點，最后是左子樹，所以子樹，然后是根結(jié)點，最后是左子樹，所以打印二叉打印二叉樹算法是一種特殊的中序遍歷算法。樹算法是一種特殊的中序遍歷算法。55 of 118.void PrintBiTree(BiTreeNode *bt, int n) int i; if(bt = NULL) return; PrintBiTree(bt-rightChild, n+1); PrintBiTree(bt-leftChild, n+1); for(i = 0; i =0) printf(-); printf(%cn, bt-data); 56 of 118.A AC CF F

47、0 01 12 23 3 3 3E E2 257 of 118.在二叉樹中查找數(shù)據(jù)元素操作的要求是：在在二叉樹中查找數(shù)據(jù)元素操作的要求是：在btbt為根結(jié)點為根結(jié)點指針的二叉樹中查找數(shù)據(jù)元素指針的二叉樹中查找數(shù)據(jù)元素x x，若查找到數(shù)據(jù)元素，若查找到數(shù)據(jù)元素x x時返回時返回該結(jié)點的指針；若查找不到數(shù)據(jù)元素該結(jié)點的指針；若查找不到數(shù)據(jù)元素x x時返回空指針。時返回空指針。在二叉樹在二叉樹btbt中查找數(shù)據(jù)元素中查找數(shù)據(jù)元素x x算法可設(shè)計成先序遍歷算法算法可設(shè)計成先序遍歷算法，此時查找結(jié)點的次序是：首先在根結(jié)點查找，然后在左子，此時查找結(jié)點的次序是：首先在根結(jié)點查找，然后在左子樹查找，最后在右

48、子樹查找。但是，和常規(guī)遞歸算法不同的樹查找，最后在右子樹查找。但是，和常規(guī)遞歸算法不同的是，此算法當(dāng)一個分支上的結(jié)點比較完仍未查找到數(shù)據(jù)元素是，此算法當(dāng)一個分支上的結(jié)點比較完仍未查找到數(shù)據(jù)元素x x時，要返回到該結(jié)點的雙親結(jié)點處繼續(xù)查找。因此，此算法時，要返回到該結(jié)點的雙親結(jié)點處繼續(xù)查找。因此，此算法是一個回溯算法是一個回溯算法 。2 2 查找數(shù)據(jù)元素查找數(shù)據(jù)元素58 of 118.BiTreeNode *Search(BiTreeNode *bt, DataType x) BiTreeNode *p; if(bt = NULL) return NULL; if(_) return bt; i

49、f(bt-leftChild != NULL) p = _(bt-leftChild, x); if(_) return p; if(_!= NULL) p = Search(bt-rightChild, x); if(p != NULL) return p; return NULL;先序遍歷查找先序遍歷查找bt-data = x Searchp != NULL bt-rightChild 59 of 118.例例8-2 8-2 編寫一個程序，首先建立如圖編寫一個程序，首先建立如圖8-108-10（b b）所示的帶頭）所示的帶頭結(jié)點的二叉鏈存儲結(jié)構(gòu)二叉樹，然后打印該二叉樹，最后輸結(jié)點的二叉鏈存

50、儲結(jié)構(gòu)二叉樹，然后打印該二叉樹，最后輸出分別按照前序遍歷二叉樹次序、中序遍歷二叉樹次序和后出分別按照前序遍歷二叉樹次序、中序遍歷二叉樹次序和后序遍歷二叉樹次序訪問各結(jié)點的序列信息。序遍歷二叉樹次序訪問各結(jié)點的序列信息。設(shè)計：設(shè)計：輸出顯示函數(shù)設(shè)計：按照某種遍歷方法輸出顯示二叉樹各結(jié)輸出顯示函數(shù)設(shè)計：按照某種遍歷方法輸出顯示二叉樹各結(jié)點的信息，其實就是把上述各遍歷二叉樹函數(shù)中的點的信息，其實就是把上述各遍歷二叉樹函數(shù)中的Visit()Visit()函數(shù)設(shè)計成輸出顯示結(jié)點信息的函數(shù)。函數(shù)設(shè)計成輸出顯示結(jié)點信息的函數(shù)。Visit()Visit()函數(shù)設(shè)計如函數(shù)設(shè)計如下：下：void Visit(Da

51、taType item) printf(%c , item); 3.3.應(yīng)用舉例應(yīng)用舉例 60 of 118.8.6 8.6 哈夫曼樹哈夫曼樹1.1.哈夫曼樹的基本概念哈夫曼樹的基本概念 從從A A結(jié)點到結(jié)點到B B結(jié)點所經(jīng)過的分支序列叫做從結(jié)點所經(jīng)過的分支序列叫做從A A結(jié)點到結(jié)點到B B結(jié)點的結(jié)點的路徑；路徑；從從A A結(jié)點到結(jié)點到B B結(jié)點所經(jīng)過的分支個數(shù)叫做從結(jié)點所經(jīng)過的分支個數(shù)叫做從A A結(jié)點到結(jié)點到B B結(jié)點結(jié)點的的路徑長度；路徑長度；從二叉樹的根結(jié)點到二叉樹中所有葉結(jié)點的路徑從二叉樹的根結(jié)點到二叉樹中所有葉結(jié)點的路徑長度之和稱作長度之和稱作該二叉樹的路徑長度。該二叉樹的路徑長度。

52、設(shè)二叉樹有設(shè)二叉樹有n n個帶權(quán)值的個帶權(quán)值的葉結(jié)點，定義從二叉樹的根結(jié)點到二叉樹中所有葉結(jié)點的路徑葉結(jié)點，定義從二叉樹的根結(jié)點到二叉樹中所有葉結(jié)點的路徑長度與相應(yīng)葉結(jié)點權(quán)值的乘積之和稱作該長度與相應(yīng)葉結(jié)點權(quán)值的乘積之和稱作該二叉樹的帶權(quán)路徑長二叉樹的帶權(quán)路徑長度（度（WPLWPL），），即：即：WPL = niiilw1 其中，其中，wi為第為第i i個葉結(jié)點的權(quán)值，個葉結(jié)點的權(quán)值，li為從根結(jié)點到第為從根結(jié)點到第i個個葉結(jié)點的路徑長度。葉結(jié)點的路徑長度。 61 of 118.1 13 35 57 77 71 13 35 57 71 13 35 55 5( (a a) )( (b b) )(

53、 (c c) )( (d d) )7 71 13 3下圖所示二叉樹帶權(quán)路徑長度分別為下圖所示二叉樹帶權(quán)路徑長度分別為:二叉樹的帶權(quán)路徑長度？二叉樹的帶權(quán)路徑長度？ 二叉樹的葉結(jié)點數(shù)和權(quán)值？二叉樹的葉結(jié)點數(shù)和權(quán)值？62 of 118.（a a）WPL = 1WPL = 12+32+32+52+52+72+72 = 322 = 32（b b）WPL = 1WPL = 12+32+33+53+53+73+71 = 331 = 33（c c）WPL = 7WPL = 73+53+53+33+32+12+11 = 431 = 43（d d）WPL = 1WPL = 13+33+33+53+52+72+7

54、1 = 291 = 29具有最小帶權(quán)路徑長度的二叉樹稱作具有最小帶權(quán)路徑長度的二叉樹稱作哈夫曼（哈夫曼（HuffmanHuffman）樹）樹（或稱最優(yōu)二叉樹）。（或稱最優(yōu)二叉樹）。圖（圖（d d）的二叉樹是一棵哈夫曼樹。）的二叉樹是一棵哈夫曼樹。定義：由給定的定義：由給定的n n個葉結(jié)點權(quán)值可以構(gòu)造很多棵形態(tài)不同個葉結(jié)點權(quán)值可以構(gòu)造很多棵形態(tài)不同的二叉樹，的二叉樹，WPLWPL值最小的二叉樹稱為值最小的二叉樹稱為哈夫曼樹哈夫曼樹。要使一棵二叉樹的帶權(quán)路徑長度要使一棵二叉樹的帶權(quán)路徑長度WPLWPL值最小，必須使權(quán)值值最小，必須使權(quán)值越大的葉結(jié)點越靠近根結(jié)點。越大的葉結(jié)點越靠近根結(jié)點。哈夫曼樹構(gòu)

55、造算法為：哈夫曼樹構(gòu)造算法為：63 of 118.（1 1）由給定的）由給定的n n個權(quán)值個權(quán)值ww1 1,w,w2 2, ,w,wn n 構(gòu)造構(gòu)造n n棵只有根結(jié)點的棵只有根結(jié)點的二叉樹，從而得到一個二叉樹森林二叉樹，從而得到一個二叉樹森林F=TF=T1 1,T,T2 2, ,T,Tn n 。（2 2）在二叉樹森林）在二叉樹森林F F中選取根結(jié)點的權(quán)值最小和次小的兩棵中選取根結(jié)點的權(quán)值最小和次小的兩棵二叉樹作為新的二叉樹的左右子樹構(gòu)造新的二叉樹，新的二二叉樹作為新的二叉樹的左右子樹構(gòu)造新的二叉樹，新的二叉樹的根結(jié)點權(quán)值為左右子樹根結(jié)點權(quán)值之和。叉樹的根結(jié)點權(quán)值為左右子樹根結(jié)點權(quán)值之和。（3

56、3）在二叉樹森林）在二叉樹森林F F中刪除作為新二叉樹左右子樹的兩棵二中刪除作為新二叉樹左右子樹的兩棵二叉樹，將新二叉樹加入到二叉樹森林叉樹，將新二叉樹加入到二叉樹森林F F中。中。（4 4）重復(fù)步驟（）重復(fù)步驟（2 2）和（）和（3 3），當(dāng)二叉樹森林），當(dāng)二叉樹森林F F中只剩下一棵中只剩下一棵二叉樹時，這棵二叉樹就是所構(gòu)造的哈夫曼樹。二叉樹時，這棵二叉樹就是所構(gòu)造的哈夫曼樹。64 of 118.2.2.哈夫曼編碼問題哈夫曼編碼問題 將傳送的文字轉(zhuǎn)換為二進(jìn)制字符將傳送的文字轉(zhuǎn)換為二進(jìn)制字符0 0和和1 1組成的二進(jìn)制串的過組成的二進(jìn)制串的過程為程為編碼。編碼。 例：例：假設(shè)要傳送的電文為假

57、設(shè)要傳送的電文為ABACCDAABACCDA，電文中只有，電文中只有A,B,C,DA,B,C,D四種四種字符，若這四個字符采用表字符，若這四個字符采用表(a)(a)所示的編碼方案，則電文的代所示的編碼方案，則電文的代碼為碼為00 01 00 10 10 11 0000 01 00 10 10 11 00，代碼總長度為，代碼總長度為1414。若這四個字符。若這四個字符采用表采用表(b)(b)所示的編碼方案，則電文的代碼為所示的編碼方案，則電文的代碼為0 110 0 10 10 0 110 0 10 10 111 0111 0，代碼總長度為，代碼總長度為1313。字符字符編碼編碼A A0000B

58、B0101C C1010D D1111字符字符編碼編碼A0B110C10D111（a） （b） 65 of 118. 哈夫曼樹可用于哈夫曼樹可用于構(gòu)造代碼總長度最短的編碼方案構(gòu)造代碼總長度最短的編碼方案。 具 體 構(gòu) 造 方 法 如 下 ： 設(shè) 需 要 編 碼 的 字 符 集 合 為具 體 構(gòu) 造 方 法 如 下 ： 設(shè) 需 要 編 碼 的 字 符 集 合 為d1,d2,dn，各個字符在電文中出現(xiàn)的次數(shù)集合為，各個字符在電文中出現(xiàn)的次數(shù)集合為w1,w2,wn，以，以d1,d2,dn作為葉結(jié)點，以作為葉結(jié)點，以w1,w2,wn作為作為各葉結(jié)點的權(quán)值構(gòu)造一棵二叉樹，規(guī)定哈夫曼樹中的左分支各葉結(jié)點的

59、權(quán)值構(gòu)造一棵二叉樹，規(guī)定哈夫曼樹中的左分支為為0，右分支為，右分支為1，則從根結(jié)點到每個葉結(jié)點所經(jīng)過的分支對，則從根結(jié)點到每個葉結(jié)點所經(jīng)過的分支對應(yīng)的應(yīng)的0和和1組成的序列便為該結(jié)點對應(yīng)字符的編碼。組成的序列便為該結(jié)點對應(yīng)字符的編碼。代碼總長代碼總長度最短的不等長編碼稱之為哈夫曼編碼。度最短的不等長編碼稱之為哈夫曼編碼。 不等長編碼不允許存在不等長編碼不允許存在前綴碼前綴碼。前綴碼的一個例子如：。前綴碼的一個例子如：A為為01，B為為010。如編碼存在前綴碼，則譯碼會出現(xiàn)二義性。如編碼存在前綴碼，則譯碼會出現(xiàn)二義性。 問題：為什么哈夫曼編碼一定不會出現(xiàn)前綴碼？問題：為什么哈夫曼編碼一定不會出現(xiàn)

60、前綴碼？66 of 118.3.3.哈夫曼編碼的軟件設(shè)計哈夫曼編碼的軟件設(shè)計 構(gòu)造哈夫曼樹構(gòu)造哈夫曼樹: :方便的實現(xiàn)從雙親結(jié)點到左右孩子結(jié)點的操作方便的實現(xiàn)從雙親結(jié)點到左右孩子結(jié)點的操作; ;哈夫曼編碼哈夫曼編碼: :方便的實現(xiàn)從孩子結(jié)點到雙親結(jié)點的操作。方便的實現(xiàn)從孩子結(jié)點到雙親結(jié)點的操作。設(shè)計哈夫曼樹的結(jié)點存儲結(jié)構(gòu)為雙親孩子存儲結(jié)構(gòu)。設(shè)計哈夫曼樹的結(jié)點存儲結(jié)構(gòu)為雙親孩子存儲結(jié)構(gòu)。采用仿真指針實現(xiàn)，每個結(jié)點的數(shù)據(jù)結(jié)構(gòu)設(shè)計為采用仿真指針實現(xiàn)，每個結(jié)點的數(shù)據(jù)結(jié)構(gòu)設(shè)計為： weightflagparentleftChildrightChild一、哈夫曼編碼的數(shù)據(jù)結(jié)構(gòu)設(shè)計一、哈夫曼編碼的數(shù)據(jù)結(jié)構(gòu)設(shè)計 n n個葉結(jié)點的個葉結(jié)點的HaffmanHaffman