數(shù)據(jù)結(jié)構(gòu)與算法5

1、第5章 樹和二叉樹（4課時(shí)）n樹是一種非常重要的非線性數(shù)據(jù)結(jié)構(gòu)。樹由n（n0）個(gè)數(shù)據(jù)元素組成，數(shù)據(jù)元素之間具有明顯的層次結(jié)構(gòu)。圖5-1是樹的樹形圖表示，由于它很像自然界中倒長的樹，因此，被命名為“樹”。樹的樹形圖表示法規(guī)定在用直線連接起來的兩端結(jié)點(diǎn)中，處在上端的結(jié)點(diǎn)是前驅(qū)，處在下端的結(jié)點(diǎn)是后繼，如A是B的前驅(qū)，B是A的后繼。圖5-1中所示樹的邏輯結(jié)構(gòu)可表示為T=(D, R)，其中：數(shù)據(jù)元素集合D=A, B, C, D, E, F, G, H, I, J, K, L，各數(shù)據(jù)元素之間的前后件關(guān)系R=, , , , , , , , , , 。 n從圖5-1可以很直觀地看出樹具有如下結(jié)構(gòu)特性：只有最頂

2、層的結(jié)點(diǎn)沒有前驅(qū)，其余結(jié)點(diǎn)都有且只有一個(gè)前驅(qū)；一個(gè)結(jié)點(diǎn)可以沒有后繼，也可以有一個(gè)或多個(gè)后繼。nAnBnCnDnEnFnGnHnInJnKnLn第1層n第2層n第3層n第4層圖5-1 樹的樹形圖表示n在客觀世界中，很多事物都可以用樹這種數(shù)據(jù)結(jié)構(gòu)來表示，如圖5-2所示的學(xué)校組織結(jié)構(gòu)圖。在計(jì)算機(jī)領(lǐng)域，樹也有著非常廣泛的應(yīng)用，如用樹型結(jié)構(gòu)表示實(shí)體之間聯(lián)系的層次模型是最早用于商業(yè)數(shù)據(jù)庫管理系統(tǒng)的數(shù)據(jù)模型；在操作系統(tǒng)中用樹來表示文件目錄結(jié)構(gòu)等。5.1.1 樹的定義樹的定義5.1.3樹的基本術(shù)語樹的基本術(shù)語5.1.2 樹的表示形式樹的表示形式n樹是由n（n0）個(gè)結(jié)點(diǎn)組成的有限集T。當(dāng)n=0時(shí)，稱為空樹；當(dāng)n

3、0時(shí)，集合T須滿足如下條件：n有且僅有一個(gè)沒有前驅(qū)的結(jié)點(diǎn)，該結(jié)點(diǎn)稱為樹的根結(jié)點(diǎn)；n將根節(jié)點(diǎn)去除后，其余結(jié)點(diǎn)可分為m（m0）個(gè)互不相交的子集T1、T2、Tm，其中每個(gè)子集Ti（i=1, 2, , m）又是一棵樹，并稱其為根的子樹。n可以看到，樹的定義采用的是遞歸定義方式，即一棵非空的樹由根節(jié)點(diǎn)和去除根節(jié)點(diǎn)后得到的若干棵規(guī)模更小的子樹構(gòu)成，而每一棵子樹又是由該子樹的根節(jié)點(diǎn)和去除該子樹根節(jié)點(diǎn)后得到的若干棵更小的子樹構(gòu)成。例如，圖5-1所示的樹可以看作是由根節(jié)點(diǎn)A和3棵子樹T1、T2、T3（結(jié)點(diǎn)集合分別為D1=B, E, F, I、D2=C, G和D3=D, H, J, K, L）構(gòu)成；子樹T1又可以

4、看作是由根節(jié)點(diǎn)B和兩棵子樹T11、T12（結(jié)點(diǎn)集合分別為D11=E、D12=F, I）構(gòu)成。 5.1.1 樹的定義樹的定義n樹形圖表示法因其直觀性強(qiáng)而成為樹的最常用的表示形式，圖5-1即是采用樹形圖表示法表示的樹。除樹形圖表示法之外，還有三種常用的表示形式：n1.1.嵌套集合表示法嵌套集合表示法嵌套集合表示法是通過集合包含的形式體現(xiàn)結(jié)點(diǎn)之間的關(guān)系，后繼結(jié)點(diǎn)集合包含在前驅(qū)結(jié)點(diǎn)集合中。例如，采用嵌套集合表示法可將圖5-1所示的樹表示為圖5-3所示的形式。 nAnBnCnDnEnInFnGnHnJnKnL5.1.2 樹的表示形式樹的表示形式n2.凹入表表示法凹入表表示法凹入表表示法是利用書的目錄形式

