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

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

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

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

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

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

6、m次樹次樹。 2. 分支節(jié)點與葉節(jié)點：分支節(jié)點與葉節(jié)點：度不為零的節(jié)點稱為非終端節(jié)點度不為零的節(jié)點稱為非終端節(jié)點,又叫分支節(jié)點。度為零的節(jié)點稱為終端節(jié)點或葉節(jié)點。在分又叫分支節(jié)點。度為零的節(jié)點稱為終端節(jié)點或葉節(jié)點。在分支節(jié)點中，每個節(jié)點的分支數(shù)就是該節(jié)點的度。如對于度為支節(jié)點中，每個節(jié)點的分支數(shù)就是該節(jié)點的度。如對于度為1的節(jié)點的節(jié)點,其分支數(shù)為其分支數(shù)為1，被稱為單分支節(jié)點；對于度為，被稱為單分支節(jié)點；對于度為2的節(jié)的節(jié)點，其分支數(shù)為點，其分支數(shù)為2，被稱為雙分支節(jié)點，其余類推。，被稱為雙分支節(jié)點，其余類推。ABCDEFGJHIKLM度為度為3度為度為2 3. 路徑與路徑長度：路徑與路徑長度

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

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

9、點的路徑上經(jīng)過的所有節(jié)點被稱作該節(jié)點的過的所有節(jié)點被稱作該節(jié)點的祖先節(jié)祖先節(jié)點點。ABCDEFGJHIKLM 5. 節(jié)點的層次和樹的高度：節(jié)點的層次和樹的高度：樹樹中的每個節(jié)點都處在一定的層次上。中的每個節(jié)點都處在一定的層次上。節(jié)點的層次從樹根開始定義，根節(jié)節(jié)點的層次從樹根開始定義，根節(jié)點為第點為第1層，它的孩子節(jié)點為第層，它的孩子節(jié)點為第2層層,以此類推以此類推,一個節(jié)點所在的層次為一個節(jié)點所在的層次為其雙親節(jié)點所在的層次加其雙親節(jié)點所在的層次加1。樹中。樹中節(jié)點的最大層次稱為樹的節(jié)點的最大層次稱為樹的高度高度（或（或樹的樹的深度深度）。）。 6. 有序樹和無序樹：有序樹和無序樹：若樹中各若

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

11、則森林就變成了樹。就變成了樹。7.1.4 樹的性質(zhì)樹的性質(zhì)性質(zhì)性質(zhì)1 樹中的節(jié)點數(shù)等于所有節(jié)點樹中的節(jié)點數(shù)等于所有節(jié)點的度數(shù)加的度數(shù)加1。 證明：證明：根據(jù)樹的定義，在一棵樹中，根據(jù)樹的定義，在一棵樹中，除樹根節(jié)點外，每個節(jié)點有且僅有一除樹根節(jié)點外，每個節(jié)點有且僅有一個前驅(qū)節(jié)點。也就是說，每個節(jié)點與個前驅(qū)節(jié)點。也就是說，每個節(jié)點與指向它的一個分支一一對應(yīng)，所以除指向它的一個分支一一對應(yīng)，所以除樹根之外的節(jié)點數(shù)等于所有節(jié)點的分樹根之外的節(jié)點數(shù)等于所有節(jié)點的分支數(shù)（度數(shù)），從而可得樹中的節(jié)點支數(shù)（度數(shù)），從而可得樹中的節(jié)點數(shù)等于所有節(jié)點的度數(shù)加數(shù)等于所有節(jié)點的度數(shù)加1。度之和分支數(shù)度之和分支數(shù)分支

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

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

14、樣得到只有一個節(jié)點，顯然結(jié)論成立。節(jié)點，顯然結(jié)論成立。 假設(shè)對于第假設(shè)對于第(i-1)層（層（i1）命題成立，即度為）命題成立，即度為m的樹中第的樹中第(i-1)層上至多有層上至多有mi-2個節(jié)點。個節(jié)點。 則根據(jù)樹的度的定義，度為則根據(jù)樹的度的定義，度為m的樹中每個節(jié)點至多有的樹中每個節(jié)點至多有m個孩個孩子節(jié)點，所以第子節(jié)點，所以第i層上的節(jié)點數(shù)至多為第層上的節(jié)點數(shù)至多為第(i-1)層上節(jié)點數(shù)的層上節(jié)點數(shù)的m倍，倍，即至多為即至多為mi-2m=mi-1個，這與命題相同，故命題成立。個，這與命題相同，故命題成立。 性質(zhì)性質(zhì)3 高度為高度為h的的m次樹至多有次樹至多有 個節(jié)點。個節(jié)點。 證明：證

