第7章樹(shù)形結(jié)構(gòu)

1、第第7章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)7.1 樹(shù)的基本概念樹(shù)的基本概念 7.2 二叉樹(shù)概念和性質(zhì)二叉樹(shù)概念和性質(zhì)7.3 二叉樹(shù)存儲(chǔ)結(jié)構(gòu)二叉樹(shù)存儲(chǔ)結(jié)構(gòu)7.4 二叉樹(shù)的遍歷二叉樹(shù)的遍歷7.5 二叉樹(shù)的基本運(yùn)算及其實(shí)現(xiàn)二叉樹(shù)的基本運(yùn)算及其實(shí)現(xiàn)7.6 二叉樹(shù)的構(gòu)造二叉樹(shù)的構(gòu)造7.8 哈夫曼樹(shù)哈夫曼樹(shù) 7.7 線索二叉樹(shù)線索二叉樹(shù)本章小結(jié)本章小結(jié)7.1.1 樹(shù)的定義樹(shù)的定義 形式化定義：形式化定義： 樹(shù)：樹(shù)：T=D,R。D是包含是包含n個(gè)節(jié)點(diǎn)的有窮集合（個(gè)節(jié)點(diǎn)的有窮集合（n0）。）。當(dāng)當(dāng)n=0時(shí)為空樹(shù)，否則關(guān)系時(shí)為空樹(shù)，否則關(guān)系R滿足以下條件滿足以下條件: l 有且僅有一個(gè)節(jié)點(diǎn)有且僅有一個(gè)節(jié)點(diǎn)d0D，它對(duì)于關(guān)

2、系，它對(duì)于關(guān)系R來(lái)說(shuō)沒(méi)來(lái)說(shuō)沒(méi)有前驅(qū)節(jié)點(diǎn)，節(jié)點(diǎn)有前驅(qū)節(jié)點(diǎn)，節(jié)點(diǎn)d0稱作樹(shù)的稱作樹(shù)的根節(jié)點(diǎn)根節(jié)點(diǎn)。l 除節(jié)點(diǎn)除節(jié)點(diǎn)d0外，外，D中的每個(gè)節(jié)點(diǎn)對(duì)于關(guān)系中的每個(gè)節(jié)點(diǎn)對(duì)于關(guān)系R來(lái)說(shuō)都來(lái)說(shuō)都有且有且僅有一個(gè)前驅(qū)節(jié)點(diǎn)僅有一個(gè)前驅(qū)節(jié)點(diǎn)。l D中每個(gè)節(jié)點(diǎn)對(duì)于關(guān)系中每個(gè)節(jié)點(diǎn)對(duì)于關(guān)系R來(lái)說(shuō)可以有來(lái)說(shuō)可以有零個(gè)或多個(gè)零個(gè)或多個(gè)后繼節(jié)點(diǎn)后繼節(jié)點(diǎn)。7.1 樹(shù)的基本概念樹(shù)的基本概念 遞歸定義：遞歸定義： 樹(shù)樹(shù)是由是由n（n0）個(gè)節(jié)點(diǎn)組成的有限集合（記為）個(gè)節(jié)點(diǎn)組成的有限集合（記為T）。其中：）。其中： l 如果如果n=0，它是一棵空樹(shù)，這是樹(shù)的特例；，它是一棵空樹(shù)，這是樹(shù)的特例；l 如果如果n0，這，這n個(gè)節(jié)點(diǎn)中存在（有僅

3、存在）一個(gè)節(jié)點(diǎn)個(gè)節(jié)點(diǎn)中存在（有僅存在）一個(gè)節(jié)點(diǎn)作為樹(shù)的根節(jié)點(diǎn)，簡(jiǎn)稱為根節(jié)點(diǎn)（作為樹(shù)的根節(jié)點(diǎn)，簡(jiǎn)稱為根節(jié)點(diǎn)（root），其余節(jié)點(diǎn)），其余節(jié)點(diǎn)可分為可分為m （m0）個(gè)互不相交的有限集）個(gè)互不相交的有限集T1,T2,Tm,其其中每一棵子集本身又是一棵符合本定義的中每一棵子集本身又是一棵符合本定義的樹(shù)樹(shù)，稱為，稱為根根root的子樹(shù)。的子樹(shù)。rootT1T2Tm7.1.2 樹(shù)的表示樹(shù)的表示 （1）樹(shù)形表示法。）樹(shù)形表示法。這是樹(shù)的最基本的表示，使用一棵倒這是樹(shù)的最基本的表示，使用一棵倒置的樹(shù)表示樹(shù)結(jié)構(gòu)，非常直觀和形象。下圖就是采用這種表置的樹(shù)表示樹(shù)結(jié)構(gòu)，非常直觀和形象。下圖就是采用這種表示法。示法。

4、ABCDEFGJHIKLM邏輯結(jié)構(gòu)表示邏輯結(jié)構(gòu)表示1 （2）文氏圖表示法。）文氏圖表示法。使用集合以及集合的包含關(guān)系描述樹(shù)結(jié)使用集合以及集合的包含關(guān)系描述樹(shù)結(jié)構(gòu)。下圖就是樹(shù)的文氏圖表示法。構(gòu)。下圖就是樹(shù)的文氏圖表示法。ABCDEFGJHIKLM邏輯結(jié)構(gòu)表示邏輯結(jié)構(gòu)表示2AEFBCGJHDKLMI （3）凹入表示法。）凹入表示法。使用線段的伸縮描述樹(shù)結(jié)構(gòu)。下使用線段的伸縮描述樹(shù)結(jié)構(gòu)。下圖是樹(shù)的凹入表示法。圖是樹(shù)的凹入表示法。邏輯結(jié)構(gòu)表示邏輯結(jié)構(gòu)表示3ABCDEFGJHIKLM（4）括號(hào)表示法。）括號(hào)表示法。將樹(shù)的根節(jié)點(diǎn)寫在括號(hào)的左邊，除將樹(shù)的根節(jié)點(diǎn)寫在括號(hào)的左邊，除根節(jié)點(diǎn)之外的其余節(jié)點(diǎn)寫在括號(hào)中

