數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言樹(shù)形結(jié)構(gòu)學(xué)習(xí)教案

1、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(sh j ji u)C語(yǔ)言樹(shù)形結(jié)構(gòu)語(yǔ)言樹(shù)形結(jié)構(gòu)第一頁(yè)，共115頁(yè)。7.1.1 7.1.1 樹(shù)的定義樹(shù)的定義 形式化定義：形式化定義： 樹(shù)：樹(shù)：T TK,RK,R。K K是包含是包含n n個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)(ji din)(ji din)的的有窮集合有窮集合(n0),(n0),關(guān)系關(guān)系R R滿足以下條件滿足以下條件: : (1) (1)有且僅有一個(gè)結(jié)點(diǎn)有且僅有一個(gè)結(jié)點(diǎn)(ji din)k0K,(ji din)k0K,它對(duì)于它對(duì)于關(guān)系關(guān)系R R來(lái)說(shuō)沒(méi)有前驅(qū)結(jié)點(diǎn)來(lái)說(shuō)沒(méi)有前驅(qū)結(jié)點(diǎn)(ji din),(ji din),結(jié)點(diǎn)結(jié)點(diǎn)(ji din)k0(ji din)k0稱作樹(shù)的根。稱作樹(shù)的根。 (2

2、) (2)除結(jié)點(diǎn)除結(jié)點(diǎn)(ji din)k0(ji din)k0外外,K,K中的每個(gè)結(jié)點(diǎn)中的每個(gè)結(jié)點(diǎn)(ji (ji din)din)對(duì)于關(guān)系對(duì)于關(guān)系R R來(lái)說(shuō)都有且僅有一個(gè)前驅(qū)結(jié)點(diǎn)來(lái)說(shuō)都有且僅有一個(gè)前驅(qū)結(jié)點(diǎn)(ji (ji din)din)。 (3)K (3)K中每個(gè)結(jié)點(diǎn)中每個(gè)結(jié)點(diǎn)(ji din)(ji din)對(duì)于關(guān)系對(duì)于關(guān)系R R來(lái)說(shuō)可以來(lái)說(shuō)可以有多個(gè)后繼結(jié)點(diǎn)有多個(gè)后繼結(jié)點(diǎn)(ji din)(ji din)。第1頁(yè)/共115頁(yè)第二頁(yè)，共115頁(yè)。遞歸定義：遞歸定義： 樹(shù)是由樹(shù)是由n(n0)個(gè)結(jié)點(diǎn)組成個(gè)結(jié)點(diǎn)組成(z chn)的有限集合的有限集合(記為記為T(mén))。其中。其中, 如果如果n=0,它是一棵

3、空樹(shù)它是一棵空樹(shù),這是樹(shù)的特例；這是樹(shù)的特例； 如果如果n0,這這n個(gè)結(jié)點(diǎn)中存在個(gè)結(jié)點(diǎn)中存在(有僅存在有僅存在)一個(gè)結(jié)點(diǎn)一個(gè)結(jié)點(diǎn)作為樹(shù)的根結(jié)點(diǎn)作為樹(shù)的根結(jié)點(diǎn),簡(jiǎn)稱為根簡(jiǎn)稱為根(root),其余結(jié)點(diǎn)可分為其余結(jié)點(diǎn)可分為m (m0)個(gè)互不相交的有限集個(gè)互不相交的有限集T1,T2,Tm,其中每一其中每一棵子集本身又是一棵符合本定義的樹(shù)棵子集本身又是一棵符合本定義的樹(shù),稱為根稱為根root的的子樹(shù)。子樹(shù)。第2頁(yè)/共115頁(yè)第三頁(yè)，共115頁(yè)。7 . 1 . 2 7 . 1 . 2 樹(shù) 的 表 示樹(shù) 的 表 示(biosh)(biosh) (1) (1)樹(shù)形表示法。這是樹(shù)的最基本的表示樹(shù)形表示法。這是樹(shù)

4、的最基本的表示, ,使用一使用一棵 倒 置 的 樹(shù) 表 示 樹(shù) 結(jié) 構(gòu)棵 倒 置 的 樹(shù) 表 示 樹(shù) 結(jié) 構(gòu) , , 非 常 直 觀 和 形 象非 常 直 觀 和 形 象(xngxing)(xngxing)。下圖就是采用這種表示法。下圖就是采用這種表示法。 A C G J B E D F I H M K L 樹(shù)形表示法樹(shù)形表示法 第3頁(yè)/共115頁(yè)第四頁(yè)，共115頁(yè)。 (2)文氏圖表示法。使用集合以及集合文氏圖表示法。使用集合以及集合的包含關(guān)系描述的包含關(guān)系描述(mio sh)樹(shù)結(jié)構(gòu)。下圖樹(shù)結(jié)構(gòu)。下圖就是樹(shù)的文氏圖表示法。就是樹(shù)的文氏圖表示法。 H L D K I M C G J E B F