5、表示結(jié)點(diǎn)之間的關(guān)系，后繼結(jié)點(diǎn)位于前驅(qū)結(jié)點(diǎn)的下一層目錄中。例如，采用凹入表表示法可將圖5-1所示的樹表示為圖5-4所示的形式。 n3.廣義表表示法廣義表表示法廣義表表示法是利用廣義表的多層次結(jié)構(gòu)來表示樹，后繼結(jié)點(diǎn)位于前驅(qū)結(jié)點(diǎn)的下一層次。例如，采用廣義表表示法可將圖5-1所示的樹表示為圖5-5所示的形式。nAnBnEnFnInCnGnDnHnJnKnL5.1.2 樹的表示形式樹的表示形式2.結(jié)點(diǎn)的層和樹的深度結(jié)點(diǎn)的層和樹的深度 樹的根結(jié)點(diǎn)所在的層為第1層，其余結(jié)點(diǎn)的層等于其前驅(qū)結(jié)點(diǎn)的層加1；樹中各結(jié)點(diǎn)的層的最大值稱為樹的深度。1.度和樹的度度和樹的度 一個(gè)結(jié)點(diǎn)的后繼的數(shù)目稱為該結(jié)點(diǎn)的度度；樹中各結(jié)

6、點(diǎn)度的最大值稱為樹的度。5.1.3樹的基本術(shù)語樹的基本術(shù)語3.3.分支、路徑、路徑長度和樹的路徑長度分支、路徑、路徑長度和樹的路徑長度 從一個(gè)結(jié)點(diǎn)到其后繼結(jié)點(diǎn)之間的連線稱為一個(gè)分支分支；從一個(gè)結(jié)點(diǎn)X到另一個(gè)結(jié)點(diǎn)Y所經(jīng)歷的所有分支構(gòu)成結(jié)點(diǎn)X到結(jié)點(diǎn)Y的路徑；一條路徑上的分支數(shù)目稱為路徑長度；從樹的根結(jié)點(diǎn)到其他各個(gè)結(jié)點(diǎn)的路徑長度之和稱為樹的路徑長度。5.1.3樹的基本術(shù)語樹的基本術(shù)語 5.結(jié)點(diǎn)間的關(guān)系結(jié)點(diǎn)間的關(guān)系 在樹中，一個(gè)結(jié)點(diǎn)的后繼結(jié)點(diǎn)稱為該結(jié)點(diǎn)的孩子，相應(yīng)地，一個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)稱為該結(jié)點(diǎn)的雙親，即一個(gè)結(jié)點(diǎn)是其孩子結(jié)點(diǎn)的雙親、其雙親結(jié)點(diǎn)的孩子。 同一雙親的孩子結(jié)點(diǎn)之間互稱為兄弟，不同雙親但在同一

7、層的結(jié)點(diǎn)之間互稱為堂兄弟。 從樹的根結(jié)點(diǎn)到某一個(gè)結(jié)點(diǎn)X的路徑上經(jīng)歷的所有結(jié)點(diǎn)（包括根結(jié)點(diǎn)但不包括結(jié)點(diǎn)X）稱為結(jié)點(diǎn)X的祖先，以某一結(jié)點(diǎn)X為根的子樹上的所有非根結(jié)點(diǎn)（即除結(jié)點(diǎn)X外）稱為結(jié)點(diǎn)X的子孫。 4.葉子結(jié)點(diǎn)、分支結(jié)點(diǎn)和內(nèi)部結(jié)點(diǎn)葉子結(jié)點(diǎn)、分支結(jié)點(diǎn)和內(nèi)部結(jié)點(diǎn) 樹中度為0的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)（或終端結(jié)點(diǎn)），度不為0的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)（或非終端結(jié)點(diǎn)），除根結(jié)點(diǎn)以外的分支結(jié)點(diǎn)也稱為內(nèi)部結(jié)點(diǎn)。5.1.3樹的基本術(shù)語樹的基本術(shù)語6.有序樹和無序樹有序樹和無序樹 對于樹中的任一結(jié)點(diǎn)，如果其各棵子樹的相對次序被用來表示數(shù)據(jù)之間的關(guān)系，即交換子樹位置會(huì)改變樹所表示的內(nèi)容，則稱該樹為有序樹；否則稱為無序樹。ABCA

8、CB（a）（b）5.1.3樹的基本術(shù)語樹的基本術(shù)語7.森林森林 m（m0）棵互不相交的樹的集合就構(gòu)成了森林。顯然，將一棵樹的根結(jié)點(diǎn)刪除就可以得到由根結(jié)點(diǎn)的子樹組成的森林；將森林中的樹用一個(gè)根結(jié)點(diǎn)連起來就可以得到一棵樹。 n二叉樹是一種特殊的樹型結(jié)構(gòu)，在實(shí)際應(yīng)用中有著十分重要的意義。比如，在通信、數(shù)據(jù)壓縮等領(lǐng)域有著廣泛應(yīng)用的哈夫曼樹就是采用二叉樹的結(jié)構(gòu)；在數(shù)據(jù)庫中可以選擇使用二叉樹結(jié)構(gòu)管理數(shù)據(jù)等。本節(jié)主要介紹二叉樹的定義和一些基本性質(zhì)。 n對二叉樹中的結(jié)點(diǎn)可以按照“自上而下、自左至右”的順序進(jìn)行連續(xù)編號（稱為順序編號法），即從根結(jié)點(diǎn)開始將其編號為1；除第一層外其余各層第一個(gè)結(jié)點(diǎn)的編號等于上一層最