5、并用逗號(hào)間隔來(lái)描述根節(jié)點(diǎn)之外的其余節(jié)點(diǎn)寫在括號(hào)中并用逗號(hào)間隔來(lái)描述樹(shù)結(jié)構(gòu)。下圖是樹(shù)的括號(hào)表示法。樹(shù)結(jié)構(gòu)。下圖是樹(shù)的括號(hào)表示法。 括括號(hào)號(hào)表表示示法法 A(B(E,F),C(G(J),D(H,I(K,L,M) ABCDEFGJHIKLM思考題：思考題：樹(shù)的邏輯結(jié)構(gòu)定義？適合表示什么類型的數(shù)據(jù)？樹(shù)的邏輯結(jié)構(gòu)定義？適合表示什么類型的數(shù)據(jù)？7.1.3 樹(shù)的基本術(shù)語(yǔ)樹(shù)的基本術(shù)語(yǔ) 1. 節(jié)點(diǎn)的度與樹(shù)的度：節(jié)點(diǎn)的度與樹(shù)的度：樹(shù)中某樹(shù)中某個(gè)節(jié)點(diǎn)的子樹(shù)的個(gè)數(shù)稱為該節(jié)點(diǎn)的個(gè)節(jié)點(diǎn)的子樹(shù)的個(gè)數(shù)稱為該節(jié)點(diǎn)的度。樹(shù)中各節(jié)點(diǎn)的度的最大值稱為度。樹(shù)中各節(jié)點(diǎn)的度的最大值稱為樹(shù)的度，通常將度為樹(shù)的度，通常將度為m的樹(shù)稱為的樹(shù)稱為

6、m次樹(shù)次樹(shù)。 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)中，每個(gè)節(jié)點(diǎn)的分支數(shù)就是該節(jié)點(diǎn)的度。如對(duì)于度為支節(jié)點(diǎn)中，每個(gè)節(jié)點(diǎn)的分支數(shù)就是該節(jié)點(diǎn)的度。如對(duì)于度為1的節(jié)點(diǎn)的節(jié)點(diǎn),其分支數(shù)為其分支數(shù)為1，被稱為單分支節(jié)點(diǎn)；對(duì)于度為，被稱為單分支節(jié)點(diǎn)；對(duì)于度為2的節(jié)的節(jié)點(diǎn)，其分支數(shù)為點(diǎn)，其分支數(shù)為2，被稱為雙分支節(jié)點(diǎn)，其余類推。，被稱為雙分支節(jié)點(diǎn)，其余類推。ABCDEFGJHIKLM度為度為3度為度為2 3. 路徑與路徑長(zhǎng)度：路徑與路徑長(zhǎng)度

7、：對(duì)于任意對(duì)于任意兩個(gè)節(jié)點(diǎn)兩個(gè)節(jié)點(diǎn)di和和dj，若樹(shù)中存在一個(gè)節(jié)，若樹(shù)中存在一個(gè)節(jié)點(diǎn)序列點(diǎn)序列di,di1,di2,din,dj，使得序列中，使得序列中除除di外的任一節(jié)點(diǎn)都是其在序列中的外的任一節(jié)點(diǎn)都是其在序列中的前一個(gè)節(jié)點(diǎn)的后繼，則稱該節(jié)點(diǎn)序前一個(gè)節(jié)點(diǎn)的后繼，則稱該節(jié)點(diǎn)序列為由列為由di到到dj的一條路徑，用路徑所的一條路徑，用路徑所通過(guò)的節(jié)點(diǎn)序列通過(guò)的節(jié)點(diǎn)序列(di,di1,di2,dj)表示表示這條路徑這條路徑。 路徑長(zhǎng)度路徑長(zhǎng)度等于路徑所通過(guò)的節(jié)點(diǎn)等于路徑所通過(guò)的節(jié)點(diǎn)數(shù)目減數(shù)目減1（即路徑上分支數(shù)目）。（即路徑上分支數(shù)目）。ABCDEFGJHIKLMA到到K的路徑為的路徑為A,D,I

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

9、點(diǎn)的路徑上經(jīng)過(guò)的所有節(jié)點(diǎn)被稱作該節(jié)點(diǎn)的過(guò)的所有節(jié)點(diǎn)被稱作該節(jié)點(diǎn)的祖先節(jié)祖先節(jié)點(diǎn)點(diǎn)。ABCDEFGJHIKLM 5. 節(jié)點(diǎn)的層次和樹(shù)的高度：節(jié)點(diǎn)的層次和樹(shù)的高度：樹(shù)樹(shù)中的每個(gè)節(jié)點(diǎn)都處在一定的層次上。中的每個(gè)節(jié)點(diǎn)都處在一定的層次上。節(jié)點(diǎn)的層次從樹(shù)根開(kāi)始定義，根節(jié)節(jié)點(diǎn)的層次從樹(shù)根開(kāi)始定義，根節(jié)點(diǎn)為第點(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ù)中。樹(shù)中節(jié)點(diǎn)的最大層次稱為樹(shù)的節(jié)點(diǎn)的最大層次稱為樹(shù)的高度高度（或（或樹(shù)的樹(shù)的深度深度）。）。 6. 有序樹(shù)和無(wú)序樹(shù)：有序樹(shù)和無(wú)序樹(shù)：若樹(shù)中各若

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

11、則森林就變成了樹(shù)。就變成了樹(shù)。7.1.4 樹(shù)的性質(zhì)樹(shù)的性質(zhì)性質(zhì)性質(zhì)1 樹(shù)中的節(jié)點(diǎn)數(shù)等于所有節(jié)點(diǎn)樹(shù)中的節(jié)點(diǎn)數(shù)等于所有節(jié)點(diǎn)的度數(shù)加的度數(shù)加1。 證明：證明：根據(jù)樹(shù)的定義，在一棵樹(shù)中，根據(jù)樹(shù)的定義，在一棵樹(shù)中，除樹(shù)根節(jié)點(diǎn)外，每個(gè)節(jié)點(diǎn)有且僅有一除樹(shù)根節(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è)分支一一對(duì)應(yīng)，所以除樹(shù)根之外的節(jié)點(diǎn)數(shù)等于所有節(jié)點(diǎn)的分樹(shù)根之外的節(jié)點(diǎn)數(shù)等于所有節(jié)點(diǎn)的分支數(shù)（度數(shù)），從而可得樹(shù)中的節(jié)點(diǎn)支數(shù)（度數(shù)），從而可得樹(shù)中的節(jié)點(diǎn)數(shù)等于所有節(jié)點(diǎn)的度數(shù)加數(shù)等于所有節(jié)點(diǎn)的度數(shù)加1。度之和分支數(shù)度之和分支數(shù)分支

12、數(shù)分支數(shù)=n-1所以，所以，n=度之和度之和+1ABCDEFGJHIKLM求解樹(shù)的節(jié)點(diǎn)個(gè)數(shù)問(wèn)題求解樹(shù)的節(jié)點(diǎn)個(gè)數(shù)問(wèn)題：對(duì)于度為：對(duì)于度為m的樹(shù)，在的樹(shù)，在n、n0、n1、n2、nm中只有兩個(gè)參數(shù)未知時(shí)，一般可求出這兩個(gè)值。中只有兩個(gè)參數(shù)未知時(shí)，一般可求出這兩個(gè)值。例如求例如求n和和n0的求解過(guò)程如下：的求解過(guò)程如下：n=n0+n1+nm度之和度之和=n1度之和度之和=n1+2n2+mnm所以有：所以有：nn1+2n2+mnm+1=n0+n1+nm這樣：這樣：n0=n2+(m1)nm+1求解方法歸納求解方法歸納 例：一棵度為例：一棵度為4的樹(shù)的樹(shù)T中，若有中，若有20個(gè)度為個(gè)度為4的節(jié)點(diǎn)，的節(jié)點(diǎn)，

13、10個(gè)個(gè)度為度為3的節(jié)點(diǎn)，的節(jié)點(diǎn)，1個(gè)度為個(gè)度為2的節(jié)點(diǎn)，的節(jié)點(diǎn)，10個(gè)度為個(gè)度為1的節(jié)點(diǎn)，則樹(shù)的節(jié)點(diǎn)，則樹(shù)T的葉子節(jié)點(diǎn)個(gè)數(shù)是的葉子節(jié)點(diǎn)個(gè)數(shù)是 。 A.41B.82 C.113D.122注：本題為注：本題為2010年全國(guó)考研題年全國(guó)考研題 性質(zhì)性質(zhì)2 度為度為m的樹(shù)中第的樹(shù)中第i層上至多有層上至多有mi-1個(gè)節(jié)點(diǎn)，這里應(yīng)有個(gè)節(jié)點(diǎn)，這里應(yīng)有i1。 證明（采用數(shù)學(xué)歸納法）證明（采用數(shù)學(xué)歸納法） 對(duì)于第一層對(duì)于第一層,因?yàn)闃?shù)中的第一層上只有一個(gè)節(jié)點(diǎn)，即整個(gè)樹(shù)的因?yàn)闃?shù)中的第一層上只有一個(gè)節(jié)點(diǎn)，即整個(gè)樹(shù)的根節(jié)點(diǎn)根節(jié)點(diǎn),而由而由i=1代入代入mi-1，得，得mi-1=m1-1=1，也同樣得到只有一個(gè)，也同

14、樣得到只有一個(gè)節(jié)點(diǎn)，顯然結(jié)論成立。節(jié)點(diǎn)，顯然結(jié)論成立。 假設(shè)對(duì)于第假設(shè)對(duì)于第(i-1)層（層（i1）命題成立，即度為）命題成立，即度為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è)孩個(gè)孩子節(jié)點(diǎn)，所以第子節(jié)點(diǎn)，所以第i層上的節(jié)點(diǎn)數(shù)至多為第層上的節(jié)點(diǎn)數(shù)至多為第(i-1)層上節(jié)點(diǎn)數(shù)的層上節(jié)點(diǎn)數(shù)的m倍，倍，即至多為即至多為mi-2m=mi-1個(gè)，這與命題相同，故命題成立。個(gè)，這與命題相同，故命題成立。 性質(zhì)性質(zhì)3 高度為高度為h的的m次樹(shù)至多有次樹(shù)至多有 個(gè)節(jié)點(diǎn)。個(gè)節(jié)點(diǎn)。 證明：證