15、明：由樹的性質(zhì)由樹的性質(zhì)2可知可知,第第i層上最多節(jié)點數(shù)為層上最多節(jié)點數(shù)為mi - 1（i=1,2,h），顯然當(dāng)高度為），顯然當(dāng)高度為h的的m次樹（即度為次樹（即度為m的樹）上的樹）上每一層都達到最多節(jié)點數(shù)時，整個每一層都達到最多節(jié)點數(shù)時，整個m次樹具有最多節(jié)點數(shù)，因次樹具有最多節(jié)點數(shù)，因此有：此有：整 個 樹 的 最 多 節(jié) 點 數(shù)整 個 樹 的 最 多 節(jié) 點 數(shù) = 每 一 層 最 多 節(jié) 點 數(shù) 之 和每 一 層 最 多 節(jié) 點 數(shù) 之 和=m0+m1+m2+mh-1 = 。11 mmh11 mmh 性質(zhì)性質(zhì)4 具有具有n個節(jié)點的個節(jié)點的m次樹的最小高度為次樹的最小高度為 logm(n

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

17、數(shù)后得：為底取對數(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個節(jié)點的三次樹的最小高度是多少？最大高個節(jié)點的三次樹的最小高度是多少？最大高度是多少？度是多少？ 解：解：設(shè)含設(shè)含n個節(jié)點的（為完全三次樹時高度最小）的個節(jié)點的（為完全三次樹時高度最?。┑娜螛涞淖钚「叨葹槿螛涞淖钚「叨葹閔，則有：，則有： 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 樹的基本運算樹的基本運算 樹的運算主要分為三大類：樹的運算主要分為三大類： 第一類，尋找滿足某種特定關(guān)系的節(jié)點，如尋找當(dāng)前第一類，尋找滿足某種特定關(guān)系的節(jié)點，如尋找當(dāng)前節(jié)點的雙親節(jié)點等；節(jié)點的雙親節(jié)點等； 第二類，插入或刪除某個節(jié)點，如在樹的當(dāng)前節(jié)點上第二類，插入或刪除某個節(jié)點，如在樹的當(dāng)前節(jié)點上插入一個新節(jié)點或刪除當(dāng)前節(jié)點的第插入一個新節(jié)點或刪除當(dāng)前節(jié)點的第i個孩子節(jié)點等；個孩子節(jié)點等； 第三類，遍歷樹中每個節(jié)點，這里著重介紹。第三類，遍歷樹中每個節(jié)點，這里著重介紹。 樹的遍歷運算是指按某種方式

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

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

21、點中附設(shè)一個偽指針偽指針指指示其雙親節(jié)點的位置。示其雙親節(jié)點的位置。 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) 樹的雙親存儲結(jié)構(gòu)示意圖樹的雙親存儲結(jié)構(gòu)示意圖雙親存儲結(jié)構(gòu)的類型聲明如下：雙親存儲結(jié)構(gòu)的類型聲明如下：typedef struct ElemType data; /節(jié)點的值節(jié)點的值 int parent;/指向雙親的位置指向雙親的位置 PTreeMaxSize;思考題：思考題：該存儲結(jié)構(gòu)的優(yōu)缺點？該存儲結(jié)構(gòu)的優(yōu)缺點？ 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. 孩子鏈存儲結(jié)構(gòu)孩子鏈存儲結(jié)構(gòu) 孩子鏈存儲結(jié)構(gòu)可按樹的度（即樹中所有節(jié)點度的最大值）孩子鏈存儲結(jié)構(gòu)可按樹的度（即樹中所有節(jié)點度的最大值）設(shè)計節(jié)點的孩子節(jié)點指針域個數(shù)。以下左圖的樹對應(yīng)的孩子鏈設(shè)計節(jié)點的孩子節(jié)點指針域個數(shù)。以下左圖的樹對應(yīng)的孩子鏈存儲結(jié)構(gòu)如右圖所示。存儲結(jié)構(gòu)如右圖所示。樹的樹的孩子鏈孩子鏈存儲結(jié)構(gòu)示意圖存儲結(jié)構(gòu)示意圖孩子鏈存儲結(jié)構(gòu)的節(jié)點類型聲明如下：孩子鏈存儲結(jié)構(gòu)的節(jié)點類型聲明如下：typedef struct node ElemType data; /節(jié)點的值節(jié)點的值 struct node *sonsMaxSons;/指向孩

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

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

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

26、子節(jié)點和右孩所有分支節(jié)點都有左孩子節(jié)點和右孩子節(jié)點，子節(jié)點，并且并且葉節(jié)點都集中在二叉樹的最下一層，葉節(jié)點都集中在二叉樹的最下一層，這樣的二叉這樣的二叉樹稱為樹稱為滿二叉樹滿二叉樹。下圖所示就是一棵滿二叉樹。可以對滿二叉樹的節(jié)點進行下圖所示就是一棵滿二叉樹。可以對滿二叉樹的節(jié)點進行連續(xù)編號，約定編號從樹根為連續(xù)編號，約定編號從樹根為1開始，按照層數(shù)從小到大、同開始，按照層數(shù)從小到大、同一層從左到右的次序進行。圖中每個節(jié)點外邊的數(shù)字為對該節(jié)一層從左到右的次序進行。圖中每個節(jié)點外邊的數(shù)字為對該節(jié)點的編號。點的編號。 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 滿二叉樹滿二叉樹 若二叉樹中最多若二叉樹中最多只有最下面兩層的節(jié)點的度數(shù)可以小于只有最下面兩層的節(jié)點的度數(shù)可以小于2，并且并且最下面一層的葉節(jié)點都依次排列在該層最左邊的位置上，最下面一層的葉節(jié)點都依次排列在該層最左邊的位置上，則這樣的二叉樹稱為則這樣的二叉樹稱為完全二叉樹完全二叉樹。如下圖所示為一棵完全二叉樹。同樣可以對完全二叉樹中每如下圖所示為一棵完全二叉樹。同樣可以對完全二叉樹中每個節(jié)點進行連續(xù)編號，編號的方法同滿二叉樹相同。圖中每個個節(jié)點進行連續(xù)編號，編號的方法同滿二叉樹相同。圖中每個節(jié)點外邊的數(shù)字為對該節(jié)點的編號。節(jié)點外邊的數(shù)字為對該節(jié)

28、點的編號。 A B C D E H I J K F G 1 2 3 4 5 6 7 8 9 10 11 完全二叉樹完全二叉樹 7.2.2 二叉樹性質(zhì)二叉樹性質(zhì) 性質(zhì)性質(zhì)1 非空二叉樹上葉節(jié)點數(shù)等于雙分支節(jié)點數(shù)加非空二叉樹上葉節(jié)點數(shù)等于雙分支節(jié)點數(shù)加1。 證明：證明：設(shè)二叉樹上葉節(jié)點數(shù)為設(shè)二叉樹上葉節(jié)點數(shù)為n0，單分支節(jié)點數(shù)為，單分支節(jié)點數(shù)為n1，雙分，雙分支節(jié)點數(shù)為支節(jié)點數(shù)為n2，則總節(jié)點數(shù)，則總節(jié)點數(shù)n=n0+n1+n2。在一棵二叉樹中，所。在一棵二叉樹中，所有節(jié)點的分支數(shù)（即度數(shù)）應(yīng)等于單分支節(jié)點數(shù)加上雙分支節(jié)有節(jié)點的分支數(shù)（即度數(shù)）應(yīng)等于單分支節(jié)點數(shù)加上雙分支節(jié)點數(shù)的點數(shù)的2倍，即總的分

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

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

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

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

33、 n/2 ，即即2in，則編號為，則編號為i的節(jié)點為分支節(jié)點，的節(jié)點為分支節(jié)點，否則為葉子節(jié)點。否則為葉子節(jié)點。 （2）若）若n為奇數(shù)，則每個分支節(jié)點都既有左孩子節(jié)點，為奇數(shù)，則每個分支節(jié)點都既有左孩子節(jié)點，也有右孩子節(jié)點；若也有右孩子節(jié)點；若n為偶數(shù)，則編號最大的分支節(jié)點只有為偶數(shù)，則編號最大的分支節(jié)點只有左孩子節(jié)點，沒有右孩子節(jié)點，其余分支節(jié)點都有左、右孩左孩子節(jié)點，沒有右孩子節(jié)點，其余分支節(jié)點都有左、右孩子節(jié)點。子節(jié)點。i/2i2i2i+1 （3）若編號為）若編號為i的節(jié)點有左孩子節(jié)點，則左孩子節(jié)點的編的節(jié)點有左孩子節(jié)點，則左孩子節(jié)點的編號為號為2i；若編號為；若編號為i的節(jié)點有右孩子節(jié)

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

35、完全二叉樹的高度為 log2n+1 或或 log2n +1。 由完全二叉樹的定義和樹的性質(zhì)由完全二叉樹的定義和樹的性質(zhì)3可推出。可推出。7.2.3 二叉樹與樹、森林之間的轉(zhuǎn)換二叉樹與樹、森林之間的轉(zhuǎn)換1森林、樹轉(zhuǎn)換為二叉樹森林、樹轉(zhuǎn)換為二叉樹 步驟如下：步驟如下： （1）在所有相鄰兄弟節(jié)點（森林中每棵樹的根節(jié)點可看）在所有相鄰兄弟節(jié)點（森林中每棵樹的根節(jié)點可看成是兄弟節(jié)點）之間加一水平連線。成是兄弟節(jié)點）之間加一水平連線。 （2）對每個非葉節(jié)點）對每個非葉節(jié)點k,除了其最左邊的孩子節(jié)點外，刪去除了其最左邊的孩子節(jié)點外，刪去k與其他孩子節(jié)點的連線。與其他孩子節(jié)點的連線。 （3）所有水平線段以左邊

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

37、叉樹中任一節(jié)點k0，沿著，沿著k0的左孩子的左孩子節(jié)點節(jié)點k1的右子樹方向搜索所有右孩子節(jié)點，即搜索節(jié)點序的右子樹方向搜索所有右孩子節(jié)點，即搜索節(jié)點序列列k2,k3,km，其中，其中ki+1為為ki的右孩子節(jié)點（的右孩子節(jié)點（1im），），km沒有右孩子節(jié)點。沒有右孩子節(jié)點。 （2）刪去）刪去k1,k2,km之間連線。之間連線。 （3）若）若k1有雙親節(jié)點有雙親節(jié)點k0，則連接，則連接k0與與ki（2im）。）。 （4）將圖形規(guī)整化，使各節(jié)點按層次排列）將圖形規(guī)整化，使各節(jié)點按層次排列。 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) 將一棵二叉樹還原為樹的過程將一棵二叉樹還原為樹的過程 例例7.3 設(shè)森林設(shè)森林F中有中有3棵樹，第一、第二和第三棵樹的節(jié)棵樹，第一、第二和第三棵樹的節(jié)點個數(shù)分別為點個數(shù)分別為9、8和和7，則與森林，則與森林F對應(yīng)的二叉樹根節(jié)點的右對應(yīng)的二叉樹根節(jié)點的右子樹上的節(jié)點個數(shù)是子樹上的節(jié)點個數(shù)是 。A. 16B. 15C. 7D. 17 例例7.4 設(shè)一棵二叉樹是由森林轉(zhuǎn)換而來的，若森林中有設(shè)一棵二叉樹是由森林轉(zhuǎn)換而來的，若森林中有n個非終端節(jié)點，則二叉樹中無右孩子的節(jié)點個數(shù)為個非終端節(jié)點，則二叉樹中無右孩子的節(jié)點個數(shù)為 。 A. n-1B. n C. n+1D. n+2設(shè)計題：設(shè)計題：

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