9、后一個(gè)結(jié)點(diǎn)的編號加1。圖5-8所示的就是3棵深度為3、采用順序編號法表示的二叉樹：5.2.1 二叉樹的定義二叉樹的定義1234567（a）123456（b）12345（c）圖5-8 采用順序編號法表示的樹5.2.1 二叉樹的定義二叉樹的定義5.2.2 二叉樹的基本性質(zhì)二叉樹的基本性質(zhì)n 1.1.二叉樹二叉樹 與樹一樣，二叉樹的定義也采用遞歸定義方式。二叉樹是由n（n0）個(gè)結(jié)點(diǎn)組成的有限集T。當(dāng)n=0時(shí)，稱為空二叉樹；當(dāng)n0時(shí)，集合T須滿足如下條件：n 有且僅有一個(gè)沒有前驅(qū)的結(jié)點(diǎn)，該結(jié)點(diǎn)稱為二叉樹的根結(jié)n 將根節(jié)點(diǎn)去除后，其余結(jié)點(diǎn)可分為兩個(gè)互不相交的子集T1、T2，其中每個(gè)子集Ti（i=1, 2

10、）又是一棵二叉樹，并分別稱為根結(jié)點(diǎn)的左子樹和右子樹。5.2.1 二叉樹的定義二叉樹的定義n二叉樹共有5種基本形態(tài)，如圖5-7所示。5.2.1 二叉樹的定義二叉樹的定義AAAA（a）空二叉樹（b）只有根結(jié)點(diǎn)（c）右子樹為空（d）左子樹為空（e）左、右子樹非空圖5-7 二叉樹的基本形態(tài)n2.滿二叉樹和完全二叉樹滿二叉樹和完全二叉樹 滿二叉樹是指除了最后一層的結(jié)點(diǎn)為葉子結(jié)點(diǎn)外其它結(jié)點(diǎn)都有左、右兩棵子樹的二叉樹。例如，圖5-8（a）是一棵滿二叉樹；圖5-8（b）中的結(jié)點(diǎn)3缺少右子樹，圖5-8（c）中的結(jié)點(diǎn)2缺少右子樹、結(jié)點(diǎn)3缺少左子樹，因此它們都不是滿二叉樹。 完全二叉樹是指其結(jié)點(diǎn)與相同深度的滿二叉樹

11、中的結(jié)點(diǎn)編號完全一致的二叉樹。對于深度為k的完全二叉樹，其前k-1層與深度為k的滿二叉樹的前k-1層完全一樣，只是在第k層上有可能缺少右邊若干個(gè)結(jié)點(diǎn)。顯然，滿二叉樹必然是完全二叉樹，而完全二叉樹不一定是滿二叉樹。例如，圖5-8（a）既是滿二叉樹也是完全二叉樹；圖5-8（b）與圖5-8（a）中的滿二叉樹相比只是在最后一層上缺少右邊的一個(gè)結(jié)點(diǎn)，因此是一棵完全二叉樹；而圖5-8（c）則不是完全二叉樹。5.2.1 二叉樹的定義二叉樹的定義二叉樹具有以下幾個(gè)基本性質(zhì)。二叉樹具有以下幾個(gè)基本性質(zhì)。n性質(zhì)1：在二叉樹的第i層上至多有2i-1個(gè)結(jié)點(diǎn)（i1）。n性質(zhì)2：深度為k的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)。n性

12、質(zhì)3：在二叉樹中，若度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。n性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹其深度為log2n+1（其中l(wèi)og2n表示不大于log2n的最大整數(shù)）。n性質(zhì)5：采用順序編號的完全二叉樹具有如下性質(zhì)：（1）若一個(gè)分支結(jié)點(diǎn)的編號為i，則其左子樹的根結(jié)點(diǎn)（即左孩子結(jié)點(diǎn)）編號為2*i，右子樹的根結(jié)點(diǎn)（即右孩子結(jié)點(diǎn)）編號為2*i+1；（2）反之，若一個(gè)非根結(jié)點(diǎn)的編號為i，則其雙親結(jié)點(diǎn)的編號為i/2（其中i/2表示不大于i/2的最大整數(shù)）。5.2.2 二叉樹的基本性質(zhì)二叉樹的基本性質(zhì) 同線性表一樣，二叉樹中的每個(gè)結(jié)點(diǎn)既可以存儲(chǔ)單值元素，又可以存儲(chǔ)記錄型元