15、明：由樹(shù)的性質(zhì)由樹(shù)的性質(zhì)2可知可知,第第i層上最多節(jié)點(diǎn)數(shù)為層上最多節(jié)點(diǎn)數(shù)為mi - 1（i=1,2,h），顯然當(dāng)高度為），顯然當(dāng)高度為h的的m次樹(shù)（即度為次樹(shù)（即度為m的樹(shù)）上的樹(shù)）上每一層都達(dá)到最多節(jié)點(diǎn)數(shù)時(shí)，整個(gè)每一層都達(dá)到最多節(jié)點(diǎn)數(shù)時(shí)，整個(gè)m次樹(shù)具有最多節(jié)點(diǎn)數(shù)，因次樹(shù)具有最多節(jié)點(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 性質(zhì)性質(zhì)4 具有具有n個(gè)節(jié)點(diǎn)的個(gè)節(jié)點(diǎn)的m次樹(shù)的最小高度為次樹(shù)的最小高度為 logm(n

16、(m-1)+1) 。 證明：證明：設(shè)具有設(shè)具有n個(gè)節(jié)點(diǎn)的個(gè)節(jié)點(diǎn)的m次樹(shù)的高度為次樹(shù)的高度為h，若在該樹(shù)中前，若在該樹(shù)中前h-1層都是滿的，即每一層的節(jié)點(diǎn)數(shù)都等于層都是滿的，即每一層的節(jié)點(diǎn)數(shù)都等于mi-1個(gè)（個(gè)（1ih-1），第），第h層（即最后一層）的節(jié)點(diǎn)數(shù)可能滿，也可能不滿，則該樹(shù)具層（即最后一層）的節(jié)點(diǎn)數(shù)可能滿，也可能不滿，則該樹(shù)具有最小的高度。其高度有最小的高度。其高度h可計(jì)算如下：可計(jì)算如下：m=3，h=3，最多節(jié)點(diǎn)情況，最多節(jié)點(diǎn)情況m=3，h=3，最少節(jié)點(diǎn)情況，最少節(jié)點(diǎn)情況根據(jù)樹(shù)的性質(zhì)根據(jù)樹(shù)的性質(zhì)3可得：可得： n乘乘(m-1)后得：后得： mh-1n(m-1)+1mh以以m為底取對(duì)

17、數(shù)后得：為底取對(duì)數(shù)后得：h-1logm(n(m-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 例例7.1 含含n個(gè)節(jié)點(diǎn)的三次樹(shù)的最小高度是多少？最大高個(gè)節(jié)點(diǎn)的三次樹(shù)的最小高度是多少？最大高度是多少？度是多少？ 解：解：設(shè)含設(shè)含n個(gè)節(jié)點(diǎn)的（為完全三次樹(shù)時(shí)高度最小）的個(gè)節(jié)點(diǎn)的（為完全三次樹(shù)時(shí)高度最?。┑娜螛?shù)的最小高度為三次樹(shù)的最小高度為h，則有：，則有： 1+3+9+3h-2n1+3+9+3h-1 (3h-1-1)/2 n (3h-1)/2

18、3h-12n+13h 即：即：h= log3(2n+1) 最大高度為最大高度為n-2。7.1.5 樹(shù)的基本運(yùn)算樹(shù)的基本運(yùn)算 樹(shù)的運(yùn)算主要分為三大類：樹(shù)的運(yùn)算主要分為三大類： 第一類，尋找滿足某種特定關(guān)系的節(jié)點(diǎn)，如尋找當(dāng)前第一類，尋找滿足某種特定關(guān)系的節(jié)點(diǎn)，如尋找當(dāng)前節(jié)點(diǎn)的雙親節(jié)點(diǎn)等；節(jié)點(diǎn)的雙親節(jié)點(diǎn)等； 第二類，插入或刪除某個(gè)節(jié)點(diǎn)，如在樹(shù)的當(dāng)前節(jié)點(diǎn)上第二類，插入或刪除某個(gè)節(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個(gè)孩子節(jié)點(diǎn)等；個(gè)孩子節(jié)點(diǎn)等； 第三類，遍歷樹(shù)中每個(gè)節(jié)點(diǎn)，這里著重介紹。第三類，遍歷樹(shù)中每個(gè)節(jié)點(diǎn)，這里著重介紹。 樹(shù)的遍歷運(yùn)算是指按某種方式

19、訪問(wèn)樹(shù)中的樹(shù)的遍歷運(yùn)算是指按某種方式訪問(wèn)樹(shù)中的每一個(gè)節(jié)點(diǎn)且每每一個(gè)節(jié)點(diǎn)且每一個(gè)節(jié)點(diǎn)只被訪問(wèn)一次一個(gè)節(jié)點(diǎn)只被訪問(wèn)一次。 有以下三種遍歷方法：有以下三種遍歷方法：樹(shù)的遍歷樹(shù)的遍歷 先根遍歷先根遍歷 后根遍歷后根遍歷 層次遍歷層次遍歷注意：先根和后根遍歷算法都是遞歸的。注意：先根和后根遍歷算法都是遞歸的。先根遍歷先根遍歷: 若樹(shù)不空，則先訪問(wèn)根節(jié)點(diǎn)，然后依次先根遍歷各棵子樹(shù)。若樹(shù)不空，則先訪問(wèn)根節(jié)點(diǎn)，然后依次先根遍歷各棵子樹(shù)。后根遍歷后根遍歷: 若樹(shù)不空，則先依次后根遍歷各棵子樹(shù)，然后訪問(wèn)根節(jié)點(diǎn)。若樹(shù)不空，則先依次后根遍歷各棵子樹(shù)，然后訪問(wèn)根節(jié)點(diǎn)。按層次遍歷按層次遍歷: 若樹(shù)不空，則自上而下自左至右

20、訪問(wèn)樹(shù)中每個(gè)節(jié)點(diǎn)。若樹(shù)不空，則自上而下自左至右訪問(wèn)樹(shù)中每個(gè)節(jié)點(diǎn)。ABCDEFGHJIK 先根遍歷的頂點(diǎn)訪問(wèn)次序：先根遍歷的頂點(diǎn)訪問(wèn)次序：A B E F C D G H I J K 后根遍歷的頂點(diǎn)訪問(wèn)次序：后根遍歷的頂點(diǎn)訪問(wèn)次序：E F B C I J K H G D A 層次遍歷的頂點(diǎn)訪問(wèn)次序：層次遍歷的頂點(diǎn)訪問(wèn)次序：A B C D E F G H I J K7.1.6 樹(shù)的存儲(chǔ)結(jié)構(gòu)樹(shù)的存儲(chǔ)結(jié)構(gòu)1. 1. 雙親存儲(chǔ)結(jié)構(gòu)雙親存儲(chǔ)結(jié)構(gòu) 這種存儲(chǔ)結(jié)構(gòu)是一種順序存儲(chǔ)結(jié)構(gòu)，用一組連續(xù)空間這種存儲(chǔ)結(jié)構(gòu)是一種順序存儲(chǔ)結(jié)構(gòu)，用一組連續(xù)空間存儲(chǔ)樹(shù)的所有節(jié)點(diǎn)，同時(shí)在每個(gè)節(jié)點(diǎn)中附設(shè)一個(gè)存儲(chǔ)樹(shù)的所有節(jié)點(diǎn)，同時(shí)在每個(gè)節(jié)

21、點(diǎn)中附設(shè)一個(gè)偽指針偽指針指指示其雙親節(jié)點(diǎn)的位置。示其雙親節(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ù)的雙親存儲(chǔ)結(jié)構(gòu)示意圖樹(shù)的雙親存儲(chǔ)結(jié)構(gòu)示意圖雙親存儲(chǔ)結(jié)構(gòu)的類型聲明如下：雙親存儲(chǔ)結(jié)構(gòu)的類型聲明如下：typedef struct ElemType data; /節(jié)點(diǎn)的值節(jié)點(diǎn)的值 int parent;/指向雙親的位置指向雙親的位置 PTreeMaxSize;思考題：思考題：該存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)？該存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)？ A D B C G E F A -1 B 0 C 0 D 0 E 2 F 2 G

22、2 0 1 2 3 4 5 6 (a) (b) 2. 孩子鏈存儲(chǔ)結(jié)構(gòu)孩子鏈存儲(chǔ)結(jié)構(gòu) 孩子鏈存儲(chǔ)結(jié)構(gòu)可按樹(shù)的度（即樹(shù)中所有節(jié)點(diǎn)度的最大值）孩子鏈存儲(chǔ)結(jié)構(gòu)可按樹(shù)的度（即樹(shù)中所有節(jié)點(diǎn)度的最大值）設(shè)計(jì)節(jié)點(diǎn)的孩子節(jié)點(diǎn)指針域個(gè)數(shù)。以下左圖的樹(shù)對(duì)應(yīng)的孩子鏈設(shè)計(jì)節(jié)點(diǎn)的孩子節(jié)點(diǎn)指針域個(gè)數(shù)。以下左圖的樹(shù)對(duì)應(yīng)的孩子鏈存儲(chǔ)結(jié)構(gòu)如右圖所示。存儲(chǔ)結(jié)構(gòu)如右圖所示。樹(shù)的樹(shù)的孩子鏈孩子鏈存儲(chǔ)結(jié)構(gòu)示意圖存儲(chǔ)結(jié)構(gòu)示意圖孩子鏈存儲(chǔ)結(jié)構(gòu)的節(jié)點(diǎn)類型聲明如下：孩子鏈存儲(chǔ)結(jié)構(gòu)的節(jié)點(diǎn)類型聲明如下：typedef struct node ElemType data; /節(jié)點(diǎn)的值節(jié)點(diǎn)的值 struct node *sonsMaxSons;/指向孩

23、子節(jié)點(diǎn)指向孩子節(jié)點(diǎn) TSonNode;其中，其中，MaxSons為最多的孩子節(jié)點(diǎn)個(gè)數(shù)。為最多的孩子節(jié)點(diǎn)個(gè)數(shù)。思考題思考題：n個(gè)節(jié)點(diǎn)的個(gè)節(jié)點(diǎn)的m次樹(shù)有多少個(gè)空指針域？次樹(shù)有多少個(gè)空指針域？思考題思考題：該存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)？：該存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)？3. 孩子兄弟鏈存儲(chǔ)結(jié)構(gòu)孩子兄弟鏈存儲(chǔ)結(jié)構(gòu) 孩子兄弟鏈存儲(chǔ)結(jié)構(gòu)是為每個(gè)節(jié)點(diǎn)設(shè)計(jì)三個(gè)域：一個(gè)數(shù)孩子兄弟鏈存儲(chǔ)結(jié)構(gòu)是為每個(gè)節(jié)點(diǎn)設(shè)計(jì)三個(gè)域：一個(gè)數(shù)據(jù)元素域，一個(gè)該節(jié)點(diǎn)的第一個(gè)孩子節(jié)點(diǎn)指針域，一個(gè)該據(jù)元素域，一個(gè)該節(jié)點(diǎn)的第一個(gè)孩子節(jié)點(diǎn)指針域，一個(gè)該節(jié)點(diǎn)的下一個(gè)兄弟節(jié)點(diǎn)指針域。節(jié)點(diǎn)的下一個(gè)兄弟節(jié)點(diǎn)指針域。樹(shù)的樹(shù)的孩子兄弟鏈孩子兄弟鏈存儲(chǔ)結(jié)構(gòu)示意圖存儲(chǔ)結(jié)構(gòu)示意圖兄弟鏈