5、文氏圖表示法文氏圖表示法 A 第4頁(yè)/共115頁(yè)第五頁(yè)，共115頁(yè)。 (3)凹入表示法。使用凹入表示法。使用(shyng)線段的伸縮描線段的伸縮描述樹(shù)結(jié)構(gòu)。下圖是樹(shù)的凹入表示法。述樹(shù)結(jié)構(gòu)。下圖是樹(shù)的凹入表示法。第5頁(yè)/共115頁(yè)第六頁(yè)，共115頁(yè)。 (4)括號(hào)表示法。將樹(shù)的根結(jié)點(diǎn)寫(xiě)在括號(hào)的左邊括號(hào)表示法。將樹(shù)的根結(jié)點(diǎn)寫(xiě)在括號(hào)的左邊,除除根結(jié)點(diǎn)之外的其余根結(jié)點(diǎn)之外的其余(qy)結(jié)點(diǎn)寫(xiě)在括號(hào)中并用逗號(hào)間隔結(jié)點(diǎn)寫(xiě)在括號(hào)中并用逗號(hào)間隔來(lái)描述樹(shù)結(jié)構(gòu)。下圖是樹(shù)的括號(hào)表示法。來(lái)描述樹(shù)結(jié)構(gòu)。下圖是樹(shù)的括號(hào)表示法。 括號(hào)表示法括號(hào)表示法 A(B(E,F),C(G(J),D(H,I(K,L,M) 第6頁(yè)/共115

6、頁(yè)第七頁(yè)，共115頁(yè)。7.1.3 7.1.3 樹(shù)的基本術(shù)語(yǔ)樹(shù)的基本術(shù)語(yǔ) 1. 1. 結(jié)點(diǎn)的度與樹(shù)的度：樹(shù)中某個(gè)結(jié)點(diǎn)的度與樹(shù)的度：樹(shù)中某個(gè)(mu )(mu )結(jié)點(diǎn)結(jié)點(diǎn)的子樹(shù)的個(gè)數(shù)稱為該結(jié)點(diǎn)的度。樹(shù)中各結(jié)點(diǎn)的度的最大的子樹(shù)的個(gè)數(shù)稱為該結(jié)點(diǎn)的度。樹(shù)中各結(jié)點(diǎn)的度的最大值稱為樹(shù)的度值稱為樹(shù)的度, ,通常將度為通常將度為m m的樹(shù)稱為的樹(shù)稱為m m次樹(shù)。次樹(shù)。 2. 2. 分支結(jié)點(diǎn)與葉結(jié)點(diǎn)：度不為零的結(jié)點(diǎn)稱為非分支結(jié)點(diǎn)與葉結(jié)點(diǎn)：度不為零的結(jié)點(diǎn)稱為非終端結(jié)點(diǎn)終端結(jié)點(diǎn), ,又叫分支結(jié)點(diǎn)。度為零的結(jié)點(diǎn)稱為終端結(jié)點(diǎn)或又叫分支結(jié)點(diǎn)。度為零的結(jié)點(diǎn)稱為終端結(jié)點(diǎn)或葉結(jié)點(diǎn)。在分支結(jié)點(diǎn)中葉結(jié)點(diǎn)。在分支結(jié)點(diǎn)中, ,每個(gè)結(jié)點(diǎn)的分

7、支數(shù)就是該結(jié)點(diǎn)的每個(gè)結(jié)點(diǎn)的分支數(shù)就是該結(jié)點(diǎn)的度。如對(duì)于度為度。如對(duì)于度為1 1的結(jié)點(diǎn)的結(jié)點(diǎn), ,其分支數(shù)為其分支數(shù)為1,1,被稱為單分支結(jié)被稱為單分支結(jié)點(diǎn)；對(duì)于度為點(diǎn)；對(duì)于度為2 2的結(jié)點(diǎn)的結(jié)點(diǎn), ,其分支數(shù)為其分支數(shù)為2,2,被稱為雙分支結(jié)點(diǎn)被稱為雙分支結(jié)點(diǎn), ,其余類推。其余類推。第7頁(yè)/共115頁(yè)第八頁(yè)，共115頁(yè)。 3. 路徑與路徑長(zhǎng)度：對(duì)于任意兩個(gè)結(jié)點(diǎn)路徑與路徑長(zhǎng)度：對(duì)于任意兩個(gè)結(jié)點(diǎn)ki和和kj,若樹(shù)若樹(shù)中存在一個(gè)結(jié)點(diǎn)序列中存在一個(gè)結(jié)點(diǎn)序列ki,ki1,ki2,kin,kj,使得序列中除使得序列中除ki外的任一結(jié)點(diǎn)都是其在序列中的前一個(gè)結(jié)點(diǎn)的后繼外的任一結(jié)點(diǎn)都是其在序列中的前一個(gè)結(jié)點(diǎn)

8、的后繼,則稱則稱該結(jié)點(diǎn)序列為由該結(jié)點(diǎn)序列為由ki到到kj的一條路徑的一條路徑,用路徑所通過(guò)的結(jié)點(diǎn)序用路徑所通過(guò)的結(jié)點(diǎn)序列列(ki,ki1,ki2,kj)表示這條路徑。路徑的長(zhǎng)度等于路徑表示這條路徑。路徑的長(zhǎng)度等于路徑所通過(guò)的結(jié)點(diǎn)數(shù)目減所通過(guò)的結(jié)點(diǎn)數(shù)目減1(即路徑上分支數(shù)目即路徑上分支數(shù)目)?？梢?jiàn)?？梢?jiàn),路徑就路徑就是從是從ki出發(fā)出發(fā)“自上而下自上而下”到達(dá)到達(dá)kj所通過(guò)的樹(shù)中結(jié)點(diǎn)序列。顯所通過(guò)的樹(shù)中結(jié)點(diǎn)序列。顯然然(xinrn),從樹(shù)的根結(jié)點(diǎn)到樹(shù)中其余結(jié)點(diǎn)均存在一條路從樹(shù)的根結(jié)點(diǎn)到樹(shù)中其余結(jié)點(diǎn)均存在一條路徑。徑。第8頁(yè)/共115頁(yè)第九頁(yè)，共115頁(yè)。 4. 4. 孩子結(jié)點(diǎn)、雙親結(jié)點(diǎn)和兄弟結(jié)點(diǎn)

9、：在孩子結(jié)點(diǎn)、雙親結(jié)點(diǎn)和兄弟結(jié)點(diǎn)：在一棵樹(shù)中一棵樹(shù)中, ,每個(gè)結(jié)點(diǎn)的后繼每個(gè)結(jié)點(diǎn)的后繼, ,被稱作該結(jié)點(diǎn)的被稱作該結(jié)點(diǎn)的孩子結(jié)點(diǎn)孩子結(jié)點(diǎn)( (或子女結(jié)點(diǎn)或子女結(jié)點(diǎn)) )。相應(yīng)地。相應(yīng)地, ,該結(jié)點(diǎn)被該結(jié)點(diǎn)被稱作孩子結(jié)點(diǎn)的雙親結(jié)點(diǎn)稱作孩子結(jié)點(diǎn)的雙親結(jié)點(diǎn)( (或父母結(jié)點(diǎn)或父母結(jié)點(diǎn)) )。具。具有有(jyu)(jyu)同一雙親的孩子結(jié)點(diǎn)互為兄弟同一雙親的孩子結(jié)點(diǎn)互為兄弟結(jié)點(diǎn)。進(jìn)一步推廣這些關(guān)系結(jié)點(diǎn)。進(jìn)一步推廣這些關(guān)系, ,可以把每個(gè)結(jié)可以把每個(gè)結(jié)點(diǎn)的所有子樹(shù)中的結(jié)點(diǎn)稱為該結(jié)點(diǎn)的子孫結(jié)點(diǎn)的所有子樹(shù)中的結(jié)點(diǎn)稱為該結(jié)點(diǎn)的子孫結(jié)點(diǎn)點(diǎn), ,從樹(shù)根結(jié)點(diǎn)到達(dá)該結(jié)點(diǎn)的路徑上經(jīng)過(guò)的從樹(shù)根結(jié)點(diǎn)到達(dá)該結(jié)點(diǎn)的路徑上經(jīng)過(guò)的所

10、有結(jié)點(diǎn)被稱作該結(jié)點(diǎn)的祖先結(jié)點(diǎn)。所有結(jié)點(diǎn)被稱作該結(jié)點(diǎn)的祖先結(jié)點(diǎn)。第9頁(yè)/共115頁(yè)第十頁(yè)，共115頁(yè)。 5. 結(jié)點(diǎn)的層次和樹(shù)的高度：樹(shù)中的每個(gè)結(jié)點(diǎn)都處結(jié)點(diǎn)的層次和樹(shù)的高度：樹(shù)中的每個(gè)結(jié)點(diǎn)都處在一定的層次上。結(jié)點(diǎn)的層次從樹(shù)根開(kāi)始定義在一定的層次上。結(jié)點(diǎn)的層次從樹(shù)根開(kāi)始定義,根結(jié)點(diǎn)根結(jié)點(diǎn)為第為第1層層,它的孩子結(jié)點(diǎn)為第它的孩子結(jié)點(diǎn)為第2層層,以此類推以此類推,一個(gè)結(jié)點(diǎn)所一個(gè)結(jié)點(diǎn)所在的層次為其雙親結(jié)點(diǎn)所在的層次加在的層次為其雙親結(jié)點(diǎn)所在的層次加1。樹(shù)中結(jié)點(diǎn)的。樹(shù)中結(jié)點(diǎn)的最大層次稱為樹(shù)的高度最大層次稱為樹(shù)的高度(或樹(shù)的深度或樹(shù)的深度)。 7. 有序樹(shù)和無(wú)序樹(shù)：若樹(shù)中各結(jié)點(diǎn)的子樹(shù)是按照有序樹(shù)和無(wú)序樹(shù)：若樹(shù)

11、中各結(jié)點(diǎn)的子樹(shù)是按照一定的次序從左向右安排一定的次序從左向右安排(npi)的的,且相對(duì)次序是不且相對(duì)次序是不能隨意變換的能隨意變換的,則稱為有序樹(shù)則稱為有序樹(shù),否則稱為無(wú)序樹(shù)。否則稱為無(wú)序樹(shù)。第10頁(yè)/共115頁(yè)第十一頁(yè)，共115頁(yè)。 7. 森林：森林：n(n0)個(gè)互不相交的樹(shù)的集合稱個(gè)互不相交的樹(shù)的集合稱為森林。森林的概念與樹(shù)的概念十分相近為森林。森林的概念與樹(shù)的概念十分相近,因?yàn)橐驗(yàn)?yn wi)只要把樹(shù)的根結(jié)點(diǎn)刪去就成了森林。只要把樹(shù)的根結(jié)點(diǎn)刪去就成了森林。反之反之,只要給只要給n棵獨(dú)立的樹(shù)加上一個(gè)結(jié)點(diǎn)棵獨(dú)立的樹(shù)加上一個(gè)結(jié)點(diǎn),并把這并把這n棵樹(shù)作為該結(jié)點(diǎn)的子樹(shù)棵樹(shù)作為該結(jié)點(diǎn)的子樹(shù),則森林

12、就變成了樹(shù)。則森林就變成了樹(shù)。第11頁(yè)/共115頁(yè)第十二頁(yè)，共115頁(yè)。7.1.4 7.1.4 樹(shù)的性質(zhì)樹(shù)的性質(zhì)性質(zhì)性質(zhì)1 1 樹(shù)中的結(jié)點(diǎn)數(shù)等于所有結(jié)點(diǎn)的度數(shù)加樹(shù)中的結(jié)點(diǎn)數(shù)等于所有結(jié)點(diǎn)的度數(shù)加1 1。 證明：根據(jù)證明：根據(jù)(gnj)(gnj)樹(shù)的定義樹(shù)的定義, ,在一棵樹(shù)中在一棵樹(shù)中, ,除樹(shù)根除樹(shù)根結(jié)點(diǎn)外結(jié)點(diǎn)外, ,每個(gè)結(jié)點(diǎn)有且僅有一個(gè)前驅(qū)結(jié)點(diǎn)。也就是說(shuō)每個(gè)結(jié)點(diǎn)有且僅有一個(gè)前驅(qū)結(jié)點(diǎn)。也就是說(shuō), ,每每個(gè)結(jié)點(diǎn)與指向它的一個(gè)分支一一對(duì)應(yīng)個(gè)結(jié)點(diǎn)與指向它的一個(gè)分支一一對(duì)應(yīng), ,所以除樹(shù)根之外的所以除樹(shù)根之外的結(jié)點(diǎn)數(shù)等于所有結(jié)點(diǎn)的分支數(shù)結(jié)點(diǎn)數(shù)等于所有結(jié)點(diǎn)的分支數(shù)( (度數(shù)度數(shù)),),從而可得樹(shù)中的結(jié)從

13、而可得樹(shù)中的結(jié)點(diǎn)數(shù)等于所有結(jié)點(diǎn)的度數(shù)加點(diǎn)數(shù)等于所有結(jié)點(diǎn)的度數(shù)加1 1。第12頁(yè)/共115頁(yè)第十三頁(yè)，共115頁(yè)。 性質(zhì)性質(zhì)2 度為度為m的樹(shù)中第的樹(shù)中第i層上至多有層上至多有mi-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn),這里應(yīng)這里應(yīng)有有i1。 證明證明(采用數(shù)學(xué)歸納法采用數(shù)學(xué)歸納法) 對(duì)于第一層對(duì)于第一層,因?yàn)闃?shù)中的第一層上只有一個(gè)結(jié)點(diǎn)因?yàn)闃?shù)中的第一層上只有一個(gè)結(jié)點(diǎn),即整個(gè)即整個(gè)樹(shù)的根結(jié)點(diǎn)樹(shù)的根結(jié)點(diǎn),而由而由i=1代入代入mi-1,得得mi-1=m1-1=1,也同樣得到也同樣得到只有一個(gè)結(jié)點(diǎn)只有一個(gè)結(jié)點(diǎn),顯然結(jié)論成立。顯然結(jié)論成立。 假設(shè)假設(shè)(jish)對(duì)于第對(duì)于第(i-1)層層(i1)命題成立命題成立,即度為即度為