13、素。二叉樹一般需要進(jìn)行下面的基本操作：n 創(chuàng)建一棵空二叉樹n 刪除一棵二叉樹n 先序遍歷二叉樹n 中序遍歷二叉樹n 后序遍歷二叉樹n 逐層遍歷二叉樹n 判斷二叉樹是否為空n 清空二叉樹n 以指定元素值創(chuàng)建根結(jié)點(diǎn)n 將一個(gè)結(jié)點(diǎn)作為指定結(jié)點(diǎn)的左孩子插入n 將一個(gè)結(jié)點(diǎn)作為指定結(jié)點(diǎn)的右孩子插入n 刪除以指定結(jié)點(diǎn)為根的子樹n 按關(guān)鍵字查找結(jié)點(diǎn)n 修改指定結(jié)點(diǎn)的元素值n 獲取指定結(jié)點(diǎn)的雙親結(jié)點(diǎn)n 計(jì)算二叉樹的深度n 計(jì)算二叉樹的葉子結(jié)點(diǎn)數(shù) 5.3.1 二叉樹的順序表示及其實(shí)現(xiàn)二叉樹的順序表示及其實(shí)現(xiàn)5.3.2 二叉樹的鏈?zhǔn)奖硎炯捌鋵?shí)現(xiàn)二叉樹的鏈?zhǔn)奖硎炯捌鋵?shí)現(xiàn)n2.二叉樹順序表示的實(shí)現(xiàn)二叉樹順序表示的實(shí)現(xiàn)

14、由于順序表示非完全二叉樹時(shí)空間利用率較低，因此，二叉樹的順序表示在實(shí)際中應(yīng)用不多。下面主要圍繞二叉樹的創(chuàng)建和刪除這兩個(gè)最基本的操作介紹二叉樹順序表示的實(shí)現(xiàn)。n二叉樹順序表示的類模板描述如下： 【描述5-1】二叉樹順序表示的類模板描述。 分析：在類模板中，需設(shè)置以下成員變量：一維數(shù)組m_pElement用于存儲(chǔ)二叉樹中各結(jié)點(diǎn)的值，數(shù)組類型由二叉樹結(jié)點(diǎn)的值的類型決定；整型變量m_nMaxSize用于存儲(chǔ)二叉樹中的最大結(jié)點(diǎn)數(shù)；一個(gè)bool型一維數(shù)組m_pbUsed，用于表示結(jié)點(diǎn)狀態(tài)，若某個(gè)結(jié)點(diǎn)不存在（如圖5-9（b）中的結(jié)點(diǎn)4和結(jié)點(diǎn)5），則m_pbUsed中相應(yīng)元素的值為false，否則相應(yīng)元素的值

15、為true。 5.3.1 二叉樹的順序表示及其實(shí)現(xiàn)二叉樹的順序表示及其實(shí)現(xiàn)n3.二叉樹順序表示代碼復(fù)用示例二叉樹順序表示代碼復(fù)用示例【例5-1】基于二叉樹順序表示的C+實(shí)現(xiàn)代碼，完成如下操作： 創(chuàng)建圖5-9（b）所示的二叉樹，其中每一個(gè)結(jié)點(diǎn)保存一個(gè)字符信息，并通過逐層遍歷輸出各結(jié)點(diǎn)的值。 將以結(jié)點(diǎn)C為根結(jié)點(diǎn)的子樹刪除，并通過逐層遍歷輸出各結(jié)點(diǎn)的值。 清空二叉樹中的元素。 分析：對于由簡單數(shù)據(jù)元素構(gòu)成的二叉樹，一般可以直接使用C+語言提供的基本數(shù)據(jù)類型來描述數(shù)據(jù)元素，本例中可直接使用char類型。5.3.1 二叉樹的順序表示及其實(shí)現(xiàn)二叉樹的順序表示及其實(shí)現(xiàn)n1.二叉樹的鏈?zhǔn)奖硎径鏄涞逆準(zhǔn)奖硎?

16、在二叉樹的鏈?zhǔn)奖硎局?，結(jié)點(diǎn)之間的關(guān)系通過指針來體現(xiàn)。根據(jù)一個(gè)結(jié)點(diǎn)中指針域數(shù)量的不同，二叉樹的鏈?zhǔn)奖硎居挚梢苑譃槎骀湵肀硎竞腿骀湵肀硎?。圖5-10是一個(gè)用二叉鏈表表示法存儲(chǔ)二叉樹的例子。由于二叉樹中每個(gè)結(jié)點(diǎn)最多有兩個(gè)孩子，因此在一個(gè)結(jié)點(diǎn)中設(shè)置兩個(gè)指針域leftchild和rightchild分別指向其左孩子和右孩子，數(shù)據(jù)域data用于存放每個(gè)結(jié)點(diǎn)中數(shù)據(jù)元素的值。5.3.2 二叉樹的鏈?zhǔn)奖硎炯捌鋵?shí)現(xiàn)二叉樹的鏈?zhǔn)奖硎炯捌鋵?shí)現(xiàn) 分析：創(chuàng)建二叉樹的方式有多種，這里采用基于隊(duì)列的層次創(chuàng)建方式。其創(chuàng)建步驟如圖5-13所示。 5.3.2 二叉樹的鏈?zhǔn)奖硎炯捌鋵?shí)現(xiàn)二叉樹的鏈?zhǔn)奖硎炯捌鋵?shí)現(xiàn)n圖5-11是一個(gè)用