24、存儲(chǔ)結(jié)構(gòu)中節(jié)點(diǎn)的類型聲明如下：兄弟鏈存儲(chǔ)結(jié)構(gòu)中節(jié)點(diǎn)的類型聲明如下：typedef struct tnode ElemType data;/節(jié)點(diǎn)的值節(jié)點(diǎn)的值 struct tnode *hp; /指向兄弟指向兄弟 struct tnode *vp; /指向孩子節(jié)點(diǎn)指向孩子節(jié)點(diǎn) TSBNode;每個(gè)節(jié)點(diǎn)固定只有兩個(gè)指針域。每個(gè)節(jié)點(diǎn)固定只有兩個(gè)指針域。思考題思考題：該存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)？：該存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)？7.2.1 二叉樹(shù)概念二叉樹(shù)概念 二叉樹(shù)是有限的節(jié)點(diǎn)集合。二叉樹(shù)是有限的節(jié)點(diǎn)集合。 這個(gè)集合或者是空。這個(gè)集合或者是空。 或者由一個(gè)根節(jié)點(diǎn)和兩棵互不相交的稱為左子樹(shù)和右或者由一個(gè)根節(jié)點(diǎn)和兩棵互不相

25、交的稱為左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。子樹(shù)的二叉樹(shù)組成。 注意：二叉樹(shù)的定義是一種遞歸定義。注意：二叉樹(shù)的定義是一種遞歸定義。7.2 二叉樹(shù)概念和性質(zhì)二叉樹(shù)概念和性質(zhì) 二叉樹(shù)的五種基本形態(tài)：二叉樹(shù)的五種基本形態(tài)：空樹(shù)空樹(shù)N只含根節(jié)點(diǎn)只含根節(jié)點(diǎn)L右子樹(shù)為空樹(shù)右子樹(shù)為空樹(shù)NL左右子樹(shù)均左右子樹(shù)均不為空樹(shù)不為空樹(shù)N左子樹(shù)為空樹(shù)左子樹(shù)為空樹(shù)NRR 二叉樹(shù)是可以采用樹(shù)的邏輯結(jié)構(gòu)表示法，其四種表示二叉樹(shù)是可以采用樹(shù)的邏輯結(jié)構(gòu)表示法，其四種表示法如下：法如下： 樹(shù)形表示法樹(shù)形表示法 文氏圖表示法文氏圖表示法 凹入表示法凹入表示法 括號(hào)表示法括號(hào)表示法 在一棵二叉樹(shù)中在一棵二叉樹(shù)中,如果如果所有分支節(jié)點(diǎn)都有左孩

26、子節(jié)點(diǎn)和右孩所有分支節(jié)點(diǎn)都有左孩子節(jié)點(diǎn)和右孩子節(jié)點(diǎn)，子節(jié)點(diǎn)，并且并且葉節(jié)點(diǎn)都集中在二叉樹(shù)的最下一層，葉節(jié)點(diǎn)都集中在二叉樹(shù)的最下一層，這樣的二叉這樣的二叉樹(shù)稱為樹(shù)稱為滿二叉樹(shù)滿二叉樹(shù)。下圖所示就是一棵滿二叉樹(shù)?？梢詫?duì)滿二叉樹(shù)的節(jié)點(diǎn)進(jìn)行下圖所示就是一棵滿二叉樹(shù)。可以對(duì)滿二叉樹(shù)的節(jié)點(diǎn)進(jìn)行連續(xù)編號(hào)，約定編號(hào)從樹(shù)根為連續(xù)編號(hào)，約定編號(hào)從樹(shù)根為1開(kāi)始，按照層數(shù)從小到大、同開(kāi)始，按照層數(shù)從小到大、同一層從左到右的次序進(jìn)行。圖中每個(gè)節(jié)點(diǎn)外邊的數(shù)字為對(duì)該節(jié)一層從左到右的次序進(jìn)行。圖中每個(gè)節(jié)點(diǎn)外邊的數(shù)字為對(duì)該節(jié)點(diǎn)的編號(hào)。點(diǎn)的編號(hào)。 A B C D E H I J K F G L M N O 1 2 3 4 5 6

27、 7 8 9 10 15 11 12 13 14 滿二叉樹(shù)滿二叉樹(shù) 若二叉樹(shù)中最多若二叉樹(shù)中最多只有最下面兩層的節(jié)點(diǎn)的度數(shù)可以小于只有最下面兩層的節(jié)點(diǎn)的度數(shù)可以小于2，并且并且最下面一層的葉節(jié)點(diǎn)都依次排列在該層最左邊的位置上，最下面一層的葉節(jié)點(diǎn)都依次排列在該層最左邊的位置上，則這樣的二叉樹(shù)稱為則這樣的二叉樹(shù)稱為完全二叉樹(shù)完全二叉樹(shù)。如下圖所示為一棵完全二叉樹(shù)。同樣可以對(duì)完全二叉樹(shù)中每如下圖所示為一棵完全二叉樹(shù)。同樣可以對(duì)完全二叉樹(shù)中每個(gè)節(jié)點(diǎn)進(jìn)行連續(xù)編號(hào)，編號(hào)的方法同滿二叉樹(shù)相同。圖中每個(gè)個(gè)節(jié)點(diǎn)進(jìn)行連續(xù)編號(hào)，編號(hào)的方法同滿二叉樹(shù)相同。圖中每個(gè)節(jié)點(diǎn)外邊的數(shù)字為對(duì)該節(jié)點(diǎn)的編號(hào)。節(jié)點(diǎn)外邊的數(shù)字為對(duì)該節(jié)

28、點(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ù) 7.2.2 二叉樹(shù)性質(zhì)二叉樹(shù)性質(zhì) 性質(zhì)性質(zhì)1 非空二叉樹(shù)上葉節(jié)點(diǎn)數(shù)等于雙分支節(jié)點(diǎn)數(shù)加非空二叉樹(shù)上葉節(jié)點(diǎn)數(shù)等于雙分支節(jié)點(diǎn)數(shù)加1。 證明：證明：設(shè)二叉樹(shù)上葉節(jié)點(diǎn)數(shù)為設(shè)二叉樹(shù)上葉節(jié)點(diǎn)數(shù)為n0，單分支節(jié)點(diǎn)數(shù)為，單分支節(jié)點(diǎn)數(shù)為n1，雙分，雙分支節(jié)點(diǎn)數(shù)為支節(jié)點(diǎn)數(shù)為n2，則總節(jié)點(diǎn)數(shù)，則總節(jié)點(diǎn)數(shù)n=n0+n1+n2。在一棵二叉樹(shù)中，所。在一棵二叉樹(shù)中，所有節(jié)點(diǎn)的分支數(shù)（即度數(shù)）應(yīng)等于單分支節(jié)點(diǎn)數(shù)加上雙分支節(jié)有節(jié)點(diǎn)的分支數(shù)（即度數(shù)）應(yīng)等于單分支節(jié)點(diǎn)數(shù)加上雙分支節(jié)點(diǎn)數(shù)的點(diǎn)數(shù)的2倍，即總的分

29、支數(shù)倍，即總的分支數(shù)=n1+2n2。 由于二叉樹(shù)中除根節(jié)點(diǎn)以外，每個(gè)節(jié)點(diǎn)都有唯一的一個(gè)分支由于二叉樹(shù)中除根節(jié)點(diǎn)以外，每個(gè)節(jié)點(diǎn)都有唯一的一個(gè)分支指向它，因此二叉樹(shù)中有：總的分支數(shù)指向它，因此二叉樹(shù)中有：總的分支數(shù)=總節(jié)點(diǎn)數(shù)總節(jié)點(diǎn)數(shù)-1。 由上述三個(gè)等式可得：由上述三個(gè)等式可得：n1+2n2=n0+n1+n2-1即：即：n0=n2+1求解二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)問(wèn)題：求解二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)問(wèn)題：通常利用二叉樹(shù)的性質(zhì)通常利用二叉樹(shù)的性質(zhì)1，即，即n0=n2+1來(lái)求解這類問(wèn)題，也常利用以下關(guān)系求解：來(lái)求解這類問(wèn)題，也常利用以下關(guān)系求解： n=n0+n1+n2 度之和度之和=n-1 度之和度之和=n1+2n2所以