14、m的的樹(shù)中第樹(shù)中第(i-1)層上至多有層上至多有mi-2個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn),則根據(jù)樹(shù)的度的定義則根據(jù)樹(shù)的度的定義,度度為為m的樹(shù)中每個(gè)結(jié)點(diǎn)至多有的樹(shù)中每個(gè)結(jié)點(diǎn)至多有m個(gè)孩子結(jié)點(diǎn)個(gè)孩子結(jié)點(diǎn),所以第所以第i層上的結(jié)層上的結(jié)點(diǎn)數(shù)至多為第點(diǎn)數(shù)至多為第(i-1)層上結(jié)點(diǎn)數(shù)的層上結(jié)點(diǎn)數(shù)的m倍倍,即至多為即至多為mi-2m=mi-1個(gè)個(gè),這與命題相同這與命題相同,故命題成立。故命題成立。第13頁(yè)/共115頁(yè)第十四頁(yè)，共115頁(yè)。 性質(zhì)性質(zhì)3 高度高度(god)為為h的的m次樹(shù)至多有次樹(shù)至多有 個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。 證明：由樹(shù)的性質(zhì)證明：由樹(shù)的性質(zhì)2可知可知,第第i層上最多結(jié)點(diǎn)數(shù)為層上最多結(jié)點(diǎn)數(shù)為mi-1(i=1,2,

15、h),顯然當(dāng)高度顯然當(dāng)高度(god)為為h的的m次樹(shù)次樹(shù)(即度為即度為m的的樹(shù)樹(shù))上每一層都達(dá)到最多結(jié)點(diǎn)數(shù)時(shí)上每一層都達(dá)到最多結(jié)點(diǎn)數(shù)時(shí),整個(gè)整個(gè)m次樹(shù)具有最多結(jié)次樹(shù)具有最多結(jié)點(diǎn)數(shù)點(diǎn)數(shù),因此有：因此有：整 個(gè) 樹(shù) 的 最 多 結(jié) 點(diǎn) 數(shù)整 個(gè) 樹(shù) 的 最 多 結(jié) 點(diǎn) 數(shù) = 每 一 層 最 多 結(jié) 點(diǎn) 數(shù) 之 和每 一 層 最 多 結(jié) 點(diǎn) 數(shù) 之 和=m0+m1+m2+mh-1 = 。11 mmh11 mmh第14頁(yè)/共115頁(yè)第十五頁(yè)，共115頁(yè)。 性質(zhì)性質(zhì)4 具有具有n個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)(ji din)的的m次樹(shù)的最小高度為次樹(shù)的最小高度為logm(n(m-1)+1)。 證明：設(shè)具有證明：設(shè)具有n

16、個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)(ji din)的的m次樹(shù)的高度為次樹(shù)的高度為h,若若在該樹(shù)中前在該樹(shù)中前h-1層都是滿的層都是滿的,即每一層的結(jié)點(diǎn)即每一層的結(jié)點(diǎn)(ji din)數(shù)都數(shù)都等于等于mi-1個(gè)個(gè)(1ih-1),第第h層層(即最后一層即最后一層)的結(jié)點(diǎn)的結(jié)點(diǎn)(ji din)數(shù)可能滿數(shù)可能滿,也可能不滿也可能不滿,則該樹(shù)具有最小的高度。其高度則該樹(shù)具有最小的高度。其高度h可可計(jì)算如下：計(jì)算如下：第15頁(yè)/共115頁(yè)第十六頁(yè)，共115頁(yè)。根據(jù)樹(shù)的性質(zhì)根據(jù)樹(shù)的性質(zhì)(xngzh)3可得：可得： n乘乘(m-1)后得：后得： mh-1n(m-1)+1mh以以m為底取對(duì)數(shù)后得：為底取對(duì)數(shù)后得：h-1logm(n(m

17、-1)+1)h即即logm(n(m-1)+1)hlogm(n(m-1)+1)+1因因h只能取整數(shù)只能取整數(shù),所以所以 h=logm(n(m-1)+1)結(jié)論得證。結(jié)論得證。111 mmh11 mmh第16頁(yè)/共115頁(yè)第十七頁(yè)，共115頁(yè)。 例例7.1 含含n個(gè)結(jié)點(diǎn)的三次樹(shù)的最小高度個(gè)結(jié)點(diǎn)的三次樹(shù)的最小高度(god)是多少？是多少？ 解：設(shè)含解：設(shè)含n個(gè)結(jié)點(diǎn)的個(gè)結(jié)點(diǎn)的(為完全三次樹(shù)時(shí)高度為完全三次樹(shù)時(shí)高度(god)最最小小)的三次樹(shù)的最小高度的三次樹(shù)的最小高度(god)為為h,則有：則有： 1+3+9+3h-2n1+3+9+3h-1 (3h-1-1)/2 n (3h-1)/2 3h-12n+13

18、h 即：即：h= log3(2n+1)第17頁(yè)/共115頁(yè)第十八頁(yè)，共115頁(yè)。7.1.5 7.1.5 樹(shù)的基本樹(shù)的基本(jbn)(jbn)運(yùn)運(yùn)算算 樹(shù)的運(yùn)算主要樹(shù)的運(yùn)算主要(zhyo)(zhyo)分為三大類：分為三大類： 第一類第一類, ,尋找滿足某種特定關(guān)系的結(jié)點(diǎn)尋找滿足某種特定關(guān)系的結(jié)點(diǎn), ,如尋找當(dāng)如尋找當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)等；前結(jié)點(diǎn)的雙親結(jié)點(diǎn)等； 第二類第二類, ,插入或刪除某個(gè)結(jié)點(diǎn)插入或刪除某個(gè)結(jié)點(diǎn), ,如在樹(shù)的當(dāng)前結(jié)點(diǎn)如在樹(shù)的當(dāng)前結(jié)點(diǎn)上插入一個(gè)新結(jié)點(diǎn)或刪除當(dāng)前結(jié)點(diǎn)的第上插入一個(gè)新結(jié)點(diǎn)或刪除當(dāng)前結(jié)點(diǎn)的第i i個(gè)孩子結(jié)點(diǎn)個(gè)孩子結(jié)點(diǎn)等；等； 第三類第三類, ,遍歷樹(shù)中每個(gè)結(jié)點(diǎn)遍歷樹(shù)中每個(gè)

19、結(jié)點(diǎn), ,這里著重介紹。這里著重介紹。第18頁(yè)/共115頁(yè)第十九頁(yè)，共115頁(yè)。 樹(shù)的遍歷運(yùn)算是指按某種方式訪問(wèn)樹(shù)中的每一個(gè)樹(shù)的遍歷運(yùn)算是指按某種方式訪問(wèn)樹(shù)中的每一個(gè)(y )結(jié)點(diǎn)且每一個(gè)結(jié)點(diǎn)且每一個(gè)(y )結(jié)點(diǎn)只被訪問(wèn)一次。樹(shù)的遍結(jié)點(diǎn)只被訪問(wèn)一次。樹(shù)的遍歷運(yùn)算的算法主要有先根遍歷和后根遍歷兩種。注意歷運(yùn)算的算法主要有先根遍歷和后根遍歷兩種。注意,下面的先根遍歷和后根遍歷算法都是遞歸的。下面的先根遍歷和后根遍歷算法都是遞歸的。 1. 先根遍歷先根遍歷 先根遍歷過(guò)程為：先根遍歷過(guò)程為： (1)訪問(wèn)根結(jié)點(diǎn)；訪問(wèn)根結(jié)點(diǎn)； (2)按照從左到右的次序先根遍歷根結(jié)點(diǎn)的每一棵子按照從左到右的次序先根遍歷根結(jié)點(diǎn)

20、的每一棵子樹(shù)。樹(shù)。 第19頁(yè)/共115頁(yè)第二十頁(yè)，共115頁(yè)。2. 后根遍歷后根遍歷 后根遍歷過(guò)程為：后根遍歷過(guò)程為： (1)按照從左到右的次序后根遍歷根結(jié)點(diǎn)按照從左到右的次序后根遍歷根結(jié)點(diǎn)(ji din)的每的每一棵子樹(shù)；一棵子樹(shù)； (2)訪問(wèn)根結(jié)點(diǎn)訪問(wèn)根結(jié)點(diǎn)(ji din)。第20頁(yè)/共115頁(yè)第二十一頁(yè)，共115頁(yè)。7.1.6 7.1.6 樹(shù)的存儲(chǔ)樹(shù)的存儲(chǔ)(cn ch)(cn ch)結(jié)結(jié)構(gòu)構(gòu)1. 1. 雙親存儲(chǔ)結(jié)構(gòu)雙親存儲(chǔ)結(jié)構(gòu) 這種存儲(chǔ)結(jié)構(gòu)是一種順序存儲(chǔ)結(jié)構(gòu)這種存儲(chǔ)結(jié)構(gòu)是一種順序存儲(chǔ)結(jié)構(gòu), ,用一組連續(xù)空用一組連續(xù)空間 存 儲(chǔ) 樹(shù) 的 所 有 結(jié) 點(diǎn)間 存 儲(chǔ) 樹(shù) 的 所 有 結(jié) 點(diǎn) ,