17、三叉鏈表表示法存儲(chǔ)二叉樹的例子。在三叉鏈表表示中，雙親結(jié)點(diǎn)有指向其孩子結(jié)點(diǎn)的指針，而孩子結(jié)點(diǎn)也包含指向其雙親結(jié)點(diǎn)的指針。因此，在用三叉鏈表表示的二叉樹的每個(gè)結(jié)點(diǎn)中，除了具有二叉鏈表中的兩個(gè)指向孩子結(jié)點(diǎn)的指針域leftchild和rightchild外，還有一個(gè)指向雙親結(jié)點(diǎn)的指針域parent。根結(jié)點(diǎn)沒有雙親，所以它的parent指針為空（用NULL或0表示）。 5.3.2 二叉樹的鏈?zhǔn)奖硎炯捌鋵?shí)現(xiàn)二叉樹的鏈?zhǔn)奖硎炯捌鋵?shí)現(xiàn)n2.二叉樹鏈?zhǔn)奖硎镜膶?shí)現(xiàn)二叉樹鏈?zhǔn)奖硎镜膶?shí)現(xiàn) 二叉鏈表表示是二叉樹最常用的存儲(chǔ)結(jié)構(gòu)，這里以二叉鏈表為例、圍繞二叉樹的創(chuàng)建介紹二叉樹鏈?zhǔn)奖硎镜膶?shí)現(xiàn)，其他常用操作的實(shí)現(xiàn)在5.4節(jié)

18、給出。詳細(xì)代碼見講義5.3.2 二叉樹的鏈?zhǔn)奖硎炯捌鋵?shí)現(xiàn)二叉樹的鏈?zhǔn)奖硎炯捌鋵?shí)現(xiàn)n3.二叉樹鏈?zhǔn)奖硎敬a復(fù)用二叉樹鏈?zhǔn)奖硎敬a復(fù)用示例示例n【例5-2】基于二叉樹二叉鏈表表示的C+實(shí)現(xiàn)代碼，創(chuàng)建圖5-12所示的二叉樹，其中每一個(gè)結(jié)點(diǎn)保存一個(gè)字符信息。 5.3.2 二叉樹的鏈?zhǔn)奖硎炯捌鋵?shí)現(xiàn)二叉樹的鏈?zhǔn)奖硎炯捌鋵?shí)現(xiàn)ABCDEFGHI圖5-12 例5-2創(chuàng)建的二叉樹 在二叉樹的應(yīng)用中，常常要求在樹中查找具有某種特征的結(jié)點(diǎn)或者對樹中全部結(jié)點(diǎn)逐一進(jìn)行各種處理，這時(shí)就涉及二叉樹的遍歷問題。5.4.1 二叉樹的遍歷及其實(shí)現(xiàn)二叉樹的遍歷及其實(shí)現(xiàn)5.4.2二叉樹常用操作的實(shí)現(xiàn)二叉樹常用操作的實(shí)現(xiàn)1.先序遍歷先序

19、遍歷 先序遍歷，也稱為先根遍歷，其訪問方式遞歸定義如下：對于一棵二叉樹，先訪問其根結(jié)點(diǎn)，再訪問根結(jié)點(diǎn)的左、右子樹；對于左、右子樹中的結(jié)點(diǎn)仍然是按照先序遍歷方式訪問，即先訪問根結(jié)點(diǎn)，再訪問根結(jié)點(diǎn)的左、右子樹。 提示：在先序遍歷中，只規(guī)定了根結(jié)點(diǎn)和其子樹的訪問順序，但沒有規(guī)定左、右子樹的訪問順序。本書中規(guī)定，在先序、中序和后序遍歷時(shí)均是先訪問左子樹后訪問右子樹。 例如，對于圖5-12所示的二叉樹，其先序遍歷的結(jié)果為：A、B、D、G、C、E、F、H、I。5.4.1 二叉樹的遍歷及其實(shí)現(xiàn)二叉樹的遍歷及其實(shí)現(xiàn)5.4.1 二叉樹的遍歷及其實(shí)現(xiàn)二叉樹的遍歷及其實(shí)現(xiàn)操作棧中元素（最左邊為棧底元素，最右邊為棧頂

20、元素）根結(jié)點(diǎn)A入棧A棧頂元素A出棧并訪問，將A的右孩子C和左孩子B依次入棧C、B棧頂元素B出棧并訪問，將B的左孩子D入棧C、D棧頂元素D出棧并訪問，將D的右孩子G入棧C、G棧頂元素G出棧并訪問C棧頂元素C出棧并訪問，將C的右孩子F和左孩子E依次入棧F、E棧頂元素E出棧并訪問F棧頂元素F出棧并訪問，將F的右孩子I和左孩子H依次入棧I、H棧頂元素H出棧并訪問I棧頂元素I出棧并訪問棧為空，二叉樹先序遍歷結(jié)束表5-1 圖5-12所示二叉樹的非遞歸先序遍歷過程 2.中序遍歷中序遍歷 中序遍歷，也稱為中根遍歷，其訪問方式遞歸定義如下：對于一棵二叉樹，先訪問根結(jié)點(diǎn)左子樹，再訪問根結(jié)點(diǎn)，最后右子樹；對于左、右