30、有：所以有： n=n1+2n2求解方法歸納求解方法歸納 求解完全二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)問(wèn)題求解完全二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)問(wèn)題：完全二叉樹(shù)屬于二叉：完全二叉樹(shù)屬于二叉樹(shù)，也滿足二叉樹(shù)的性質(zhì)樹(shù)，也滿足二叉樹(shù)的性質(zhì)1，即，即n0=n2+1。 除此之外，完全二叉樹(shù)中一旦除此之外，完全二叉樹(shù)中一旦n確定，其樹(shù)形就確定了，確定，其樹(shù)形就確定了，可以計(jì)算出高度可以計(jì)算出高度h以及以及n0、n1和和n2。其中。其中n1=0或或1，當(dāng)，當(dāng)n為偶數(shù)為偶數(shù)時(shí)，時(shí)，n1=1，當(dāng)，當(dāng)n為奇數(shù)時(shí)，為奇數(shù)時(shí)，n1=0。其關(guān)系有：。其關(guān)系有： h= log2n +1或或h= log2(n+1) 求解方法歸納求解方法歸納例例7.2 已知一

31、棵完全二叉樹(shù)的第已知一棵完全二叉樹(shù)的第6層（設(shè)根為第層（設(shè)根為第1層）有層）有8個(gè)葉節(jié)點(diǎn)，則該完全二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)最多是個(gè)葉節(jié)點(diǎn)，則該完全二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)最多是 。A.39B.52C.111D.119注：本題為注：本題為2009年全國(guó)考研題年全國(guó)考研題求解滿二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)問(wèn)題：求解滿二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)問(wèn)題：滿二叉樹(shù)是最嚴(yán)格的二叉滿二叉樹(shù)是最嚴(yán)格的二叉樹(shù)，一旦樹(shù)，一旦n確定，其樹(shù)形就確定了，可以計(jì)算出高度確定，其樹(shù)形就確定了，可以計(jì)算出高度h以及以及n0、n1和和n2。其關(guān)系有：。其關(guān)系有：h=log2(n+1)n1=0n=2h-1n0=2h-1n2=2h-1-1求解方法歸納求解方法歸納例：一棵

32、滿二叉樹(shù)中共有例：一棵滿二叉樹(shù)中共有n個(gè)節(jié)點(diǎn)，其中有個(gè)節(jié)點(diǎn)，其中有m個(gè)葉子節(jié)點(diǎn)，個(gè)葉子節(jié)點(diǎn)，高度為高度為h，則，則 。A. n=h+mB. h+m=2nC. m=h-1D. n=2h-1 性質(zhì)性質(zhì)2 非空二叉樹(shù)上第非空二叉樹(shù)上第i層上至多有層上至多有2i-1個(gè)節(jié)點(diǎn)，這里應(yīng)有個(gè)節(jié)點(diǎn)，這里應(yīng)有i1。 由樹(shù)的性質(zhì)由樹(shù)的性質(zhì)2可推出?？赏瞥觥?性質(zhì)性質(zhì)3 高度為高度為h的二叉樹(shù)至多有的二叉樹(shù)至多有2h-1個(gè)節(jié)點(diǎn)（個(gè)節(jié)點(diǎn)（h1）。）。 由樹(shù)的性質(zhì)由樹(shù)的性質(zhì)3可推出?？赏瞥觥?性質(zhì)性質(zhì)4 對(duì)完全二叉樹(shù)中編號(hào)為對(duì)完全二叉樹(shù)中編號(hào)為i的節(jié)點(diǎn)（的節(jié)點(diǎn)（1in，n1，n為節(jié)點(diǎn)數(shù)）有：為節(jié)點(diǎn)數(shù)）有： （1）若）若i

33、 n/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ù)，則每個(gè)分支節(jié)點(diǎn)都既有左孩子節(jié)點(diǎn)，為奇數(shù)，則每個(gè)分支節(jié)點(diǎn)都既有左孩子節(jié)點(diǎn)，也有右孩子節(jié)點(diǎn)；若也有右孩子節(jié)點(diǎn)；若n為偶數(shù)，則編號(hào)最大的分支節(jié)點(diǎn)只有為偶數(shù)，則編號(hào)最大的分支節(jié)點(diǎn)只有左孩子節(jié)點(diǎn)，沒(méi)有右孩子節(jié)點(diǎn)，其余分支節(jié)點(diǎn)都有左、右孩左孩子節(jié)點(diǎn)，沒(méi)有右孩子節(jié)點(diǎn)，其余分支節(jié)點(diǎn)都有左、右孩子節(jié)點(diǎn)。子節(jié)點(diǎn)。i/2i2i2i+1 （3）若編號(hào)為）若編號(hào)為i的節(jié)點(diǎn)有左孩子節(jié)點(diǎn)，則左孩子節(jié)點(diǎn)的編的節(jié)點(diǎn)有左孩子節(jié)點(diǎn)，則左孩子節(jié)點(diǎn)的編號(hào)為號(hào)為2i；若編號(hào)為；若編號(hào)為i的節(jié)點(diǎn)有右孩子節(jié)

34、點(diǎn)，則右孩子節(jié)點(diǎn)的編的節(jié)點(diǎn)有右孩子節(jié)點(diǎn)，則右孩子節(jié)點(diǎn)的編號(hào)為號(hào)為(2i+1)。 （4）除樹(shù)根節(jié)點(diǎn)外）除樹(shù)根節(jié)點(diǎn)外,若一個(gè)節(jié)點(diǎn)的編號(hào)為若一個(gè)節(jié)點(diǎn)的編號(hào)為i，則它的雙親，則它的雙親節(jié)點(diǎn)的編號(hào)為節(jié)點(diǎn)的編號(hào)為 i/2 ，也就是說(shuō)，當(dāng)，也就是說(shuō)，當(dāng)i為偶數(shù)時(shí)，其雙親節(jié)點(diǎn)的為偶數(shù)時(shí)，其雙親節(jié)點(diǎn)的編號(hào)為編號(hào)為i/2,它是雙親節(jié)點(diǎn)的左孩子節(jié)點(diǎn)，當(dāng)它是雙親節(jié)點(diǎn)的左孩子節(jié)點(diǎn)，當(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)。，它是雙親節(jié)點(diǎn)的右孩子節(jié)點(diǎn)。思考題：思考題：性質(zhì)性質(zhì)4的特點(diǎn)？的特點(diǎn)？ 性質(zhì)性質(zhì)5 具有具有n個(gè)（個(gè)（n0）節(jié)點(diǎn)的完全二叉樹(shù)的高度為）節(jié)點(diǎn)的