21、 , 同 時(shí) 在 每 個(gè) 結(jié) 點(diǎn) 中 附 設(shè)同 時(shí) 在 每 個(gè) 結(jié) 點(diǎn) 中 附 設(shè)(fsh)(fsh)一個(gè)偽指針指示其雙親結(jié)點(diǎn)的位置。一個(gè)偽指針指示其雙親結(jié)點(diǎn)的位置。 A D B C G E F A -1 B 0 C 0 D 0 E 2 F 2 G 2 0 1 2 3 4 5 6 (a) (b) 樹(shù)的雙親樹(shù)的雙親(shungqn)(shungqn)存儲(chǔ)結(jié)構(gòu)示意圖存儲(chǔ)結(jié)構(gòu)示意圖第21頁(yè)/共115頁(yè)第二十二頁(yè)，共115頁(yè)。2. 孩子孩子(hi zi)鏈存儲(chǔ)結(jié)構(gòu)鏈存儲(chǔ)結(jié)構(gòu) 孩子孩子(hi zi)鏈存儲(chǔ)結(jié)構(gòu)可按樹(shù)的度鏈存儲(chǔ)結(jié)構(gòu)可按樹(shù)的度(即樹(shù)中所有結(jié)點(diǎn)度即樹(shù)中所有結(jié)點(diǎn)度的最大值的最大值)設(shè)計(jì)結(jié)點(diǎn)的孩子

22、設(shè)計(jì)結(jié)點(diǎn)的孩子(hi zi)結(jié)點(diǎn)指針域個(gè)數(shù)。下圖結(jié)點(diǎn)指針域個(gè)數(shù)。下圖(a)的樹(shù)對(duì)應(yīng)的孩子的樹(shù)對(duì)應(yīng)的孩子(hi zi)鏈存儲(chǔ)結(jié)構(gòu)如圖鏈存儲(chǔ)結(jié)構(gòu)如圖(b)所示。所示。 A B C F D E (a) G A B C D E F G (b) 樹(shù)的孩子鏈存儲(chǔ)樹(shù)的孩子鏈存儲(chǔ)(cn ch)(cn ch)結(jié)結(jié)構(gòu)示意圖構(gòu)示意圖第22頁(yè)/共115頁(yè)第二十三頁(yè)，共115頁(yè)。3. 孩子兄弟鏈存儲(chǔ)結(jié)構(gòu)孩子兄弟鏈存儲(chǔ)結(jié)構(gòu) 孩子兄弟鏈存儲(chǔ)結(jié)構(gòu)是為每個(gè)結(jié)點(diǎn)設(shè)計(jì)三個(gè)域：孩子兄弟鏈存儲(chǔ)結(jié)構(gòu)是為每個(gè)結(jié)點(diǎn)設(shè)計(jì)三個(gè)域：一個(gè)一個(gè)(y )數(shù)據(jù)元素域數(shù)據(jù)元素域,一個(gè)一個(gè)(y )該結(jié)點(diǎn)的第一個(gè)該結(jié)點(diǎn)的第一個(gè)(y )孩子結(jié)點(diǎn)指針域孩子結(jié)點(diǎn)指針

23、域,一個(gè)一個(gè)(y )該結(jié)點(diǎn)的下一個(gè)該結(jié)點(diǎn)的下一個(gè)(y )兄弟結(jié)點(diǎn)指針域。下圖兄弟結(jié)點(diǎn)指針域。下圖(a)的樹(shù)對(duì)應(yīng)的孩子兄的樹(shù)對(duì)應(yīng)的孩子兄弟鏈存儲(chǔ)結(jié)構(gòu)如圖弟鏈存儲(chǔ)結(jié)構(gòu)如圖(b)所示。所示。 A B C F D E (a) G A B D C E G F (b) 樹(shù)的孩子兄弟鏈存儲(chǔ)樹(shù)的孩子兄弟鏈存儲(chǔ)(cn ch)(cn ch)結(jié)構(gòu)示意圖結(jié)構(gòu)示意圖第23頁(yè)/共115頁(yè)第二十四頁(yè)，共115頁(yè)。7 . 2 7 . 2 二 叉 樹(shù) 概 念二 叉 樹(shù) 概 念(ginin)(ginin)和性質(zhì)和性質(zhì) 7.2.1 7.2.1 二叉樹(shù)概念二叉樹(shù)概念(ginin)(ginin)7.2.2 7.2.2 二叉樹(shù)性質(zhì)二叉樹(shù)

24、性質(zhì)(xngzh)(xngzh)7.2.3 7.2.3 二叉樹(shù)與樹(shù)、森林之間的轉(zhuǎn)換二叉樹(shù)與樹(shù)、森林之間的轉(zhuǎn)換第24頁(yè)/共115頁(yè)第二十五頁(yè)，共115頁(yè)。7.2.1 7.2.1 二叉樹(shù)概念二叉樹(shù)概念 二叉樹(shù)也稱為二叉樹(shù)也稱為(chn wi)(chn wi)二次樹(shù)或二分樹(shù)二次樹(shù)或二分樹(shù), ,它是有限它是有限的結(jié)點(diǎn)集合的結(jié)點(diǎn)集合, ,這個(gè)集合或者是空這個(gè)集合或者是空, ,或者由一個(gè)根結(jié)點(diǎn)和兩棵互或者由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的稱為不相交的稱為(chn wi)(chn wi)左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。 二叉樹(shù)的定義是一種遞歸定義。二叉樹(shù)的定義是一種遞歸定義。第25頁(yè)/共1

25、15頁(yè)第二十六頁(yè)，共115頁(yè)。 二叉樹(shù)有五種基本形態(tài)二叉樹(shù)有五種基本形態(tài), ,如下如下(rxi)(rxi)圖所示圖所示, ,任何復(fù)雜的二叉樹(shù)都是這五種基本形態(tài)的復(fù)合。任何復(fù)雜的二叉樹(shù)都是這五種基本形態(tài)的復(fù)合。第26頁(yè)/共115頁(yè)第二十七頁(yè)，共115頁(yè)。 從定義看到,二叉樹(shù)是一種(y zhn)特殊的樹(shù),其表示法也與樹(shù)的表示法一樣,有樹(shù)形表示法、文氏圖表示法、凹入表示法和括號(hào)表示法等。第27頁(yè)/共115頁(yè)第二十八頁(yè)，共115頁(yè)。 在一棵二叉樹(shù)中在一棵二叉樹(shù)中, ,如果所有分支結(jié)點(diǎn)如果所有分支結(jié)點(diǎn)(ji din)(ji din)都有左孩子結(jié)點(diǎn)都有左孩子結(jié)點(diǎn)(ji din)(ji din)和右孩子結(jié)點(diǎn)

26、和右孩子結(jié)點(diǎn)(ji (ji din),din),并且葉結(jié)點(diǎn)并且葉結(jié)點(diǎn)(ji din)(ji din)都集中在二叉樹(shù)的都集中在二叉樹(shù)的最下一層最下一層, ,這樣的二叉樹(shù)稱為滿二叉樹(shù)。下圖所示就這樣的二叉樹(shù)稱為滿二叉樹(shù)。下圖所示就是一棵滿二叉樹(shù)?？梢詫?duì)滿二叉樹(shù)的結(jié)點(diǎn)是一棵滿二叉樹(shù)?？梢詫?duì)滿二叉樹(shù)的結(jié)點(diǎn)(ji (ji din)din)進(jìn)行連續(xù)編號(hào)進(jìn)行連續(xù)編號(hào), ,約定編號(hào)從樹(shù)根為約定編號(hào)從樹(shù)根為1 1開(kāi)始開(kāi)始, ,按照按照層數(shù)從小到大、同一層從左到右的次序進(jìn)行。圖中每層數(shù)從小到大、同一層從左到右的次序進(jìn)行。圖中每個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)(ji din)(ji din)外邊的數(shù)字為對(duì)該結(jié)點(diǎn)外邊的數(shù)字為對(duì)該結(jié)點(diǎn)(j

27、i (ji din)din)的編號(hào)。的編號(hào)。 A B C D E H I J K F G L M N O 1 2 3 4 5 6 7 8 9 10 15 11 12 13 14 滿二叉樹(shù)滿二叉樹(shù) 第28頁(yè)/共115頁(yè)第二十九頁(yè)，共115頁(yè)。 若二叉樹(shù)中最多只有最下面兩層的結(jié)點(diǎn)的度數(shù)可以若二叉樹(shù)中最多只有最下面兩層的結(jié)點(diǎn)的度數(shù)可以小于小于2,2,并且最下面一層的葉結(jié)點(diǎn)并且最下面一層的葉結(jié)點(diǎn) 都依次都依次(yc)(yc)排列排列在該層最左邊的位置上在該層最左邊的位置上, ,則這樣的二叉樹(shù)稱為完全二叉則這樣的二叉樹(shù)稱為完全二叉樹(shù)。如下圖所示為一棵完全二叉樹(shù)。同樣可以對(duì)完全二樹(shù)。如下圖所示為一棵完全二