21、子樹中的結(jié)點(diǎn)仍然是按照中序遍歷方式訪問。 例如，對于圖5-12所示的二叉樹，其中序遍歷的結(jié)果為：D、G、B、A、E、C、H、F、I。5.4.1 二叉樹的遍歷及其實(shí)現(xiàn)二叉樹的遍歷及其實(shí)現(xiàn)3.后序遍歷后序遍歷 后序遍歷，也稱為后根遍歷，其訪問方式遞歸定義如下：對于一棵二叉樹，先訪問根結(jié)點(diǎn)的左子樹，后訪問右子樹，最后訪問根結(jié)點(diǎn)；對于左、右子樹中的結(jié)點(diǎn)仍然是按照后序遍歷方式訪問。 例如，對于圖5-12所示的二叉樹，其后序遍歷的結(jié)果為：G、D、B、E、H、I、F、C、A。5.4.1 二叉樹的遍歷及其實(shí)現(xiàn)二叉樹的遍歷及其實(shí)現(xiàn)n1.獲取指定結(jié)點(diǎn)的雙親結(jié)點(diǎn)獲取指定結(jié)點(diǎn)的雙親結(jié)點(diǎn)在二叉樹的二叉鏈表表示中，結(jié)點(diǎn)中

22、沒有指向其雙親結(jié)點(diǎn)的指針，要獲取雙親結(jié)點(diǎn)則需要從根結(jié)點(diǎn)開始遍歷二叉樹直至找到指定結(jié)點(diǎn)的雙親結(jié)點(diǎn)。因此，可以參照上一小節(jié)中給出的二叉樹遍歷算法，編寫獲取雙親結(jié)點(diǎn)的程序。n2.刪除以指定結(jié)點(diǎn)為根的子樹刪除以指定結(jié)點(diǎn)為根的子樹刪除以指定結(jié)點(diǎn)為根的子樹，一方面要將子樹從二叉樹中刪除，另一方面要將子樹中的結(jié)點(diǎn)釋放。將子樹從二叉樹中刪除是通過將指定結(jié)點(diǎn)的雙親結(jié)點(diǎn)的指針值置空來實(shí)現(xiàn)（若刪除的是整棵二叉樹，則應(yīng)將根結(jié)點(diǎn)指針值置空）。將子樹中的結(jié)點(diǎn)釋放，就是采用類似于遍歷子樹中所有結(jié)點(diǎn)的方式將各結(jié)點(diǎn)占據(jù)的內(nèi)存釋放。5.4.2二叉樹常用操作的實(shí)現(xiàn)二叉樹常用操作的實(shí)現(xiàn)n3.根據(jù)關(guān)鍵字查找結(jié)點(diǎn)根據(jù)關(guān)鍵字查找結(jié)點(diǎn) 根據(jù)

23、關(guān)鍵字查找結(jié)點(diǎn)，實(shí)質(zhì)上就是按照某種規(guī)則依次訪問二叉樹中的每一結(jié)點(diǎn)，直至找到與關(guān)鍵字匹配的結(jié)點(diǎn)。因此，同遍歷算法一樣，根據(jù)關(guān)鍵字查找結(jié)點(diǎn)也可以采用遞歸方式和非遞歸方式。5.4.2二叉樹常用操作的實(shí)現(xiàn)二叉樹常用操作的實(shí)現(xiàn)n哈夫曼樹，又稱最優(yōu)二叉樹，是指在一類有著相同葉子結(jié)點(diǎn)的樹中具有最短帶權(quán)路徑長度的二叉樹。哈夫曼樹在實(shí)際中有著廣泛的應(yīng)用。5.5.1 基本術(shù)語基本術(shù)語5.5.3 哈夫曼碼及其編解碼方法哈夫曼碼及其編解碼方法5.5.2 哈夫曼樹及其構(gòu)造方法哈夫曼樹及其構(gòu)造方法1.結(jié)點(diǎn)的權(quán)和帶權(quán)路徑長度結(jié)點(diǎn)的權(quán)和帶權(quán)路徑長度n在實(shí)際應(yīng)用中，往往給樹中的結(jié)點(diǎn)賦予一個(gè)具有某種意義的實(shí)數(shù)，該實(shí)數(shù)就稱為是結(jié)點(diǎn)