35、完全二叉樹(shù)的高度為 log2n+1 或或 log2n +1。 由完全二叉樹(shù)的定義和樹(shù)的性質(zhì)由完全二叉樹(shù)的定義和樹(shù)的性質(zhì)3可推出?？赏瞥觥?.2.3 二叉樹(shù)與樹(shù)、森林之間的轉(zhuǎn)換二叉樹(shù)與樹(shù)、森林之間的轉(zhuǎn)換1森林、樹(shù)轉(zhuǎn)換為二叉樹(shù)森林、樹(shù)轉(zhuǎn)換為二叉樹(shù) 步驟如下：步驟如下： （1）在所有相鄰兄弟節(jié)點(diǎn)（森林中每棵樹(shù)的根節(jié)點(diǎn)可看）在所有相鄰兄弟節(jié)點(diǎn)（森林中每棵樹(shù)的根節(jié)點(diǎn)可看成是兄弟節(jié)點(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）所有水平線段以左邊

36、節(jié)點(diǎn)為軸心順時(shí)針旋轉(zhuǎn)）所有水平線段以左邊節(jié)點(diǎn)為軸心順時(shí)針旋轉(zhuǎn)45度。度。 通過(guò)以上步驟，原來(lái)的森林就轉(zhuǎn)換為一棵二叉樹(shù)。通過(guò)以上步驟，原來(lái)的森林就轉(zhuǎn)換為一棵二叉樹(shù)。 一般的樹(shù)是森林中的特殊情況，由一般的樹(shù)轉(zhuǎn)換的二叉樹(shù)一般的樹(shù)是森林中的特殊情況，由一般的樹(shù)轉(zhuǎn)換的二叉樹(shù)的根節(jié)點(diǎn)的右孩子節(jié)點(diǎn)始終為空，原因是一般的樹(shù)的根節(jié)點(diǎn)的根節(jié)點(diǎn)的右孩子節(jié)點(diǎn)始終為空，原因是一般的樹(shù)的根節(jié)點(diǎn)不存在兄弟節(jié)點(diǎn)和相鄰的樹(shù)。不存在兄弟節(jié)點(diǎn)和相鄰的樹(shù)。ABCDEFGHII將森林轉(zhuǎn)換為二叉樹(shù)的過(guò)程將森林轉(zhuǎn)換為二叉樹(shù)的過(guò)程2. 二叉樹(shù)還原為森林、樹(shù)二叉樹(shù)還原為森林、樹(shù) 步驟如下：步驟如下： （1）對(duì)于一棵二叉樹(shù)中任一節(jié)點(diǎn)）對(duì)于一棵二

37、叉樹(shù)中任一節(jié)點(diǎn)k0，沿著，沿著k0的左孩子的左孩子節(jié)點(diǎn)節(jié)點(diǎn)k1的右子樹(shù)方向搜索所有右孩子節(jié)點(diǎn)，即搜索節(jié)點(diǎn)序的右子樹(shù)方向搜索所有右孩子節(jié)點(diǎn)，即搜索節(jié)點(diǎn)序列列k2,k3,km，其中，其中ki+1為為ki的右孩子節(jié)點(diǎn)（的右孩子節(jié)點(diǎn)（1im），），km沒(méi)有右孩子節(jié)點(diǎn)。沒(méi)有右孩子節(jié)點(diǎn)。 （2）刪去）刪去k1,k2,km之間連線。之間連線。 （3）若）若k1有雙親節(jié)點(diǎn)有雙親節(jié)點(diǎn)k0，則連接，則連接k0與與ki（2im）。）。 （4）將圖形規(guī)整化，使各節(jié)點(diǎn)按層次排列）將圖形規(guī)整化，使各節(jié)點(diǎn)按層次排列。 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

38、 G (b) 將一棵二叉樹(shù)還原為樹(shù)的過(guò)程將一棵二叉樹(shù)還原為樹(shù)的過(guò)程 例例7.3 設(shè)森林設(shè)森林F中有中有3棵樹(shù)，第一、第二和第三棵樹(shù)的節(jié)棵樹(shù)，第一、第二和第三棵樹(shù)的節(jié)點(diǎn)個(gè)數(shù)分別為點(diǎn)個(gè)數(shù)分別為9、8和和7，則與森林，則與森林F對(duì)應(yīng)的二叉樹(shù)根節(jié)點(diǎn)的右對(duì)應(yīng)的二叉樹(shù)根節(jié)點(diǎn)的右子樹(shù)上的節(jié)點(diǎn)個(gè)數(shù)是子樹(shù)上的節(jié)點(diǎn)個(gè)數(shù)是 。A. 16B. 15C. 7D. 17 例例7.4 設(shè)一棵二叉樹(shù)是由森林轉(zhuǎn)換而來(lái)的，若森林中有設(shè)一棵二叉樹(shù)是由森林轉(zhuǎn)換而來(lái)的，若森林中有n個(gè)非終端節(jié)點(diǎn)，則二叉樹(shù)中無(wú)右孩子的節(jié)點(diǎn)個(gè)數(shù)為個(gè)非終端節(jié)點(diǎn)，則二叉樹(shù)中無(wú)右孩子的節(jié)點(diǎn)個(gè)數(shù)為 。 A. n-1B. n C. n+1D. n+2設(shè)計(jì)題：設(shè)計(jì)題：

39、設(shè)計(jì)一棵二叉樹(shù)，表示夫妻、父子和兄弟關(guān)系。設(shè)計(jì)一棵二叉樹(shù)，表示夫妻、父子和兄弟關(guān)系。思考題：思考題：樹(shù)樹(shù)二叉樹(shù)，二叉樹(shù)二叉樹(shù)，二叉樹(shù)樹(shù)樹(shù)為什么沒(méi)有討論樹(shù)的算法？為什么沒(méi)有討論樹(shù)的算法？7.3.1 二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu) 二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)中節(jié)點(diǎn)的存放次序是：對(duì)該二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)中節(jié)點(diǎn)的存放次序是：對(duì)該樹(shù)中每個(gè)節(jié)點(diǎn)進(jìn)行編號(hào)，其編號(hào)從小到大的順序就是節(jié)點(diǎn)樹(shù)中每個(gè)節(jié)點(diǎn)進(jìn)行編號(hào)，其編號(hào)從小到大的順序就是節(jié)點(diǎn)存放在連續(xù)存儲(chǔ)單元的先后次序。存放在連續(xù)存儲(chǔ)單元的先后次序。 若把二叉樹(shù)存儲(chǔ)到一維數(shù)組中若把二叉樹(shù)存儲(chǔ)到一維數(shù)組中,則該編號(hào)就是下標(biāo)值則該編號(hào)就是下標(biāo)值加加1（注意（注意C/

40、C+語(yǔ)言中數(shù)組的起始下標(biāo)為語(yǔ)言中數(shù)組的起始下標(biāo)為0）。樹(shù)中各節(jié)）。樹(shù)中各節(jié)點(diǎn)的編號(hào)與等高度的完全二叉樹(shù)中對(duì)應(yīng)位置上節(jié)點(diǎn)的編號(hào)點(diǎn)的編號(hào)與等高度的完全二叉樹(shù)中對(duì)應(yīng)位置上節(jié)點(diǎn)的編號(hào)相同。相同。 利用二叉樹(shù)的性質(zhì)利用二叉樹(shù)的性質(zhì)4。7.3 二叉樹(shù)存儲(chǔ)結(jié)構(gòu)二叉樹(shù)存儲(chǔ)結(jié)構(gòu) A B C D E H I J K F G 1 2 3 4 5 6 7 8 9 10 11 完全二叉樹(shù)完全二叉樹(shù) ABCDEFGHIJK123456789101112131415順序存儲(chǔ)結(jié)構(gòu)（不用下標(biāo)為順序存儲(chǔ)結(jié)構(gòu)（不用下標(biāo)為0的元素）的元素）ABCDEF A B D # C # E # # # # # # F 1 2 3 4 5 6

41、7 8 9 10 11 12 13 142511437一般的二叉樹(shù)先用空節(jié)點(diǎn)一般的二叉樹(shù)先用空節(jié)點(diǎn)補(bǔ)全成為完全二叉樹(shù)，然補(bǔ)全成為完全二叉樹(shù)，然后對(duì)節(jié)點(diǎn)編號(hào)后對(duì)節(jié)點(diǎn)編號(hào)typedef ElemType SqBTreeMaxSize;SqBTree bt=#ABD#C#E#F;7.3.2 二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 在二叉樹(shù)的鏈接存儲(chǔ)中，節(jié)點(diǎn)的結(jié)構(gòu)如下在二叉樹(shù)的鏈接存儲(chǔ)中，節(jié)點(diǎn)的結(jié)構(gòu)如下: typedef struct node ElemType data; struct node *lchild,*rchild; BTNode; 其中其中,data表示值域表示值域,用于存儲(chǔ)對(duì)應(yīng)的數(shù)

42、據(jù)元素，用于存儲(chǔ)對(duì)應(yīng)的數(shù)據(jù)元素，lchild和和rchild分別表示左指針域和右指針域，用于分別存儲(chǔ)左孩子節(jié)分別表示左指針域和右指針域，用于分別存儲(chǔ)左孩子節(jié)點(diǎn)和右孩子節(jié)點(diǎn)（即左、右子樹(shù)的根節(jié)點(diǎn)）的存儲(chǔ)位置。點(diǎn)和右孩子節(jié)點(diǎn)（即左、右子樹(shù)的根節(jié)點(diǎn)）的存儲(chǔ)位置。二叉樹(shù)及其鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：二叉鏈二叉樹(shù)及其鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：二叉鏈 ABCDEGFABDGCEFb7.4.1 二叉樹(shù)的基本運(yùn)算概述二叉樹(shù)的基本運(yùn)算概述 歸納起來(lái)，二叉樹(shù)有以下基本運(yùn)算：歸納起來(lái)，二叉樹(shù)有以下基本運(yùn)算： （1）創(chuàng)建二叉樹(shù)）創(chuàng)建二叉樹(shù)CreateBTNode(*b,*str)：根據(jù)二叉樹(shù)括：根據(jù)二叉樹(shù)括號(hào)表示法的字符串號(hào)表示法的字符串*

43、str生成對(duì)應(yīng)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。生成對(duì)應(yīng)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 （2）查找節(jié)點(diǎn)）查找節(jié)點(diǎn)FindNode(*b,x)：在二叉樹(shù)：在二叉樹(shù)b中尋找中尋找data域域值為值為x的節(jié)點(diǎn)，并返回指向該節(jié)點(diǎn)的指針。的節(jié)點(diǎn)，并返回指向該節(jié)點(diǎn)的指針。 （3）找孩子節(jié)點(diǎn)）找孩子節(jié)點(diǎn)LchildNode(p)和和Rchild-Node(p)：分別：分別求二叉樹(shù)中節(jié)點(diǎn)求二叉樹(shù)中節(jié)點(diǎn)*p的左孩子節(jié)點(diǎn)和右孩子節(jié)點(diǎn)。的左孩子節(jié)點(diǎn)和右孩子節(jié)點(diǎn)。7.4 二叉樹(shù)的基本運(yùn)算及其實(shí)現(xiàn)二叉樹(shù)的基本運(yùn)算及其實(shí)現(xiàn) （4）求高度）求高度BTNodeDepth(*b)：求二叉樹(shù)：求二叉樹(shù)b的高度。若二的高度。若二叉樹(shù)為空，則其高度為叉樹(shù)為空，則其