28、叉樹(shù)。同樣可以對(duì)完全二叉樹(shù)中每個(gè)結(jié)點(diǎn)進(jìn)行連續(xù)編號(hào)叉樹(shù)中每個(gè)結(jié)點(diǎn)進(jìn)行連續(xù)編號(hào), ,編號(hào)的方法同滿二叉樹(shù)編號(hào)的方法同滿二叉樹(shù)相同。圖中每個(gè)結(jié)點(diǎn)外邊的數(shù)字為對(duì)該結(jié)點(diǎn)的編號(hào)。相同。圖中每個(gè)結(jié)點(diǎn)外邊的數(shù)字為對(duì)該結(jié)點(diǎn)的編號(hào)。 A B C D E H I J K F G 1 2 3 4 5 6 7 8 9 10 11 完全二叉樹(shù)完全二叉樹(shù) 第29頁(yè)/共115頁(yè)第三十頁(yè)，共115頁(yè)。7.2.2 7.2.2 二叉樹(shù)性質(zhì)二叉樹(shù)性質(zhì) 性質(zhì)性質(zhì)1 1 非空二叉樹(shù)上葉結(jié)點(diǎn)數(shù)等于雙分支結(jié)點(diǎn)非空二叉樹(shù)上葉結(jié)點(diǎn)數(shù)等于雙分支結(jié)點(diǎn)數(shù)加數(shù)加1 1。 證明：設(shè)二叉樹(shù)上葉結(jié)點(diǎn)數(shù)為證明：設(shè)二叉樹(shù)上葉結(jié)點(diǎn)數(shù)為n0,n0,單分支結(jié)點(diǎn)單分支結(jié)

29、點(diǎn)數(shù)為數(shù)為n1,n1,雙分支結(jié)點(diǎn)數(shù)為雙分支結(jié)點(diǎn)數(shù)為n2,n2,則總結(jié)點(diǎn)數(shù)則總結(jié)點(diǎn)數(shù)=n0+n1+n2=n0+n1+n2。在一棵二叉樹(shù)中在一棵二叉樹(shù)中, ,所有結(jié)點(diǎn)的分支數(shù)所有結(jié)點(diǎn)的分支數(shù)( (即度數(shù)即度數(shù)) )應(yīng)等于應(yīng)等于單分支結(jié)點(diǎn)數(shù)加上雙分支結(jié)點(diǎn)數(shù)的單分支結(jié)點(diǎn)數(shù)加上雙分支結(jié)點(diǎn)數(shù)的2 2倍倍, ,即總的分支數(shù)即總的分支數(shù)=n1+2n2=n1+2n2。 由于二叉樹(shù)中除根結(jié)點(diǎn)以外由于二叉樹(shù)中除根結(jié)點(diǎn)以外, ,每個(gè)結(jié)點(diǎn)都有惟一每個(gè)結(jié)點(diǎn)都有惟一的一個(gè)分支指向的一個(gè)分支指向(zh xin)(zh xin)它它, ,因此二叉樹(shù)中有：總因此二叉樹(shù)中有：總的分支數(shù)的分支數(shù)= =總結(jié)點(diǎn)數(shù)總結(jié)點(diǎn)數(shù)-1-1。 由上

30、述三個(gè)等式可得：由上述三個(gè)等式可得：n1+2n2=n0+n1+n2-1n1+2n2=n0+n1+n2-1即：即：n0=n2+1n0=n2+1第30頁(yè)/共115頁(yè)第三十一頁(yè)，共115頁(yè)。 性質(zhì)性質(zhì)2 非空二叉樹(shù)上第非空二叉樹(shù)上第i層上至多有層上至多有2i-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)(ji din),這里應(yīng)有這里應(yīng)有i1。 由樹(shù)的性質(zhì)由樹(shù)的性質(zhì)2可推出?？赏瞥?。 性質(zhì)性質(zhì)3 高度為高度為h的二叉樹(shù)至多有的二叉樹(shù)至多有2h-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)(ji din)(h1)。 由樹(shù)的性質(zhì)由樹(shù)的性質(zhì)3可推出?？赏瞥?。第31頁(yè)/共115頁(yè)第三十二頁(yè)，共115頁(yè)。 性質(zhì)性質(zhì)4 對(duì)完全二叉樹(shù)中編號(hào)為對(duì)完全二叉樹(shù)中編號(hào)為i的結(jié)點(diǎn)的結(jié)

31、點(diǎn)(1in,n1,n為結(jié)點(diǎn)數(shù)為結(jié)點(diǎn)數(shù))有：有： (1)若若in/2,即即2in,則編號(hào)為則編號(hào)為i的結(jié)點(diǎn)為分支結(jié)點(diǎn)的結(jié)點(diǎn)為分支結(jié)點(diǎn),否則為葉子結(jié)點(diǎn)。否則為葉子結(jié)點(diǎn)。 (2)若若n為奇數(shù)為奇數(shù),則每個(gè)分支結(jié)點(diǎn)都既有左孩子則每個(gè)分支結(jié)點(diǎn)都既有左孩子(hi zi)結(jié)點(diǎn)結(jié)點(diǎn),也有右孩子也有右孩子(hi zi)結(jié)點(diǎn)；若結(jié)點(diǎn)；若n為偶數(shù)為偶數(shù),則編號(hào)最大的則編號(hào)最大的分支結(jié)點(diǎn)分支結(jié)點(diǎn)(編號(hào)為編號(hào)為)只有左孩子只有左孩子(hi zi)結(jié)點(diǎn)結(jié)點(diǎn),沒(méi)有右孩子沒(méi)有右孩子(hi zi)結(jié)點(diǎn)結(jié)點(diǎn),其余分支結(jié)點(diǎn)都有左、右孩子其余分支結(jié)點(diǎn)都有左、右孩子(hi zi)結(jié)點(diǎn)。結(jié)點(diǎn)。第32頁(yè)/共115頁(yè)第三十三頁(yè)，共115頁(yè)。

32、 (3)若編號(hào)為若編號(hào)為i的結(jié)點(diǎn)有左孩子結(jié)點(diǎn)的結(jié)點(diǎn)有左孩子結(jié)點(diǎn),則左孩子結(jié)點(diǎn)的編號(hào)則左孩子結(jié)點(diǎn)的編號(hào)為為2i；若編號(hào)為；若編號(hào)為i的結(jié)點(diǎn)有右孩子結(jié)點(diǎn)的結(jié)點(diǎn)有右孩子結(jié)點(diǎn),則右孩子結(jié)點(diǎn)的編號(hào)則右孩子結(jié)點(diǎn)的編號(hào)為為(2i+1)。 (4)除樹(shù)根結(jié)點(diǎn)外除樹(shù)根結(jié)點(diǎn)外,若一個(gè)若一個(gè)(y )結(jié)點(diǎn)的編號(hào)為結(jié)點(diǎn)的編號(hào)為i,則它的雙則它的雙親結(jié)點(diǎn)的編號(hào)為親結(jié)點(diǎn)的編號(hào)為i/2,也就是說(shuō)也就是說(shuō),當(dāng)當(dāng)i為偶數(shù)時(shí)為偶數(shù)時(shí),其雙親結(jié)點(diǎn)其雙親結(jié)點(diǎn)的編號(hào)為的編號(hào)為i/2,它是雙親結(jié)點(diǎn)的左孩子結(jié)點(diǎn)它是雙親結(jié)點(diǎn)的左孩子結(jié)點(diǎn),當(dāng)當(dāng)i為奇數(shù)時(shí)為奇數(shù)時(shí),其雙其雙親結(jié)點(diǎn)的編號(hào)為親結(jié)點(diǎn)的編號(hào)為(i-1)/2,它是雙親結(jié)點(diǎn)的右孩子結(jié)點(diǎn)。它是雙

33、親結(jié)點(diǎn)的右孩子結(jié)點(diǎn)。第33頁(yè)/共115頁(yè)第三十四頁(yè)，共115頁(yè)。 性質(zhì)性質(zhì)5 具有具有n個(gè)個(gè)(n0)結(jié)點(diǎn)的完全結(jié)點(diǎn)的完全(wnqun)二二叉樹(shù)的高度為叉樹(shù)的高度為log2(n+1)或或log2n+1。 由完全由完全(wnqun)二叉樹(shù)的定義和樹(shù)的性質(zhì)二叉樹(shù)的定義和樹(shù)的性質(zhì)3可推可推出。出。第34頁(yè)/共115頁(yè)第三十五頁(yè)，共115頁(yè)。7.2.3 7.2.3 二叉樹(shù)與樹(shù)、森林二叉樹(shù)與樹(shù)、森林(snln)(snln)之之間的轉(zhuǎn)換間的轉(zhuǎn)換1森林森林(snln)、樹(shù)轉(zhuǎn)換為二叉樹(shù)、樹(shù)轉(zhuǎn)換為二叉樹(shù) (1)在所有相鄰兄弟結(jié)點(diǎn)在所有相鄰兄弟結(jié)點(diǎn)(森林森林(snln)中每棵樹(shù)的根結(jié)中每棵樹(shù)的根結(jié)點(diǎn)可看成是兄弟結(jié)點(diǎn)

34、點(diǎn)可看成是兄弟結(jié)點(diǎn))之間加一水平連線。之間加一水平連線。 (2)對(duì)每個(gè)非葉結(jié)點(diǎn)對(duì)每個(gè)非葉結(jié)點(diǎn)k,除了其最左邊的孩子結(jié)點(diǎn)外除了其最左邊的孩子結(jié)點(diǎn)外,刪去刪去k與其他孩子結(jié)點(diǎn)的連線。與其他孩子結(jié)點(diǎn)的連線。 (3)所有水平線段以左邊結(jié)點(diǎn)為軸心順時(shí)針旋轉(zhuǎn)所有水平線段以左邊結(jié)點(diǎn)為軸心順時(shí)針旋轉(zhuǎn)45度。度。 通過(guò)以上步驟通過(guò)以上步驟,原來(lái)的森林原來(lái)的森林(snln)就轉(zhuǎn)換為一棵二叉就轉(zhuǎn)換為一棵二叉樹(shù)。一般的樹(shù)是森林樹(shù)。一般的樹(shù)是森林(snln)中的特殊情況中的特殊情況,由一般的樹(shù)由一般的樹(shù)轉(zhuǎn)換的二叉樹(shù)的根結(jié)點(diǎn)的右孩子結(jié)點(diǎn)始終為空轉(zhuǎn)換的二叉樹(shù)的根結(jié)點(diǎn)的右孩子結(jié)點(diǎn)始終為空,原因是一原因是一般的樹(shù)的根結(jié)點(diǎn)不存在