24、的權(quán)。結(jié)點(diǎn)的帶權(quán)路徑長度是指從樹根到該結(jié)點(diǎn)的路徑長度與結(jié)點(diǎn)的權(quán)的乘積。 5.5.1 基本術(shù)語基本術(shù)語2.樹的帶權(quán)路徑長度樹的帶權(quán)路徑長度n樹的帶權(quán)路徑長度是指樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和，記作（其中，n為葉子結(jié)點(diǎn)的數(shù)目，Wi為第i個(gè)葉子結(jié)點(diǎn)的權(quán)，Li為根結(jié)點(diǎn)到第i個(gè)葉子結(jié)點(diǎn)的路徑長度，可知WiLi為第i個(gè)葉子結(jié)點(diǎn)的帶權(quán)路徑長度）n例如，圖5-14中的2棵二叉樹，其帶權(quán)路徑長度分別為：WPL(a) = 2*(9+7+5)+3*(2+3) = 57WPL(b) = 1*3+3*(2+7+5+9) = 725.5.1 基本術(shù)語基本術(shù)語n在由n個(gè)葉子結(jié)點(diǎn)構(gòu)成的一類二叉樹中，具有最短帶權(quán)路徑長度的

25、二叉樹稱為哈夫曼樹。其構(gòu)造方法如下：n 已知n個(gè)權(quán)值為Wi（i = 1, 2, , n）的結(jié)點(diǎn)，將每個(gè)結(jié)點(diǎn)作為根結(jié)點(diǎn)生成n棵只有根結(jié)點(diǎn)的二叉樹Ti，形成森林F=T1, T2, , Tn。n從森林F中選出根結(jié)點(diǎn)權(quán)值最小的兩棵二叉樹Tp和Tq，并通過添加新的根結(jié)點(diǎn)將它們合并為一棵新二叉樹，新二叉樹中Tp和Tq分別作為根結(jié)點(diǎn)的左子樹和右子樹，且根結(jié)點(diǎn)的權(quán)值等于Tp和Tq兩棵二叉樹的根結(jié)點(diǎn)權(quán)值之和。以合并后生成的新二叉樹替代森林F中的原有二叉樹Tp和Tq。重復(fù)該步驟直至森林F中只存在一棵二叉樹。 5.5.2 哈夫曼樹及其構(gòu)造方法哈夫曼樹及其構(gòu)造方法n圖5-15是哈夫曼樹的構(gòu)造過程示例。初始有根結(jié)點(diǎn)權(quán)值

26、分別為2、3、5、7、9的5棵二叉樹組成的森林，如圖5-15（a）所示。從中選取根結(jié)點(diǎn)權(quán)值最小的兩棵二叉樹進(jìn)行合并，得到如圖5-15（b）所示的森林重復(fù)該合并操作，直至森林中只剩下一棵二叉樹，這棵二叉樹就是哈夫曼樹，如圖5-15（e）所示。 5.5.2 哈夫曼樹及其構(gòu)造方法哈夫曼樹及其構(gòu)造方法n哈夫曼碼是利用哈夫曼樹得到的一種不定長的二進(jìn)制編碼，它在數(shù)據(jù)壓縮領(lǐng)域有著廣泛應(yīng)用。利用哈夫曼碼進(jìn)行數(shù)據(jù)壓縮的基本原理是：對于出現(xiàn)頻率較高的字符，使用較短的編碼；而對于出現(xiàn)頻率較低的字符，則使用較長的編碼，從而使得用于表示字符序列的編碼總長度最短、節(jié)省存儲(chǔ)空間。 5.5.3 哈夫曼碼及其編解碼方法哈夫曼碼

27、及其編解碼方法1.1.哈夫曼編碼哈夫曼編碼 哈夫曼編碼是指將用其他編碼法表示的字符序列轉(zhuǎn)成用哈夫曼碼表示以減少存儲(chǔ)空間，其具體方法為：以要編碼的字符集C=c1, c2, , cn作為葉子結(jié)點(diǎn)、字符出現(xiàn)的頻度或次數(shù)W=w1, w2, , wn作為結(jié)點(diǎn)的權(quán)，構(gòu)造哈夫曼樹。規(guī)定哈夫曼樹中，從根結(jié)點(diǎn)開始，雙親結(jié)點(diǎn)到左孩子結(jié)點(diǎn)的分支標(biāo)為0，雙親結(jié)點(diǎn)到右孩子結(jié)點(diǎn)的分支標(biāo)為1。從根結(jié)點(diǎn)到某一葉子結(jié)點(diǎn)經(jīng)過的分支形成的編碼即是該葉子結(jié)點(diǎn)所對應(yīng)字符的哈夫曼碼。 5.5.3 哈夫曼碼及其編解碼方法哈夫曼碼及其編解碼方法n與雙親表示法相反，孩子表示法是通過在雙親結(jié)點(diǎn)中設(shè)置指向孩子結(jié)點(diǎn)的指針域來表示一棵樹。一個(gè)結(jié)點(diǎn)可以

