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

1、第5章 樹(shù)和二叉樹(shù)（4課時(shí)）n樹(shù)是一種非常重要的非線(xiàn)性數(shù)據(jù)結(jié)構(gòu)。樹(shù)由n（n0）個(gè)數(shù)據(jù)元素組成，數(shù)據(jù)元素之間具有明顯的層次結(jié)構(gòu)。圖5-1是樹(shù)的樹(shù)形圖表示，由于它很像自然界中倒長(zhǎng)的樹(shù)，因此，被命名為“樹(shù)”。樹(shù)的樹(shù)形圖表示法規(guī)定在用直線(xiàn)連接起來(lái)的兩端結(jié)點(diǎn)中，處在上端的結(jié)點(diǎn)是前驅(qū)，處在下端的結(jié)點(diǎn)是后繼，如A是B的前驅(qū)，B是A的后繼。圖5-1中所示樹(shù)的邏輯結(jié)構(gòu)可表示為T(mén)=(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可以很直觀地看出樹(shù)具有如下結(jié)構(gòu)特性：只有最頂

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

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

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

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

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

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

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

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

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

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

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

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

14、由于順序表示非完全二叉樹(shù)時(shí)空間利用率較低，因此，二叉樹(shù)的順序表示在實(shí)際中應(yīng)用不多。下面主要圍繞二叉樹(shù)的創(chuàng)建和刪除這兩個(gè)最基本的操作介紹二叉樹(shù)順序表示的實(shí)現(xiàn)。n二叉樹(shù)順序表示的類(lèi)模板描述如下： 【描述5-1】二叉樹(shù)順序表示的類(lèi)模板描述。 分析：在類(lèi)模板中，需設(shè)置以下成員變量：一維數(shù)組m_pElement用于存儲(chǔ)二叉樹(shù)中各結(jié)點(diǎn)的值，數(shù)組類(lèi)型由二叉樹(shù)結(jié)點(diǎn)的值的類(lèi)型決定；整型變量m_nMaxSize用于存儲(chǔ)二叉樹(shù)中的最大結(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ù)的順序表示及其實(shí)現(xiàn)二叉樹(shù)的順序表示及其實(shí)現(xiàn)n3.二叉樹(shù)順序表示代碼復(fù)用示例二叉樹(shù)順序表示代碼復(fù)用示例【例5-1】基于二叉樹(shù)順序表示的C+實(shí)現(xiàn)代碼，完成如下操作： 創(chuàng)建圖5-9（b）所示的二叉樹(shù)，其中每一個(gè)結(jié)點(diǎn)保存一個(gè)字符信息，并通過(guò)逐層遍歷輸出各結(jié)點(diǎn)的值。 將以結(jié)點(diǎn)C為根結(jié)點(diǎn)的子樹(shù)刪除，并通過(guò)逐層遍歷輸出各結(jié)點(diǎn)的值。 清空二叉樹(shù)中的元素。 分析：對(duì)于由簡(jiǎn)單數(shù)據(jù)元素構(gòu)成的二叉樹(shù)，一般可以直接使用C+語(yǔ)言提供的基本數(shù)據(jù)類(lèi)型來(lái)描述數(shù)據(jù)元素，本例中可直接使用char類(lèi)型。5.3.1 二叉樹(shù)的順序表示及其實(shí)現(xiàn)二叉樹(shù)的順序表示及其實(shí)現(xiàn)n1.二叉樹(shù)的鏈?zhǔn)奖硎径鏄?shù)的鏈?zhǔn)奖硎?

16、在二叉樹(shù)的鏈?zhǔn)奖硎局?，結(jié)點(diǎn)之間的關(guān)系通過(guò)指針來(lái)體現(xiàn)。根據(jù)一個(gè)結(jié)點(diǎn)中指針域數(shù)量的不同，二叉樹(shù)的鏈?zhǔn)奖硎居挚梢苑譃槎骀湵肀硎竞腿骀湵肀硎?。圖5-10是一個(gè)用二叉鏈表表示法存儲(chǔ)二叉樹(shù)的例子。由于二叉樹(shù)中每個(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 二叉樹(shù)的鏈?zhǔn)奖硎炯捌鋵?shí)現(xiàn)二叉樹(shù)的鏈?zhǔn)奖硎炯捌鋵?shí)現(xiàn) 分析：創(chuàng)建二叉樹(shù)的方式有多種，這里采用基于隊(duì)列的層次創(chuàng)建方式。其創(chuàng)建步驟如圖5-13所示。 5.3.2 二叉樹(shù)的鏈?zhǔn)奖硎炯捌鋵?shí)現(xiàn)二叉樹(shù)的鏈?zhǔn)奖硎炯捌鋵?shí)現(xiàn)n圖5-11是一個(gè)用

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

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

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

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

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