35、兄弟結(jié)點(diǎn)和相鄰的樹(shù)。般的樹(shù)的根結(jié)點(diǎn)不存在兄弟結(jié)點(diǎn)和相鄰的樹(shù)。第35頁(yè)/共115頁(yè)第三十六頁(yè)，共115頁(yè)。 A B C D E F G H I A B E F G C D H I (a) (c) A B C D E F G H I (b) 將森林將森林(snln)轉(zhuǎn)換為二叉樹(shù)的過(guò)程轉(zhuǎn)換為二叉樹(shù)的過(guò)程第36頁(yè)/共115頁(yè)第三十七頁(yè)，共115頁(yè)。2. 2. 二叉樹(shù)還原二叉樹(shù)還原(hun yun)(hun yun)為森林、樹(shù)為森林、樹(shù) (1) (1)對(duì)于一棵二叉樹(shù)中任一結(jié)點(diǎn)對(duì)于一棵二叉樹(shù)中任一結(jié)點(diǎn)(ji din)k0,(ji din)k0,沿沿著著k1k1右孩子結(jié)點(diǎn)右孩子結(jié)點(diǎn)(ji din)(ji d

36、in)的右子樹(shù)方向搜索所有右的右子樹(shù)方向搜索所有右孩子結(jié)點(diǎn)孩子結(jié)點(diǎn)(ji din),(ji din),即搜索結(jié)點(diǎn)即搜索結(jié)點(diǎn)(ji din)(ji din)序列序列k2,k3,km,k2,k3,km,其中其中ki+1ki+1為為kiki的右孩子結(jié)點(diǎn)的右孩子結(jié)點(diǎn)(ji (ji din)(1idin)(1im),kmm),km沒(méi)有右孩子結(jié)點(diǎn)沒(méi)有右孩子結(jié)點(diǎn)(ji din)(ji din)。 (2) (2)刪去刪去k1,k2,kmk1,k2,km之間連線。之間連線。 (3) (3)若若k1k1有雙親結(jié)點(diǎn)有雙親結(jié)點(diǎn)(ji din)k,(ji din)k,則連接則連接k k與與ki(2im)ki(2im)。

37、 (4) (4)將圖形規(guī)整化將圖形規(guī)整化, ,使各結(jié)點(diǎn)使各結(jié)點(diǎn)(ji din)(ji din)按層次按層次排列。排列。第37頁(yè)/共115頁(yè)第三十八頁(yè)，共115頁(yè)。 A D H B F C G E A B D C F E H G (a) (c) A B D C F E H G (b) 將一棵二叉樹(shù)還原將一棵二叉樹(shù)還原(hun yun)(hun yun)為樹(shù)的過(guò)程為樹(shù)的過(guò)程第38頁(yè)/共115頁(yè)第三十九頁(yè)，共115頁(yè)。7.3 7.3 二叉樹(shù)存儲(chǔ)二叉樹(shù)存儲(chǔ)(cn (cn ch)ch)結(jié)構(gòu)結(jié)構(gòu) 7.3.1 7.3.1 二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)(jigu) (jigu) 7.3.2 7.3

38、.2 二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)(cn ch)(cn ch)結(jié)構(gòu)結(jié)構(gòu)第39頁(yè)/共115頁(yè)第四十頁(yè)，共115頁(yè)。7.3.1 7.3.1 二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu) 二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)中結(jié)點(diǎn)的存放次序是：二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)中結(jié)點(diǎn)的存放次序是：對(duì)該樹(shù)中每個(gè)結(jié)點(diǎn)進(jìn)行編號(hào)對(duì)該樹(shù)中每個(gè)結(jié)點(diǎn)進(jìn)行編號(hào), ,其編號(hào)從小到大的順序其編號(hào)從小到大的順序就是結(jié)點(diǎn)存放在連續(xù)存儲(chǔ)單元的先后次序。若把二叉就是結(jié)點(diǎn)存放在連續(xù)存儲(chǔ)單元的先后次序。若把二叉樹(shù)存儲(chǔ)到一維數(shù)組中樹(shù)存儲(chǔ)到一維數(shù)組中, ,則該編號(hào)就是下標(biāo)值加則該編號(hào)就是下標(biāo)值加1(1(注注意意,C/C+,C/C+語(yǔ)言中數(shù)組的起始下標(biāo)為語(yǔ)言中數(shù)組的

39、起始下標(biāo)為0)0)。樹(shù)中各結(jié)點(diǎn)的。樹(shù)中各結(jié)點(diǎn)的編號(hào)與等高度的完全二叉樹(shù)中對(duì)應(yīng)位置上結(jié)點(diǎn)的編號(hào)編號(hào)與等高度的完全二叉樹(shù)中對(duì)應(yīng)位置上結(jié)點(diǎn)的編號(hào)相同。相同。 利用利用(lyng)(lyng)二叉樹(shù)的性質(zhì)二叉樹(shù)的性質(zhì)4 4。第40頁(yè)/共115頁(yè)第四十一頁(yè)，共115頁(yè)。 A B C D E H I J K F G 1 2 3 4 5 6 7 8 9 10 11 完全二叉樹(shù)完全二叉樹(shù) A B C D E F G H I J K123456789101112131415順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)(jigu)第41頁(yè)/共115頁(yè)第四十二頁(yè)，共115頁(yè)。7.3.2 7.3.2 二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)(c

40、n ch)(cn ch)結(jié)構(gòu)結(jié)構(gòu) 在二叉樹(shù)的鏈接存儲(chǔ)在二叉樹(shù)的鏈接存儲(chǔ)(cn ch)(cn ch)中中, ,結(jié)點(diǎn)的結(jié)構(gòu)如下結(jié)點(diǎn)的結(jié)構(gòu)如下: : typedef struct node typedef struct node ElemType data;ElemType data; struct node struct node * *lchild,lchild,* *rchild;rchild; BTNode; BTNode; 其中其中,data,data表示值域表示值域, ,用于存儲(chǔ)用于存儲(chǔ)(cn ch)(cn ch)對(duì)應(yīng)的數(shù)對(duì)應(yīng)的數(shù)據(jù)元素?fù)?jù)元素,lchild,lchild和和rchildr

41、child分別表示左指針域和右指針域分別表示左指針域和右指針域, ,用用于分別存儲(chǔ)于分別存儲(chǔ)(cn ch)(cn ch)左孩子結(jié)點(diǎn)和右孩子結(jié)點(diǎn)左孩子結(jié)點(diǎn)和右孩子結(jié)點(diǎn)( (即左、右即左、右子樹(shù)的根結(jié)點(diǎn)子樹(shù)的根結(jié)點(diǎn)) )的存儲(chǔ)的存儲(chǔ)(cn ch)(cn ch)位置。位置。第42頁(yè)/共115頁(yè)第四十三頁(yè)，共115頁(yè)。 A B C E F D G A B C D E F G (a) (b) 二叉樹(shù)及其鏈?zhǔn)酱鎯?chǔ)二叉樹(shù)及其鏈?zhǔn)酱鎯?chǔ)(cn ch)(cn ch)結(jié)構(gòu)結(jié)構(gòu) 第43頁(yè)/共115頁(yè)第四十四頁(yè)，共115頁(yè)。7.4 7.4 二叉樹(shù)的遍歷二叉樹(shù)的遍歷(bin l)(bin l)7.4.1 7.4.1 二叉

42、樹(shù)遍歷二叉樹(shù)遍歷(bin l)(bin l)的概念的概念7.4.2 7.4.2 二叉樹(shù)遍歷二叉樹(shù)遍歷(bin l)(bin l)遞歸遞歸算法算法第44頁(yè)/共115頁(yè)第四十五頁(yè)，共115頁(yè)。7.4.1 7.4.1 二叉樹(shù)遍歷的概念二叉樹(shù)遍歷的概念 二叉樹(shù)的遍歷是指按照一定次序訪問(wèn)樹(shù)中所二叉樹(shù)的遍歷是指按照一定次序訪問(wèn)樹(shù)中所有結(jié)點(diǎn)有結(jié)點(diǎn)(ji din),(ji din),并且每個(gè)結(jié)點(diǎn)并且每個(gè)結(jié)點(diǎn)(ji din)(ji din)僅被訪問(wèn)僅被訪問(wèn)一次的過(guò)程。它是最基本的運(yùn)算一次的過(guò)程。它是最基本的運(yùn)算, ,是二叉樹(shù)中所有其他是二叉樹(shù)中所有其他運(yùn)算的基礎(chǔ)。運(yùn)算的基礎(chǔ)。第45頁(yè)/共115頁(yè)第四十六頁(yè)，共1