28、有零個(gè)或多個(gè)孩子，根據(jù)結(jié)點(diǎn)中指向孩子結(jié)點(diǎn)的指針域數(shù)目是否固定可以分為定長孩子表示法和不定長孩子表示法。5.6.2 孩子表示法孩子表示法2.2.哈夫曼解碼哈夫曼解碼 哈夫曼解碼是指將用哈夫曼碼表示的字符序列轉(zhuǎn)成其他編碼法表示以讓計(jì)算機(jī)正確顯示字符內(nèi)容，其具體方法為：將用于表示字符序列的哈夫曼碼逐位取出并送入哈夫曼樹中。從哈夫曼樹的根結(jié)點(diǎn)開始，對于每一個(gè)結(jié)點(diǎn)，遇到位0則經(jīng)左分支到其左孩子，遇到位1則經(jīng)右分支到其右孩子。重復(fù)該過程直至到達(dá)某一個(gè)葉子結(jié)點(diǎn)，該葉子結(jié)點(diǎn)所對應(yīng)的字符即是解碼結(jié)果。解碼一個(gè)字符后回到哈夫曼樹的根結(jié)點(diǎn)開始解碼下一個(gè)字符。 例如，假設(shè)要解碼的哈夫曼碼是0100100011，則根據(jù)

29、圖5-16（b）的哈夫曼樹可得到解碼結(jié)果為FACE。5.5.2 哈夫曼樹及其構(gòu)造方法哈夫曼樹及其構(gòu)造方法5.5.3 哈夫曼碼及其編解碼方法哈夫曼碼及其編解碼方法5.6.1 雙親表示法雙親表示法5.6.3 孩子雙親表示法孩子雙親表示法5.6.2 孩子表示法孩子表示法5.6.3 孩子兄弟表示法孩子兄弟表示法n在樹結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)可以有零個(gè)或多個(gè)孩子結(jié)點(diǎn)，但至多只有一個(gè)雙親結(jié)點(diǎn)，因此，通過在孩子結(jié)點(diǎn)中設(shè)置一個(gè)指針域記錄其雙親結(jié)點(diǎn)的存儲(chǔ)位置就可以唯一的表示一棵樹。這種表示方法稱為雙親表示法。n雙親表示法通常采用順序存儲(chǔ)方式，從根結(jié)點(diǎn)開始編號為0，其他結(jié)點(diǎn)按照自上而下、從左至右的順序遞增編號；每個(gè)結(jié)點(diǎn)除

30、了有一個(gè)數(shù)據(jù)域存儲(chǔ)數(shù)據(jù)外，還有一個(gè)指針域存儲(chǔ)其雙親結(jié)點(diǎn)的位置；若一個(gè)結(jié)點(diǎn)沒有雙親結(jié)點(diǎn)，則其指針域賦值為-1。例如，對于圖5-17（a）所示的樹，其雙親表示法如圖5-17（b）所示。 5.6.1 雙親表示法雙親表示法n在雙親表示法中，通過一個(gè)結(jié)點(diǎn)的指針域可以直接獲取到該結(jié)點(diǎn)的雙親結(jié)點(diǎn)，但要獲取一個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)，則可能需要遍歷整棵樹。5.6.1 雙親表示法雙親表示法n1.1.定長孩子表示法定長孩子表示法 在定長孩子表示法中，每個(gè)結(jié)點(diǎn)中的指針域數(shù)目是固定的。若樹的度為n，則結(jié)點(diǎn)中指針域數(shù)目也為n。定長孩子表示法中的節(jié)點(diǎn)結(jié)構(gòu)如圖5-18所示。 5.6.2 孩子表示法孩子表示法n2.2.不定長孩子表示

31、法不定長孩子表示法n在不定長孩子表示法中，每個(gè)結(jié)點(diǎn)中的指針域數(shù)目是不固定的。若結(jié)點(diǎn)的度為d，則結(jié)點(diǎn)中指針域數(shù)目也為d。定長孩子表示法中的節(jié)點(diǎn)結(jié)構(gòu)如圖5-20所示。 5.6.2 孩子表示法孩子表示法5.7.1 樹、森林轉(zhuǎn)換為二叉樹樹、森林轉(zhuǎn)換為二叉樹5.7.2 二叉樹轉(zhuǎn)換為樹、森林二叉樹轉(zhuǎn)換為樹、森林n可見，定長孩子表示法需要預(yù)先確定樹的度，而且空指針域數(shù)量較多從而空間浪費(fèi)較大，但優(yōu)點(diǎn)是操作方便，不需人工管理內(nèi)存；不定長孩子表示法則相對靈活，可以根據(jù)結(jié)點(diǎn)的度動(dòng)態(tài)分配指針域，沒有空間浪費(fèi)，但需人工管理內(nèi)存，初學(xué)者操作起來容易出錯(cuò)。n與雙親表示法相反，在孩子表示法中，通過一個(gè)結(jié)點(diǎn)的指針域可以直接獲取到該結(jié)點(diǎn)的孩子結(jié)點(diǎn)，但要獲取一個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)，則可能需要遍歷整棵樹。 5.6.2 孩子表示法孩子表示法5.6.3 孩子雙親表示法孩子雙親表示法 孩子兄弟表示法，又稱為二叉鏈表表示法，與二叉樹的二叉鏈表表示法存儲(chǔ)結(jié)構(gòu)完全相同，只是結(jié)點(diǎn)中指針域的含義有所不同。5.6.3 孩子兄弟表示法孩子兄弟表示法n1.樹轉(zhuǎn)換為二叉樹樹轉(zhuǎn)換為二叉