22、沒(méi)有指向其雙親結(jié)點(diǎn)的指針，要獲取雙親結(jié)點(diǎn)則需要從根結(jié)點(diǎn)開(kāi)始遍歷二叉樹(shù)直至找到指定結(jié)點(diǎn)的雙親結(jié)點(diǎn)。因此，可以參照上一小節(jié)中給出的二叉樹(shù)遍歷算法，編寫(xiě)獲取雙親結(jié)點(diǎn)的程序。n2.刪除以指定結(jié)點(diǎn)為根的子樹(shù)刪除以指定結(jié)點(diǎn)為根的子樹(shù)刪除以指定結(jié)點(diǎn)為根的子樹(shù)，一方面要將子樹(shù)從二叉樹(shù)中刪除，另一方面要將子樹(shù)中的結(jié)點(diǎn)釋放。將子樹(shù)從二叉樹(shù)中刪除是通過(guò)將指定結(jié)點(diǎn)的雙親結(jié)點(diǎn)的指針值置空來(lái)實(shí)現(xiàn)（若刪除的是整棵二叉樹(shù)，則應(yīng)將根結(jié)點(diǎn)指針值置空）。將子樹(shù)中的結(jié)點(diǎn)釋放，就是采用類(lèi)似于遍歷子樹(shù)中所有結(jié)點(diǎn)的方式將各結(jié)點(diǎn)占據(jù)的內(nèi)存釋放。5.4.2二叉樹(shù)常用操作的實(shí)現(xiàn)二叉樹(shù)常用操作的實(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ī)則依次訪(fǎng)問(wèn)二叉樹(shù)中的每一結(jié)點(diǎn)，直至找到與關(guān)鍵字匹配的結(jié)點(diǎn)。因此，同遍歷算法一樣，根據(jù)關(guān)鍵字查找結(jié)點(diǎn)也可以采用遞歸方式和非遞歸方式。5.4.2二叉樹(shù)常用操作的實(shí)現(xiàn)二叉樹(shù)常用操作的實(shí)現(xiàn)n哈夫曼樹(shù)，又稱(chēng)最優(yōu)二叉樹(shù)，是指在一類(lèi)有著相同葉子結(jié)點(diǎn)的樹(shù)中具有最短帶權(quán)路徑長(zhǎng)度的二叉樹(shù)。哈夫曼樹(shù)在實(shí)際中有著廣泛的應(yīng)用。5.5.1 基本術(shù)語(yǔ)基本術(shù)語(yǔ)5.5.3 哈夫曼碼及其編解碼方法哈夫曼碼及其編解碼方法5.5.2 哈夫曼樹(shù)及其構(gòu)造方法哈夫曼樹(shù)及其構(gòu)造方法1.結(jié)點(diǎn)的權(quán)和帶權(quán)路徑長(zhǎng)度結(jié)點(diǎn)的權(quán)和帶權(quán)路徑長(zhǎng)度n在實(shí)際應(yīng)用中，往往給樹(shù)中的結(jié)點(diǎn)賦予一個(gè)具有某種意義的實(shí)數(shù)，該實(shí)數(shù)就稱(chēng)為是結(jié)點(diǎn)

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

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

26、分別為2、3、5、7、9的5棵二叉樹(shù)組成的森林，如圖5-15（a）所示。從中選取根結(jié)點(diǎn)權(quán)值最小的兩棵二叉樹(shù)進(jìn)行合并，得到如圖5-15（b）所示的森林重復(fù)該合并操作，直至森林中只剩下一棵二叉樹(shù)，這棵二叉樹(shù)就是哈夫曼樹(shù)，如圖5-15（e）所示。 5.5.2 哈夫曼樹(shù)及其構(gòu)造方法哈夫曼樹(shù)及其構(gòu)造方法n哈夫曼碼是利用哈夫曼樹(shù)得到的一種不定長(zhǎng)的二進(jìn)制編碼，它在數(shù)據(jù)壓縮領(lǐng)域有著廣泛應(yīng)用。利用哈夫曼碼進(jìn)行數(shù)據(jù)壓縮的基本原理是：對(duì)于出現(xiàn)頻率較高的字符，使用較短的編碼；而對(duì)于出現(xiàn)頻率較低的字符，則使用較長(zhǎng)的編碼，從而使得用于表示字符序列的編碼總長(zhǎng)度最短、節(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)造哈夫曼樹(shù)。規(guī)定哈夫曼樹(shù)中，從根結(jié)點(diǎn)開(kāi)始，雙親結(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)過(guò)的分支形成的編碼即是該葉子結(jié)點(diǎn)所對(duì)應(yīng)字符的哈夫曼碼。 5.5.3 哈夫曼碼及其編解碼方法哈夫曼碼及其編解碼方法n與雙親表示法相反，孩子表示法是通過(guò)在雙親結(jié)點(diǎn)中設(shè)置指向孩子結(jié)點(diǎn)的指針域來(lái)表示一棵樹(shù)。一個(gè)結(jié)點(diǎn)可以

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

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

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

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