40、C+語言中數(shù)組的起始下標(biāo)為語言中數(shù)組的起始下標(biāo)為0）。樹中各節(jié)）。樹中各節(jié)點的編號與等高度的完全二叉樹中對應(yīng)位置上節(jié)點的編號點的編號與等高度的完全二叉樹中對應(yīng)位置上節(jié)點的編號相同。相同。 利用二叉樹的性質(zhì)利用二叉樹的性質(zhì)4。7.3 二叉樹存儲結(jié)構(gòu)二叉樹存儲結(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 完全二叉樹完全二叉樹 ABCDEFGHIJK123456789101112131415順序存儲結(jié)構(gòu)（不用下標(biāo)為順序存儲結(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一般的二叉樹先用空節(jié)點一般的二叉樹先用空節(jié)點補全成為完全二叉樹，然補全成為完全二叉樹，然后對節(jié)點編號后對節(jié)點編號typedef ElemType SqBTreeMaxSize;SqBTree bt=#ABD#C#E#F;7.3.2 二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu) 在二叉樹的鏈接存儲中，節(jié)點的結(jié)構(gòu)如下在二叉樹的鏈接存儲中，節(jié)點的結(jié)構(gòu)如下: typedef struct node ElemType data; struct node *lchild,*rchild; BTNode; 其中其中,data表示值域表示值域,用于存儲對應(yīng)的數(shù)

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

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

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

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

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

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

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

49、 b; else p=FindNode(b-lchild,x); if (p!=NULL) return p; else return FindNode(b-rchild,x); （3）找孩子節(jié)點）找孩子節(jié)點LchildNode(p)和和RchildNode(p) 直接返回直接返回*p節(jié)點的左孩子節(jié)點或右孩子節(jié)點的指針。算節(jié)點的左孩子節(jié)點或右孩子節(jié)點的指針。算法如下：法如下： BTNode *LchildNode(BTNode *p) return p-lchild; BTNode *RchildNode(BTNode *p) return p-rchild; （4）求高度）求高度BTNode

50、Depth(*b) 求二叉樹的高度的遞歸模型求二叉樹的高度的遞歸模型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); /空樹的高度為空樹的高度為0 else lchilddep=BTNodeDepth(b-lchild);/求左子樹的高度為求左子樹的高度為lchilddep rchilddep=BTNodeDepth(b-rchild);/求右子樹的高度為求

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

52、BTNode *b) if (b!=NULL) printf(%c,b-data); if (b-lchild!=NULL | b-rchild!=NULL) printf(); DispBTNode(b-lchild); /遞歸處理左子樹遞歸處理左子樹 if (b-rchild!=NULL) printf(,); DispBTNode(b-rchild);/遞歸處理右子樹遞歸處理右子樹 printf(); 7.5.1 二叉樹遍歷的概念二叉樹遍歷的概念 二叉樹的遍歷是指按照一定次序訪問樹中所有節(jié)點，并二叉樹的遍歷是指按照一定次序訪問樹中所有節(jié)點，并且且每個節(jié)點僅被訪問一次每個節(jié)點僅被訪問一次的

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

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

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

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

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

58、節(jié)點個數(shù)的遞歸模型f(b)如下：如下：f(b)=0若若b=NULLf(b)=f(b- -lchild)+f(b- -rchild)+1其他情況其他情況bb- -lchildb- -rchild對應(yīng)的遞歸算法如下：對應(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è)二叉樹采用二叉鏈存儲結(jié)構(gòu)存儲，試設(shè)計一個假設(shè)二叉樹采用二叉鏈存儲結(jié)構(gòu)存儲，試設(shè)計

59、一個算法，計算一棵給定二叉樹的所有葉子節(jié)點個數(shù)。算法，計算一棵給定二叉樹的所有葉子節(jié)點個數(shù)。 解：解：計算一棵二叉樹計算一棵二叉樹b中所有葉子節(jié)點個數(shù)的遞歸模型中所有葉子節(jié)點個數(shù)的遞歸模型f(b)如下：如下：f(b)=0若若b=NULLf(b)=1若若*b為葉子節(jié)點為葉子節(jié)點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 nu

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