43、15頁(yè)。 1. 1. 先序遍歷先序遍歷先序遍歷二叉樹(shù)的過(guò)程是：先序遍歷二叉樹(shù)的過(guò)程是：(1)(1)訪問(wèn)訪問(wèn)(fngwn)(fngwn)根結(jié)點(diǎn)；根結(jié)點(diǎn)；(2)(2)先序遍歷左子樹(shù)；先序遍歷左子樹(shù)；(3)(3)先序遍歷右子樹(shù)。先序遍歷右子樹(shù)。2. 2. 中序遍歷中序遍歷中序遍歷二叉樹(shù)的過(guò)程是：中序遍歷二叉樹(shù)的過(guò)程是：(1)(1)中序遍歷左子樹(shù)；中序遍歷左子樹(shù)；(2)(2)訪問(wèn)訪問(wèn)(fngwn)(fngwn)根結(jié)點(diǎn)；根結(jié)點(diǎn)；(3)(3)中序遍歷右子樹(shù)。中序遍歷右子樹(shù)。第46頁(yè)/共115頁(yè)第四十七頁(yè)，共115頁(yè)。 3. 3. 后序遍歷后序遍歷后序遍歷二叉樹(shù)的過(guò)程后序遍歷二叉樹(shù)的過(guò)程(guchng)(g

44、uchng)是：是：(1)(1)后序遍歷左子樹(shù)；后序遍歷左子樹(shù)；(2)(2)后序遍歷右子樹(shù)；后序遍歷右子樹(shù)；(3)(3)訪問(wèn)根結(jié)點(diǎn)。訪問(wèn)根結(jié)點(diǎn)。第47頁(yè)/共115頁(yè)第四十八頁(yè)，共115頁(yè)。7.4.2 7.4.2 二叉樹(shù)遍歷遞歸算法二叉樹(shù)遍歷遞歸算法 由二叉樹(shù)的三種遍歷過(guò)程直接得到如下三種遞歸算由二叉樹(shù)的三種遍歷過(guò)程直接得到如下三種遞歸算法如下：法如下： void PreOrder(BTNode void PreOrder(BTNode * *b) b) / /* *先序遍歷的遞歸先序遍歷的遞歸算法算法* */ / if (b!=NULL) if (b!=NULL) printf(%c ,b-d

45、ata); / printf(%c ,b-data); /* *訪問(wèn)訪問(wèn)(fngwn)(fngwn)根結(jié)點(diǎn)根結(jié)點(diǎn)* */ / PreOrder(b-lchild); PreOrder(b-lchild); PreOrder(b-rchild); PreOrder(b-rchild); 第48頁(yè)/共115頁(yè)第四十九頁(yè)，共115頁(yè)。 void InOrder(BTNode *b) /*中序遍歷的遞歸算法中序遍歷的遞歸算法(sun f)*/ if (b!=NULL) InOrder(b-lchild); printf(%c ,b-data); /*訪問(wèn)根結(jié)點(diǎn)訪問(wèn)根結(jié)點(diǎn)*/ InOrder(b-rch

46、ild); 第49頁(yè)/共115頁(yè)第五十頁(yè)，共115頁(yè)。 void PostOrder(BTNode *b) /*后序后序(hu x)遍歷遞歸遍歷遞歸算法算法*/ if (b!=NULL) PostOrder(b-lchild); PostOrder(b-rchild); printf(%c ,b-data); /*訪問(wèn)根結(jié)點(diǎn)訪問(wèn)根結(jié)點(diǎn)*/ 第50頁(yè)/共115頁(yè)第五十一頁(yè)，共115頁(yè)。 例例7.2 假設(shè)二叉樹(shù)采用假設(shè)二叉樹(shù)采用(ciyng)二叉鏈存儲(chǔ)結(jié)構(gòu)存儲(chǔ)二叉鏈存儲(chǔ)結(jié)構(gòu)存儲(chǔ),試試設(shè)計(jì)一個(gè)算法設(shè)計(jì)一個(gè)算法,輸出一棵給定二叉樹(shù)的所有葉子結(jié)點(diǎn)。輸出一棵給定二叉樹(shù)的所有葉子結(jié)點(diǎn)。 解：輸出一棵二叉樹(shù)的

47、所有葉子結(jié)點(diǎn)的遞歸模型解：輸出一棵二叉樹(shù)的所有葉子結(jié)點(diǎn)的遞歸模型f()如下：如下： f(b)：不做任何事件：不做任何事件 若若b=NULL f(b)：輸出：輸出*b結(jié)點(diǎn)的結(jié)點(diǎn)的data域域 若若*b為葉子結(jié)點(diǎn)為葉子結(jié)點(diǎn) f(b)：f(b-lchild);f(b-rchild) 其他情況其他情況第51頁(yè)/共115頁(yè)第五十二頁(yè)，共115頁(yè)。 void DispLeaf(BTNode *b) if (b!=NULL) if (b-lchild=NULL & b-rchild=NULL) printf(%c ,b-data); else DispLeaf(b-lchild); DispLeaf

48、(b-rchild); 第52頁(yè)/共115頁(yè)第五十三頁(yè)，共115頁(yè)。7.5 7.5 二叉樹(shù)的基本二叉樹(shù)的基本(jbn)(jbn)運(yùn)算及其運(yùn)算及其實(shí)現(xiàn)實(shí)現(xiàn)7.5.1 7.5.1 二叉樹(shù)的基本二叉樹(shù)的基本(jbn)(jbn)運(yùn)算運(yùn)算概述概述7.5.2 7.5.2 二叉樹(shù)的基本運(yùn)算算法二叉樹(shù)的基本運(yùn)算算法(sun (sun f)f)實(shí)現(xiàn)實(shí)現(xiàn)第53頁(yè)/共115頁(yè)第五十四頁(yè)，共115頁(yè)。7.5.1 7.5.1 二叉樹(shù)的基本運(yùn)算概述二叉樹(shù)的基本運(yùn)算概述 歸納起來(lái)歸納起來(lái), ,二叉樹(shù)有以下基本運(yùn)算：二叉樹(shù)有以下基本運(yùn)算： (1) (1)創(chuàng)建二叉樹(shù)創(chuàng)建二叉樹(shù)CreateBTNode(CreateBTNode(

49、* *b,b,* *str)str)：根據(jù)：根據(jù)(gnj)(gnj)二叉樹(shù)括號(hào)表示法的字符串二叉樹(shù)括號(hào)表示法的字符串* *strstr生成對(duì)應(yīng)的鏈生成對(duì)應(yīng)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。式存儲(chǔ)結(jié)構(gòu)。 (2) (2)查找結(jié)點(diǎn)查找結(jié)點(diǎn)FindNode(FindNode(* *b,x)b,x)：在二叉樹(shù)：在二叉樹(shù)b b中尋中尋找找datadata域值為域值為x x的結(jié)點(diǎn)的結(jié)點(diǎn), ,并返回指向該結(jié)點(diǎn)的指針。并返回指向該結(jié)點(diǎn)的指針。 ( 3 ) ( 3 ) 找 孩 子 結(jié) 點(diǎn)找 孩 子 結(jié) 點(diǎn) L c h i l d N o d e ( p )L c h i l d N o d e ( p ) 和和RchildNode

50、(p)RchildNode(p)：分別求二叉樹(shù)中結(jié)點(diǎn)：分別求二叉樹(shù)中結(jié)點(diǎn)* *p p的左孩子結(jié)點(diǎn)的左孩子結(jié)點(diǎn)和右孩子結(jié)點(diǎn)。和右孩子結(jié)點(diǎn)。第54頁(yè)/共115頁(yè)第五十五頁(yè)，共115頁(yè)。 (4)求高度求高度BTNodeDepth(*b)：求二叉樹(shù)：求二叉樹(shù)b的的高度。若二叉樹(shù)為空高度。若二叉樹(shù)為空,則其高度為則其高度為0；否則；否則,其高度其高度等于左子樹(shù)與右子樹(shù)中的最大高度加等于左子樹(shù)與右子樹(shù)中的最大高度加l。 (5)輸出輸出(shch)二叉樹(shù)二叉樹(shù)DispBTNode(*b)：以括號(hào)表示法輸出以括號(hào)表示法輸出(shch)一棵二叉樹(shù)。一棵二叉樹(shù)。第55頁(yè)/共115頁(yè)第五十六頁(yè)，共115頁(yè)。7.5.

51、2 7.5.2 二叉樹(shù)的基本運(yùn)算算法實(shí)現(xiàn)二叉樹(shù)的基本運(yùn)算算法實(shí)現(xiàn) (1) (1)創(chuàng)建二叉樹(shù)創(chuàng)建二叉樹(shù)CreateBTNode(CreateBTNode(* *b,b,* *str)str) 用用chch掃描采用括號(hào)表示法表示二叉樹(shù)的字符串。掃描采用括號(hào)表示法表示二叉樹(shù)的字符串。分以下幾種情況：分以下幾種情況： 若若ch=(ch=(：則將前面剛創(chuàng)建的結(jié)點(diǎn)作為雙親：則將前面剛創(chuàng)建的結(jié)點(diǎn)作為雙親結(jié)點(diǎn)進(jìn)棧結(jié)點(diǎn)進(jìn)棧, ,并置并置(bn zh)k=1,(bn zh)k=1,表示其后創(chuàng)建的結(jié)點(diǎn)將作表示其后創(chuàng)建的結(jié)點(diǎn)將作為這個(gè)結(jié)點(diǎn)的左孩子結(jié)點(diǎn)；為這個(gè)結(jié)點(diǎn)的左孩子結(jié)點(diǎn)； 若若ch=)ch=)：表示棧中結(jié)點(diǎn)的左右