44、高度為0；否則，其高度等于左子樹(shù)與右子樹(shù)；否則，其高度等于左子樹(shù)與右子樹(shù)中的最大高度加中的最大高度加l。 （5）輸出二叉樹(shù)）輸出二叉樹(shù)DispBTNode(*b)：以括號(hào)表示法輸出一：以括號(hào)表示法輸出一棵二叉樹(shù)?？枚鏄?shù)。7.4.2 二叉樹(shù)的基本運(yùn)算算法實(shí)現(xiàn)二叉樹(shù)的基本運(yùn)算算法實(shí)現(xiàn) （1）創(chuàng)建二叉樹(shù)）創(chuàng)建二叉樹(shù)CreateBTNode(*b,*str) 用用ch掃描采用括號(hào)表示法表示二叉樹(shù)的字符串。分以下幾種掃描采用括號(hào)表示法表示二叉樹(shù)的字符串。分以下幾種情況：情況： 若若ch=(：則將前面剛創(chuàng)建的節(jié)點(diǎn)作為雙親節(jié)點(diǎn)進(jìn)棧，并：則將前面剛創(chuàng)建的節(jié)點(diǎn)作為雙親節(jié)點(diǎn)進(jìn)棧，并置置k=1，表示其后創(chuàng)建的節(jié)點(diǎn)

45、將作為這個(gè)節(jié)點(diǎn)的左孩子節(jié)點(diǎn)；，表示其后創(chuàng)建的節(jié)點(diǎn)將作為這個(gè)節(jié)點(diǎn)的左孩子節(jié)點(diǎn)； 若若ch=)：表示棧中節(jié)點(diǎn)的左右孩子節(jié)點(diǎn)處理完畢，退棧；：表示棧中節(jié)點(diǎn)的左右孩子節(jié)點(diǎn)處理完畢，退棧； 若若ch=,：表示其后創(chuàng)建的節(jié)點(diǎn)為右孩子節(jié)點(diǎn)，置：表示其后創(chuàng)建的節(jié)點(diǎn)為右孩子節(jié)點(diǎn)，置k=2； 其他情況：其他情況： 當(dāng)當(dāng)k=1時(shí)，表示這個(gè)節(jié)點(diǎn)作為棧中節(jié)點(diǎn)的左孩子節(jié)點(diǎn)；時(shí)，表示這個(gè)節(jié)點(diǎn)作為棧中節(jié)點(diǎn)的左孩子節(jié)點(diǎn)； 當(dāng)當(dāng)k=2時(shí)，表示這個(gè)節(jié)點(diǎn)作為棧中節(jié)點(diǎn)的右孩子節(jié)點(diǎn)。如時(shí)，表示這個(gè)節(jié)點(diǎn)作為棧中節(jié)點(diǎn)的右孩子節(jié)點(diǎn)。如此循環(huán)直到此循環(huán)直到str處理完畢。處理完畢。 算法中使用一個(gè)棧算法中使用一個(gè)棧St保存雙親節(jié)點(diǎn)，保存雙親節(jié)點(diǎn)

46、，top為其棧指針，為其棧指針，k指定其后處理的節(jié)點(diǎn)是雙親節(jié)點(diǎn)（保存在棧中）的左孩子節(jié)指定其后處理的節(jié)點(diǎn)是雙親節(jié)點(diǎn)（保存在棧中）的左孩子節(jié)點(diǎn)（點(diǎn)（k=1）還是右孩子節(jié)點(diǎn)（）還是右孩子節(jié)點(diǎn)（k=2）。）。A ( B ( D ( , G ) ) , C ( E , F ) )Ak=1 2B A B D G C E F DC根據(jù)括號(hào)表示法字符串構(gòu)造二叉樹(shù)根據(jù)括號(hào)表示法字符串構(gòu)造二叉樹(shù)void CreateBTNode(BTNode * &b,char *str) BTNode *StMaxSize,*p=NULL; int top=-1,k,j=0; char ch; b=NULL;/建立的二叉樹(shù)初