52、孩子結(jié)點(diǎn)處：表示棧中結(jié)點(diǎn)的左右孩子結(jié)點(diǎn)處理完畢理完畢, ,退棧；退棧； 若若ch=,ch=,：表示其后創(chuàng)建的結(jié)點(diǎn)為右孩子結(jié)：表示其后創(chuàng)建的結(jié)點(diǎn)為右孩子結(jié)點(diǎn)；點(diǎn)；第56頁(yè)/共115頁(yè)第五十七頁(yè)，共115頁(yè)。 其他情況其他情況, ,表示要?jiǎng)?chuàng)建一個(gè)結(jié)點(diǎn)表示要?jiǎng)?chuàng)建一個(gè)結(jié)點(diǎn), ,并根并根據(jù)據(jù)k k值建立它與棧中結(jié)點(diǎn)之間的聯(lián)系值建立它與棧中結(jié)點(diǎn)之間的聯(lián)系, ,當(dāng)當(dāng)k=1k=1時(shí)時(shí), ,表示這個(gè)結(jié)點(diǎn)作為表示這個(gè)結(jié)點(diǎn)作為(zuwi)(zuwi)棧中結(jié)點(diǎn)棧中結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的左孩子結(jié)點(diǎn), ,當(dāng)當(dāng)k=2k=2時(shí)時(shí), ,表示這個(gè)結(jié)點(diǎn)作為表示這個(gè)結(jié)點(diǎn)作為(zuwi)(zuwi)棧中結(jié)點(diǎn)的右孩子結(jié)點(diǎn)。如此循棧中結(jié)點(diǎn)的右

53、孩子結(jié)點(diǎn)。如此循環(huán)直到環(huán)直到strstr處理完畢。算法中使用一個(gè)棧處理完畢。算法中使用一個(gè)棧StSt保存雙親結(jié)點(diǎn)保存雙親結(jié)點(diǎn),top,top為其棧指針為其棧指針,k,k指定其后處指定其后處理的結(jié)點(diǎn)是雙親結(jié)點(diǎn)理的結(jié)點(diǎn)是雙親結(jié)點(diǎn)( (保存在棧中保存在棧中) )的左孩子的左孩子結(jié)點(diǎn)結(jié)點(diǎn)(k=1)(k=1)還是右孩子結(jié)點(diǎn)還是右孩子結(jié)點(diǎn)(k=2)(k=2)。第57頁(yè)/共115頁(yè)第五十八頁(yè)，共115頁(yè)。 void CreateBTNode(BTNode * &b,char *str) BTNode *StMaxSize,*p=NULL; int top=-1,k,j=0; char ch; b=N

54、ULL; /*建立的二叉樹(shù)初始時(shí)為空建立的二叉樹(shù)初始時(shí)為空*/ ch=strj; while (ch!=0) /*str未掃描完時(shí)循環(huán)未掃描完時(shí)循環(huán)*/ switch(ch) case (:top+;Sttop=p;k=1; break; /*為左孩子為左孩子(hi zi)結(jié)點(diǎn)結(jié)點(diǎn)*/ case ):top-;break; case ,:k=2; break; /*為孩子為孩子(hi zi)結(jié)點(diǎn)右結(jié)點(diǎn)結(jié)點(diǎn)右結(jié)點(diǎn)*/第58頁(yè)/共115頁(yè)第五十九頁(yè)，共115頁(yè)。 d e f a u l t : p = ( B T N o d e *)malloc(sizeof(BTNode); p-data=ch

55、;p-lchild=p-rchild=NULL; if (b=NULL) /*p為二叉樹(shù)的根結(jié)點(diǎn)為二叉樹(shù)的根結(jié)點(diǎn)(ji din)*/ b=p; else /*已建立二叉樹(shù)根結(jié)點(diǎn)已建立二叉樹(shù)根結(jié)點(diǎn)(ji din)*/ switch(k) c a s e 1 : S t t o p -lchild=p;break; c a s e 2 : S t t o p -rchild=p;break; j+;ch=strj; 第59頁(yè)/共115頁(yè)第六十頁(yè)，共115頁(yè)。 例如例如, ,對(duì)于括號(hào)對(duì)于括號(hào)(kuho)(kuho)表示串表示串A(B(D(,G),C(E,F),A(B(D(,G),C(E,F),建立二

56、叉樹(shù)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的過(guò)程如下表所示。建立二叉樹(shù)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的過(guò)程如下表所示。ch算法執(zhí)行的操作算法執(zhí)行的操作St中元素中元素A建立建立A結(jié)點(diǎn)結(jié)點(diǎn),b指向該結(jié)點(diǎn)指向該結(jié)點(diǎn)空空(A結(jié)點(diǎn)進(jìn)棧結(jié)點(diǎn)進(jìn)棧,k=1AB建立建立B結(jié)點(diǎn)結(jié)點(diǎn),因因k=1,將其作為將其作為A結(jié)點(diǎn)的左結(jié)點(diǎn)的左孩子結(jié)點(diǎn)孩子結(jié)點(diǎn)A(B結(jié)點(diǎn)進(jìn)棧結(jié)點(diǎn)進(jìn)棧,k=1ABD建立建立D結(jié)點(diǎn)結(jié)點(diǎn),因因k=1,將其作為將其作為B結(jié)點(diǎn)的左結(jié)點(diǎn)的左孩子結(jié)點(diǎn)孩子結(jié)點(diǎn)AB第60頁(yè)/共115頁(yè)第六十一頁(yè)，共115頁(yè)。ch算法執(zhí)行的操作算法執(zhí)行的操作St中元素中元素(D結(jié)點(diǎn)進(jìn)棧結(jié)點(diǎn)進(jìn)棧,k=1ABD,k=2ABDG建立建立E結(jié)點(diǎn)結(jié)點(diǎn),因因k=2,將其作為將其作為D結(jié)

57、結(jié)點(diǎn)的右孩子結(jié)點(diǎn)點(diǎn)的右孩子結(jié)點(diǎn)ABD)退棧一次退棧一次AB)退棧一次退棧一次A,k=2AC建立建立C結(jié)點(diǎn)結(jié)點(diǎn),因因k=2,將其作為將其作為A結(jié)結(jié)點(diǎn)的右孩子結(jié)點(diǎn)點(diǎn)的右孩子結(jié)點(diǎn)A(C結(jié)點(diǎn)進(jìn)棧結(jié)點(diǎn)進(jìn)棧,k=1ACE建立建立E結(jié)點(diǎn)結(jié)點(diǎn),因因k=1,將其作為將其作為C結(jié)結(jié)點(diǎn)的左孩子結(jié)點(diǎn)點(diǎn)的左孩子結(jié)點(diǎn)AC,k=2AC第61頁(yè)/共115頁(yè)第六十二頁(yè)，共115頁(yè)。ch算法執(zhí)行的操作算法執(zhí)行的操作St中元素中元素F建立建立F結(jié)點(diǎn)結(jié)點(diǎn),因因k=2,將其作為將其作為C結(jié)點(diǎn)結(jié)點(diǎn)的右孩子結(jié)點(diǎn)的右孩子結(jié)點(diǎn)AC)退棧一次退棧一次A)退棧一次退棧一次空空ch掃描完畢掃描完畢算法結(jié)束算法結(jié)束 A B C D E F G 生成生

58、成(shn chn)的二叉樹(shù)的二叉樹(shù)第62頁(yè)/共115頁(yè)第六十三頁(yè)，共115頁(yè)。 (2)查找結(jié)點(diǎn)查找結(jié)點(diǎn)FindNode(*b,x) 采用先序遍歷遞歸算法查找值為采用先序遍歷遞歸算法查找值為x的結(jié)點(diǎn)。找到后返回的結(jié)點(diǎn)。找到后返回(fnhu)其指針其指針,否則返回否則返回(fnhu)NULL。算法如下：。算法如下： BTNode *FindNode(BTNode *b,ElemType x) BTNode *p; if (b=NULL) return NULL; else if (b-data=x) return b; else p=FindNode(b-lchild,x); if (p!=NU

59、LL) return p; else return FindNode(b-rchild,x); 第63頁(yè)/共115頁(yè)第六十四頁(yè)，共115頁(yè)。 (3)找孩子結(jié)點(diǎn)找孩子結(jié)點(diǎn)LchildNode(p)和和RchildNode(p) 直接直接(zhji)返回返回*p結(jié)點(diǎn)的左孩子結(jié)點(diǎn)或右孩子結(jié)點(diǎn)的指結(jié)點(diǎn)的左孩子結(jié)點(diǎn)或右孩子結(jié)點(diǎn)的指針。算法如下：針。算法如下： BTNode *LchildNode(BTNode *p) return p-lchild; BTNode *RchildNode(BTNode *p) return p-rchild; 第64頁(yè)/共115頁(yè)第六十五頁(yè)，共115頁(yè)。(4)求高度求高

60、度BTNodeDepth(*b)求二叉樹(shù)的高度的遞歸模型求二叉樹(shù)的高度的遞歸模型(mxng)f()如下：如下： f(NULL)=0 f(b)=MAXf(b-lchild),f(b-rchild)+1 其他情況其他情況對(duì)應(yīng)的算法如下：對(duì)應(yīng)的算法如下：第65頁(yè)/共115頁(yè)第六十六頁(yè)，共115頁(yè)。int BTNodeDepth(BTNode *b) int lchilddep,rchilddep; if (b=NULL) return(0); /*空樹(shù)的高度空樹(shù)的高度(god)為為0*/ else lchilddep=BTNodeDepth(b-lchild);/*求左子樹(shù)的高度求左子樹(shù)的高度(god)為為lchilddep*/ rchild