47、始時(shí)為空建立的二叉樹(shù)初始時(shí)為空 ch=strj; while (ch!=0) /str未掃描完時(shí)循環(huán)未掃描完時(shí)循環(huán) switch(ch) case (:top+;Sttop=p;k=1; break; /為左孩子節(jié)點(diǎn)為左孩子節(jié)點(diǎn) case ):top-;break; case ,:k=2; break; /為孩子節(jié)點(diǎn)右節(jié)點(diǎn)為孩子節(jié)點(diǎn)右節(jié)點(diǎn) default: p=(BTNode *)malloc(sizeof(BTNode); p-data=ch;p-lchild=p-rchild=NULL; if (b=NULL) /p為二叉樹(shù)的根節(jié)點(diǎn)為二叉樹(shù)的根節(jié)點(diǎn) b=p; else /已建立二叉樹(shù)根節(jié)點(diǎn)

48、已建立二叉樹(shù)根節(jié)點(diǎn) switch(k) case 1:Sttop-lchild=p;break;case 2:Sttop-rchild=p;break; j+;ch=strj; （2）查找節(jié)點(diǎn)）查找節(jié)點(diǎn)FindNode(*b,x) 采用先序遍歷遞歸算法查找值為采用先序遍歷遞歸算法查找值為x的節(jié)點(diǎn)。找到后返回其指的節(jié)點(diǎn)。找到后返回其指針，否則返回針，否則返回NULL。算法如下：。算法如下： BTNode *FindNode(BTNode *b,ElemType x) BTNode *p; if (b=NULL) return NULL; else if (b-data=x) return b;

49、else p=FindNode(b-lchild,x); if (p!=NULL) return p; else return FindNode(b-rchild,x); （3）找孩子節(jié)點(diǎn)）找孩子節(jié)點(diǎn)LchildNode(p)和和RchildNode(p) 直接返回直接返回*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; （4）求高度）求高度BTNodeDept

50、h(*b) 求二叉樹(shù)的高度的遞歸模型求二叉樹(shù)的高度的遞歸模型f()如下：如下： f(b) = 0 b=NULL f(b) = MAXf(b-lchild),f(b-rchild)+1 其他情況其他情況int BTNodeDepth(BTNode *b) int lchilddep,rchilddep; if (b=NULL) return(0); /空樹(shù)的高度為空樹(shù)的高度為0 else lchilddep=BTNodeDepth(b-lchild);/求左子樹(shù)的高度為求左子樹(shù)的高度為lchilddep rchilddep=BTNodeDepth(b-rchild);/求右子樹(shù)的高度為求右子樹(shù)的

51、高度為rchilddep return(lchilddeprchilddep)? (lchilddep+1):(rchilddep+1); （5）輸出二叉樹(shù)）輸出二叉樹(shù)DispBTNode(*b) 用括弧表示法輸出二叉樹(shù)。用括弧表示法輸出二叉樹(shù)。 對(duì)于非空二叉樹(shù)對(duì)于非空二叉樹(shù)b，先輸出其元素值，當(dāng)存在左孩子節(jié)點(diǎn)，先輸出其元素值，當(dāng)存在左孩子節(jié)點(diǎn)或右孩子節(jié)點(diǎn)時(shí)，輸出一個(gè)或右孩子節(jié)點(diǎn)時(shí)，輸出一個(gè)“(”符號(hào)，然后遞歸處理左子樹(shù)，符號(hào)，然后遞歸處理左子樹(shù)，輸出一個(gè)輸出一個(gè)“,”符號(hào)，遞歸處理右子樹(shù)，最后輸出一個(gè)符號(hào)，遞歸處理右子樹(shù)，最后輸出一個(gè)“)”符號(hào)。符號(hào)。void DispBTNode(BTNo

52、de *b) if (b!=NULL) printf(%c,b-data); if (b-lchild!=NULL | b-rchild!=NULL) printf(); DispBTNode(b-lchild); /遞歸處理左子樹(shù)遞歸處理左子樹(shù) if (b-rchild!=NULL) printf(,); DispBTNode(b-rchild);/遞歸處理右子樹(shù)遞歸處理右子樹(shù) printf(); 7.5.1 二叉樹(shù)遍歷的概念二叉樹(shù)遍歷的概念 二叉樹(shù)的遍歷是指按照一定次序訪問(wèn)樹(shù)中所有節(jié)點(diǎn)，并二叉樹(shù)的遍歷是指按照一定次序訪問(wèn)樹(shù)中所有節(jié)點(diǎn)，并且且每個(gè)節(jié)點(diǎn)僅被訪問(wèn)一次每個(gè)節(jié)點(diǎn)僅被訪問(wèn)一次的過(guò)程。它

53、是最基本的運(yùn)算的過(guò)程。它是最基本的運(yùn)算,是二叉是二叉樹(shù)中所有其他運(yùn)算的基礎(chǔ)。樹(shù)中所有其他運(yùn)算的基礎(chǔ)。7.5 二叉樹(shù)的遍歷二叉樹(shù)的遍歷1. 先序遍歷過(guò)程先序遍歷過(guò)程先序遍歷二叉樹(shù)的過(guò)程是：先序遍歷二叉樹(shù)的過(guò)程是： 訪問(wèn)根節(jié)點(diǎn)；訪問(wèn)根節(jié)點(diǎn)； 先序遍歷左子樹(shù)；先序遍歷左子樹(shù)； 先序遍歷右子樹(shù)。先序遍歷右子樹(shù)。ABCDEFGHK先序序列：先序序列：A B C D EHGKF2. 中序遍歷過(guò)程中序遍歷過(guò)程中序遍歷二叉樹(shù)的過(guò)程是：中序遍歷二叉樹(shù)的過(guò)程是： 中序遍歷左子樹(shù)；中序遍歷左子樹(shù)； 訪問(wèn)根節(jié)點(diǎn)；訪問(wèn)根節(jié)點(diǎn)； 中序遍歷右子樹(shù)。中序遍歷右子樹(shù)。ABCDEFGHK中序序列：中序序列：ABCDE H G K

54、 F3. 后序遍歷過(guò)程后序遍歷過(guò)程后序遍歷二叉樹(shù)的過(guò)程是：后序遍歷二叉樹(shù)的過(guò)程是： 后序遍歷左子樹(shù)；后序遍歷左子樹(shù)； 后序遍歷右子樹(shù)；后序遍歷右子樹(shù)； 訪問(wèn)根節(jié)點(diǎn)。訪問(wèn)根節(jié)點(diǎn)。ABCDEFGHK后序序列：后序序列：ABCDEHGKF7.5.3 二叉樹(shù)遍歷遞歸算法二叉樹(shù)遍歷遞歸算法 由二叉樹(shù)的三種遍歷過(guò)程直接得到如下三種遞歸算法。由二叉樹(shù)的三種遍歷過(guò)程直接得到如下三種遞歸算法。 先序遍歷的遞歸算法：先序遍歷的遞歸算法： void PreOrder(BTNode *b) if (b!=NULL) printf(%c ,b-data); /訪問(wèn)根節(jié)點(diǎn)訪問(wèn)根節(jié)點(diǎn) PreOrder(b-lchild);

55、 PreOrder(b-rchild); ABCDEFGHK先序序列：先序序列：A 形參形參T T取值取值 下層調(diào)用結(jié)束后返回到下層調(diào)用結(jié)束后返回到主調(diào)應(yīng)該執(zhí)行的語(yǔ)句主調(diào)應(yīng)該執(zhí)行的語(yǔ)句A B C D EHGKFB 445C 4D 4 555E 4 5G 4 5H 4 5K 4 5F 4 5遞歸算法執(zhí)行時(shí)系統(tǒng)棧的變化遞歸算法執(zhí)行時(shí)系統(tǒng)棧的變化 PreOrder(A) 訪問(wèn)訪問(wèn) A PreOrder(B) 訪問(wèn)訪問(wèn) B PreOrder(D) 訪問(wèn)訪問(wèn) D PreOrder(NULL) PreOrder(G) 訪問(wèn)訪問(wèn) G PreOrder(NULL) PreOrder(NULL) PreOrde

56、r(NULL) PreOrder(C) 訪問(wèn)訪問(wèn) C PreOrder(E) 訪問(wèn)訪問(wèn) E PreOrder(NULL) PreOrder(NULL) PreOrder(F) 訪問(wèn)訪問(wèn) F PreOrder(NULL) PreOrder(NULL) 遞歸算法執(zhí)行過(guò)程：遞歸算法執(zhí)行過(guò)程： 中序遍歷的遞歸算法：中序遍歷的遞歸算法： void InOrder(BTNode *b) if (b!=NULL) InOrder(b-lchild); printf(%c ,b-data); /訪問(wèn)根節(jié)點(diǎn)訪問(wèn)根節(jié)點(diǎn) InOrder(b-rchild); 后序遍歷遞歸算法：后序遍歷遞歸算法： void Post

57、Order(BTNode *b) if (b!=NULL) PostOrder(b-lchild); PostOrder(b-rchild); printf(%c ,b-data); /訪問(wèn)根節(jié)點(diǎn)訪問(wèn)根節(jié)點(diǎn) 思考題：思考題：每種遍歷序列提供了什么信息？每種遍歷序列提供了什么信息？為什么三種遍歷都采用遞歸求解？為什么三種遍歷都采用遞歸求解？ 例例7.5 假設(shè)二叉樹(shù)采用二叉鏈存儲(chǔ)結(jié)構(gòu)存儲(chǔ)，試設(shè)計(jì)一個(gè)算假設(shè)二叉樹(shù)采用二叉鏈存儲(chǔ)結(jié)構(gòu)存儲(chǔ)，試設(shè)計(jì)一個(gè)算法，計(jì)算一棵給定二叉樹(shù)的所有節(jié)點(diǎn)個(gè)數(shù)。法，計(jì)算一棵給定二叉樹(shù)的所有節(jié)點(diǎn)個(gè)數(shù)。 解：計(jì)算一棵二叉樹(shù)解：計(jì)算一棵二叉樹(shù)b中所有節(jié)點(diǎn)個(gè)數(shù)的遞歸模型中所有節(jié)點(diǎn)個(gè)數(shù)

58、的遞歸模型f(b)如下：如下：f(b)=0若若b=NULLf(b)=f(b- -lchild)+f(b- -rchild)+1其他情況其他情況bb- -lchildb- -rchild對(duì)應(yīng)的遞歸算法如下：對(duì)應(yīng)的遞歸算法如下：int Nodes(BTNode *b) int num1,num2; if (b=NULL) return 0; else return Nodes(b-lchild)+Nodes(b-rchild)+1提示：本題算法是基于后序遍歷的。提示：本題算法是基于后序遍歷的。 例例7.6 假設(shè)二叉樹(shù)采用二叉鏈存儲(chǔ)結(jié)構(gòu)存儲(chǔ)，試設(shè)計(jì)一個(gè)假設(shè)二叉樹(shù)采用二叉鏈存儲(chǔ)結(jié)構(gòu)存儲(chǔ)，試設(shè)計(jì)一個(gè)算法

59、，計(jì)算一棵給定二叉樹(shù)的所有葉子節(jié)點(diǎn)個(gè)數(shù)。算法，計(jì)算一棵給定二叉樹(shù)的所有葉子節(jié)點(diǎn)個(gè)數(shù)。 解：解：計(jì)算一棵二叉樹(shù)計(jì)算一棵二叉樹(shù)b中所有葉子節(jié)點(diǎn)個(gè)數(shù)的遞歸模型中所有葉子節(jié)點(diǎn)個(gè)數(shù)的遞歸模型f(b)如下：如下：f(b)=0若若b=NULLf(b)=1若若*b為葉子節(jié)點(diǎn)為葉子節(jié)點(diǎn)f(b)=f(b- -lchild)+f(b- -rchild)其他情況其他情況int LeafNodes(BTNode *b)int num1,num2; if (b=NULL) return 0; else if (b-lchild=NULL & b-rchild=NULL) return 1; else num1=LeafN

60、odes(b-lchild);num2=LeafNodes(b-rchild);return (num1+num2); 例例7.7 假設(shè)二叉樹(shù)采用二叉鏈存儲(chǔ)結(jié)構(gòu)存儲(chǔ)，試設(shè)計(jì)一個(gè)假設(shè)二叉樹(shù)采用二叉鏈存儲(chǔ)結(jié)構(gòu)存儲(chǔ)，試設(shè)計(jì)一個(gè)算法，計(jì)算一棵給定二叉樹(shù)的所有單分支節(jié)點(diǎn)個(gè)數(shù)。算法，計(jì)算一棵給定二叉樹(shù)的所有單分支節(jié)點(diǎn)個(gè)數(shù)。 解：解：計(jì)算一棵二叉樹(shù)計(jì)算一棵二叉樹(shù)b中所有單分支節(jié)點(diǎn)個(gè)數(shù)的遞歸模型中所有單分支節(jié)點(diǎn)個(gè)數(shù)的遞歸模型f(b)如下：如下：f(b)=0若若b=NULLf(b)=f(b- -lchild)+f(b- -rchild)+1若若*b為單分支節(jié)點(diǎn)為單分支節(jié)點(diǎn)f(b)=f(b- -lchild)+f