數(shù)據(jù)結(jié)構(gòu)[嚴(yán)蔚敏]_樹和二叉樹

1、 樹型結(jié)構(gòu)是一類非常重要的非線性結(jié)構(gòu)。直觀地，樹型結(jié)構(gòu)是一類非常重要的非線性結(jié)構(gòu)。直觀地，樹型結(jié)構(gòu)是樹型結(jié)構(gòu)是以分支關(guān)系定義的層次結(jié)構(gòu)以分支關(guān)系定義的層次結(jié)構(gòu)。 樹在計算機(jī)領(lǐng)域中也有著廣泛的應(yīng)用，例如在編譯樹在計算機(jī)領(lǐng)域中也有著廣泛的應(yīng)用，例如在編譯程序中，用樹來表示源程序的語法結(jié)構(gòu)；在數(shù)據(jù)庫系統(tǒng)程序中，用樹來表示源程序的語法結(jié)構(gòu)；在數(shù)據(jù)庫系統(tǒng)中，可用樹來組織信息；在分析算法的行為時，可用樹中，可用樹來組織信息；在分析算法的行為時，可用樹來描述其執(zhí)行過程等等。來描述其執(zhí)行過程等等。 本章將詳細(xì)討論樹和二叉樹數(shù)據(jù)結(jié)構(gòu)，主要介紹樹本章將詳細(xì)討論樹和二叉樹數(shù)據(jù)結(jié)構(gòu)，主要介紹樹和二叉樹的概念、術(shù)語，二

2、叉樹的遍歷算法。樹和二叉和二叉樹的概念、術(shù)語，二叉樹的遍歷算法。樹和二叉樹的各種存儲結(jié)構(gòu)以及建立在各種存儲結(jié)構(gòu)上的操作及樹的各種存儲結(jié)構(gòu)以及建立在各種存儲結(jié)構(gòu)上的操作及應(yīng)用等。應(yīng)用等。1 樹的定義樹的定義 樹樹(Tree)是是n(n0)個結(jié)點(diǎn)的有限集合個結(jié)點(diǎn)的有限集合T，若，若n=0時稱時稱為空樹，否則：為空樹，否則： 有且只有一個特殊的稱為樹的有且只有一個特殊的稱為樹的根根(Root)結(jié)點(diǎn)；結(jié)點(diǎn)； 若若n1時，其余的結(jié)點(diǎn)被分為時，其余的結(jié)點(diǎn)被分為m(m0)個個互不相交互不相交的子集的子集T1, T2, T3Tm，其中每個子集本身又是一棵，其中每個子集本身又是一棵樹，稱其為根的樹，稱其為根的子

3、樹子樹(Subtree)。 這是樹的遞歸定義，即用樹來定義樹，而只有一個這是樹的遞歸定義，即用樹來定義樹，而只有一個結(jié)點(diǎn)的樹必定僅由根組成，如圖結(jié)點(diǎn)的樹必定僅由根組成，如圖6-1(a)所示。所示。 6.1.1樹的定義和基本術(shù)語樹的定義和基本術(shù)語2 樹的基本術(shù)語樹的基本術(shù)語 結(jié)點(diǎn)結(jié)點(diǎn)(node)：一個數(shù)據(jù)元素及其若干指向其子一個數(shù)據(jù)元素及其若干指向其子樹的分支。樹的分支。 結(jié)點(diǎn)的度結(jié)點(diǎn)的度(degree) 、樹的度樹的度：結(jié)點(diǎn)所擁有的結(jié)點(diǎn)所擁有的子樹的棵數(shù)稱為子樹的棵數(shù)稱為結(jié)點(diǎn)的度結(jié)點(diǎn)的度。樹中結(jié)點(diǎn)度的最大值稱為。樹中結(jié)點(diǎn)度的最大值稱為樹的度樹的度。 圖圖6-1 樹的示樹的示例形式例形式AABD

4、CEGFHIMJNKL(a) 只有根結(jié)點(diǎn)只有根結(jié)點(diǎn)(b) 一般的樹一般的樹 如圖如圖6-1(b)中結(jié)點(diǎn)中結(jié)點(diǎn)A的度是的度是3 ，結(jié)點(diǎn)，結(jié)點(diǎn)B的度是的度是2 ，結(jié)點(diǎn)，結(jié)點(diǎn)M的度是的度是0，樹的度是，樹的度是3 。 葉子葉子(leaf)結(jié)點(diǎn)結(jié)點(diǎn)、非葉子結(jié)點(diǎn)非葉子結(jié)點(diǎn)：樹中樹中度為度為0的的結(jié)點(diǎn)稱為結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)葉子結(jié)點(diǎn)( (或終端結(jié)點(diǎn)或終端結(jié)點(diǎn)) )。相對應(yīng)地，。相對應(yīng)地，度不為度不為0的的結(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)又稱為內(nèi)部結(jié)點(diǎn)。除根結(jié)點(diǎn)外，分支結(jié)點(diǎn)又稱為內(nèi)部結(jié)點(diǎn)。 如圖如圖6-1(b)中結(jié)點(diǎn)中結(jié)點(diǎn)H、I、J、

5、K、L、M、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)的孩子結(jié)點(diǎn)(child)或子結(jié)點(diǎn)或子結(jié)點(diǎn)；相應(yīng)地，該結(jié)點(diǎn)是其孩子結(jié)點(diǎn)的雙親結(jié)點(diǎn)相應(yīng)地，該結(jié)點(diǎn)是其孩子結(jié)點(diǎn)的雙親結(jié)點(diǎn)(parent)或父結(jié)點(diǎn)?；蚋附Y(jié)點(diǎn)。 如圖如圖6-1(b)中結(jié)點(diǎn)中結(jié)點(diǎn)B 、C、D是結(jié)點(diǎn)是結(jié)點(diǎn)A的子結(jié)點(diǎn)的子結(jié)點(diǎn)，而，而結(jié)點(diǎn)結(jié)點(diǎn)A是是結(jié)點(diǎn)結(jié)點(diǎn)B 、C、D的的父結(jié)點(diǎn)父結(jié)點(diǎn)；類似地結(jié)點(diǎn)類似地結(jié)點(diǎn)E 、F是是結(jié)點(diǎn)結(jié)點(diǎn)B的子結(jié)點(diǎn)的子結(jié)點(diǎn)，結(jié)點(diǎn)，結(jié)點(diǎn)B是是結(jié)點(diǎn)結(jié)點(diǎn)E 、F的的父

6、結(jié)點(diǎn)。父結(jié)點(diǎn)。同一雙親結(jié)點(diǎn)的所有子結(jié)點(diǎn)互稱為同一雙親結(jié)點(diǎn)的所有子結(jié)點(diǎn)互稱為兄弟結(jié)點(diǎn)兄弟結(jié)點(diǎn)。 如圖如圖6-1(b)中結(jié)點(diǎn)中結(jié)點(diǎn)B 、C、D是兄弟結(jié)點(diǎn)；結(jié)點(diǎn)是兄弟結(jié)點(diǎn)；結(jié)點(diǎn)E 、F是兄弟結(jié)點(diǎn)。是兄弟結(jié)點(diǎn)。 結(jié)點(diǎn)的層次結(jié)點(diǎn)的層次、堂兄弟結(jié)點(diǎn)堂兄弟結(jié)點(diǎn) 規(guī)定樹中根結(jié)點(diǎn)的層次為規(guī)定樹中根結(jié)點(diǎn)的層次為1，其余結(jié)點(diǎn)的層次等于，其余結(jié)點(diǎn)的層次等于其雙親結(jié)點(diǎn)的層次加其雙親結(jié)點(diǎn)的層次加1。 若某結(jié)點(diǎn)在第若某結(jié)點(diǎn)在第l(l1)層，則其子結(jié)點(diǎn)在第層，則其子結(jié)點(diǎn)在第l+1層。層。 雙親結(jié)點(diǎn)在同一層上的所有結(jié)點(diǎn)互稱為雙親結(jié)點(diǎn)在同一層上的所有結(jié)點(diǎn)互稱為堂兄弟結(jié)點(diǎn)堂兄弟結(jié)點(diǎn)。 結(jié)點(diǎn)的層次路徑結(jié)點(diǎn)的層次路徑、祖先祖先、子孫子

7、孫 從根結(jié)點(diǎn)開始，到達(dá)某結(jié)點(diǎn)從根結(jié)點(diǎn)開始，到達(dá)某結(jié)點(diǎn)p所經(jīng)過的所有結(jié)點(diǎn)稱所經(jīng)過的所有結(jié)點(diǎn)稱為為結(jié)點(diǎn)結(jié)點(diǎn)p的的層次路徑層次路徑( (有且只有一條有且只有一條) )。 結(jié)點(diǎn)結(jié)點(diǎn)p的層次路徑上的所有結(jié)點(diǎn)（的層次路徑上的所有結(jié)點(diǎn)（p除外）稱為除外）稱為p的的祖先祖先(ancester) 。 以某一結(jié)點(diǎn)為根的子樹中的任意結(jié)點(diǎn)稱為該結(jié)點(diǎn)的以某一結(jié)點(diǎn)為根的子樹中的任意結(jié)點(diǎn)稱為該結(jié)點(diǎn)的子孫結(jié)點(diǎn)子孫結(jié)點(diǎn)(descent)。 樹的深度樹的深度(depth)：樹中結(jié)點(diǎn)的最大層次值，又樹中結(jié)點(diǎn)的最大層次值，又稱為樹的高度，如圖稱為樹的高度，如圖6-1(b)中樹的高度為中樹的高度為4。 有序樹和無序樹有序樹和無序樹：對

8、于一棵樹，若其中每一個對于一棵樹，若其中每一個結(jié)點(diǎn)的子樹（若有）具有一定的次序，則該樹稱為結(jié)點(diǎn)的子樹（若有）具有一定的次序，則該樹稱為有有序樹序樹，否則稱為，否則稱為無序樹無序樹。 森林森林(forest)：是是m(m0)棵互不相交的棵互不相交的樹的集樹的集合。顯然，若將一棵樹的根結(jié)點(diǎn)刪除，剩余的子樹就合。顯然，若將一棵樹的根結(jié)點(diǎn)刪除，剩余的子樹就構(gòu)成了森林。構(gòu)成了森林。3 樹的表示形式樹的表示形式 倒懸樹倒懸樹。是最常用的表示形式，如圖是最常用的表示形式，如圖6-1(b)。 嵌套集合嵌套集合。是一些集合的集體，對于任何兩個是一些集合的集體，對于任何兩個集合，或者不相交，或者一個集合包含另一個

9、集合。集合，或者不相交，或者一個集合包含另一個集合。圖圖6-2(a)是圖是圖6-1(b)樹的嵌套集合形式。樹的嵌套集合形式。 廣義表形式廣義表形式。圖圖6-2(b)是樹的廣義表形式。是樹的廣義表形式。 凹入法表示形式凹入法表示形式。見見P120 樹的表示方法的多樣化說明了樹結(jié)構(gòu)的重要性。樹的表示方法的多樣化說明了樹結(jié)構(gòu)的重要性。圖圖6-2 樹的表示樹的表示形式形式(a)嵌套集合嵌套集合形式形式(b) 廣義表廣義表形式形式(A(B(E(K,L),F),C(G(M,N),D(H,I,J)HIJDFBKLECM NGAADT Tree數(shù)據(jù)對象數(shù)據(jù)對象D：D是具有相同數(shù)據(jù)類型的數(shù)據(jù)元素的集是具有相同數(shù)

10、據(jù)類型的數(shù)據(jù)元素的集合合。數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系R：若：若D為空集為空集，則稱為空樹則稱為空樹； 基本操作：基本操作： ADT Tree 詳見詳見p118119。6.2.1 二叉樹的定義二叉樹的定義1 二叉樹的定義二叉樹的定義 二叉樹二叉樹(Binary tree)是是n(n0)個結(jié)點(diǎn)的有限集合。個結(jié)點(diǎn)的有限集合。若若n=0時稱為空樹，否則：時稱為空樹，否則： 有且只有一個特殊的稱為樹的根有且只有一個特殊的稱為樹的根(Root)結(jié)點(diǎn)；結(jié)點(diǎn)； 若若n1時，其余的結(jié)點(diǎn)被分成為時，其余的結(jié)點(diǎn)被分成為二個互不相交二個互不相交的子的子集集T1,T2，分別稱之為左，分別稱之為左、右子樹，并且左右子樹，并且左、右

11、子樹右子樹又都是二叉樹。又都是二叉樹。 由此可知，二叉樹的由此可知，二叉樹的定義是遞歸定義是遞歸的。的。 二叉樹在樹結(jié)構(gòu)中起著非常重要的作用。因為二叉二叉樹在樹結(jié)構(gòu)中起著非常重要的作用。因為二叉樹結(jié)構(gòu)簡單，存儲效率高，樹的操作算法相對簡單，且樹結(jié)構(gòu)簡單，存儲效率高，樹的操作算法相對簡單，且任何樹都很容易轉(zhuǎn)化成二叉樹結(jié)構(gòu)。上節(jié)中引入的有關(guān)任何樹都很容易轉(zhuǎn)化成二叉樹結(jié)構(gòu)。上節(jié)中引入的有關(guān)樹的術(shù)語也都適用于二叉樹。樹的術(shù)語也都適用于二叉樹。2 二叉樹的基本形態(tài)二叉樹的基本形態(tài) 二叉樹有二叉樹有5種基本形態(tài)，如圖種基本形態(tài)，如圖6-3所示。所示。AAAA(a)(b)(c)(d)(e)(a) 空空二叉樹

12、二叉樹(b) 單結(jié)點(diǎn)單結(jié)點(diǎn)二叉樹二叉樹(c) 右子樹為空右子樹為空(d) 左子樹為空左子樹為空(e) 左左、右子樹都不空右子樹都不空圖圖6-3 二叉二叉樹的基本樹的基本形態(tài)形態(tài)性質(zhì)性質(zhì)1：在非空二叉樹中，第在非空二叉樹中，第i i層上至多有層上至多有2i-1個結(jié)點(diǎn)個結(jié)點(diǎn)(i1)。證明證明：用數(shù)學(xué)歸納法證明。用數(shù)學(xué)歸納法證明。 當(dāng)當(dāng)i=1時：只有一個根結(jié)點(diǎn)，時：只有一個根結(jié)點(diǎn)，21-1=20 =1，命題成立。，命題成立。 現(xiàn)假設(shè)對現(xiàn)假設(shè)對i1時，處在第時，處在第i-1層上至多有層上至多有2(i-1)-1個結(jié)點(diǎn)。個結(jié)點(diǎn)。 由歸納假設(shè)知，第由歸納假設(shè)知，第i-1層上至多有層上至多有2i-2個結(jié)點(diǎn)。由

13、于二個結(jié)點(diǎn)。由于二叉樹每個結(jié)點(diǎn)的度最大為叉樹每個結(jié)點(diǎn)的度最大為2，故在第，故在第i i層上最大結(jié)點(diǎn)數(shù)為層上最大結(jié)點(diǎn)數(shù)為第第i-1層上最大結(jié)點(diǎn)數(shù)的層上最大結(jié)點(diǎn)數(shù)的2倍。倍。 即即 22i-22i-1 證畢證畢證明證明：深度為深度為k的二叉樹的最大的結(jié)點(diǎn)數(shù)為二叉樹中每的二叉樹的最大的結(jié)點(diǎn)數(shù)為二叉樹中每層上的最大結(jié)點(diǎn)數(shù)之和。層上的最大結(jié)點(diǎn)數(shù)之和。 由性質(zhì)由性質(zhì)1知知，二叉樹的第，二叉樹的第1層層、第第2層層 第第k層上的結(jié)層上的結(jié)點(diǎn)數(shù)至多有：點(diǎn)數(shù)至多有： 20、21 2k-1 。 總的總的結(jié)點(diǎn)數(shù)至多有：結(jié)點(diǎn)數(shù)至多有： 20+21+ + +2k-1=2k-1 證畢證畢 性質(zhì)性質(zhì)3：對任何一棵二叉樹，若

14、其葉子結(jié)點(diǎn)數(shù)為對任何一棵二叉樹，若其葉子結(jié)點(diǎn)數(shù)為n0，度為度為2的結(jié)點(diǎn)數(shù)為的結(jié)點(diǎn)數(shù)為n2，則，則n0=n2+1。證明：證明：設(shè)二叉樹中度為設(shè)二叉樹中度為1的結(jié)點(diǎn)數(shù)為的結(jié)點(diǎn)數(shù)為n1，二叉樹中總結(jié)，二叉樹中總結(jié)點(diǎn)數(shù)為點(diǎn)數(shù)為N，因為二叉樹中所有結(jié)點(diǎn)度均小于或等于，因為二叉樹中所有結(jié)點(diǎn)度均小于或等于2，則有：則有：N=n0+n1+n2再看二叉樹中的分支數(shù)：再看二叉樹中的分支數(shù)：性質(zhì)性質(zhì)2：深度為深度為k的二叉樹至多有的二叉樹至多有2k-1個結(jié)點(diǎn)個結(jié)點(diǎn)（k1) 。 除根結(jié)點(diǎn)外，其余每個結(jié)點(diǎn)都有唯一的一個進(jìn)入分除根結(jié)點(diǎn)外，其余每個結(jié)點(diǎn)都有唯一的一個進(jìn)入分支，而所有這些分支都是由度為支，而所有這些分支都是由

15、度為1和和2的結(jié)點(diǎn)射出的。設(shè)的結(jié)點(diǎn)射出的。設(shè)B為二叉樹中的分支總數(shù)，則有：為二叉樹中的分支總數(shù)，則有： N=B+1 Bn1+2 n2 N=B+1=n1+2 n2+1 n0+n1+n2=n1+2 n2+1 即即 n0=n2+1 證畢證畢滿二叉樹和完全二叉樹滿二叉樹和完全二叉樹 一棵深度為一棵深度為k且有且有2k-1個結(jié)點(diǎn)的二叉樹稱為個結(jié)點(diǎn)的二叉樹稱為滿二叉滿二叉樹樹(Full Binary Tree)。 如圖如圖6-4(a) 就是一棵深度為就是一棵深度為4的滿二叉樹。的滿二叉樹。894101151213614157213894101152112673(a) 滿二叉樹滿二叉樹(b) 完全二叉樹完全

16、二叉樹1362455674213(c) 非完全二叉樹非完全二叉樹圖圖6-4 特殊形態(tài)的特殊形態(tài)的二叉二叉樹樹滿二叉樹的特點(diǎn)滿二叉樹的特點(diǎn)： 基本特點(diǎn)是每一層上的結(jié)點(diǎn)數(shù)總是最大結(jié)點(diǎn)數(shù)?；咎攸c(diǎn)是每一層上的結(jié)點(diǎn)數(shù)總是最大結(jié)點(diǎn)數(shù)。 滿二叉樹的所有的分支結(jié)點(diǎn)都有左滿二叉樹的所有的分支結(jié)點(diǎn)都有左、右子樹。右子樹。 可對滿二叉樹的結(jié)點(diǎn)進(jìn)行連續(xù)編號，若規(guī)定從根可對滿二叉樹的結(jié)點(diǎn)進(jìn)行連續(xù)編號，若規(guī)定從根結(jié)點(diǎn)開始，按結(jié)點(diǎn)開始，按“自上而下自上而下、自左至右自左至右”的原則進(jìn)行。的原則進(jìn)行。完全二叉樹完全二叉樹( (Complete Binary Tree) )：如果深度為：如果深度為k，有，有n個結(jié)點(diǎn)的二叉樹，

17、當(dāng)且僅當(dāng)其每一個結(jié)點(diǎn)都與深度為個結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)點(diǎn)都與深度為k的滿二叉樹中編號從的滿二叉樹中編號從1到到n的結(jié)點(diǎn)一一對應(yīng)，該二叉樹稱的結(jié)點(diǎn)一一對應(yīng)，該二叉樹稱為完全二叉樹。為完全二叉樹。 或深度為或深度為k的滿二叉樹中編號從的滿二叉樹中編號從1到到n的前的前n個結(jié)點(diǎn)構(gòu)個結(jié)點(diǎn)構(gòu)成了一棵深度為成了一棵深度為k的完全二叉樹。的完全二叉樹。其中其中 2k-1 n2k-1 。 完全二叉樹是滿二叉樹的一部分，而滿二叉樹是完完全二叉樹是滿二叉樹的一部分，而滿二叉樹是完全二叉樹的特例。全二叉樹的特例。完全二叉樹的特點(diǎn)完全二叉樹的特點(diǎn)： 若完全二叉樹的深度為若完全二叉樹的深度為k ，則所有的葉子

18、結(jié)點(diǎn)都出現(xiàn)，則所有的葉子結(jié)點(diǎn)都出現(xiàn)在第在第k k層或?qū)踊騥-1層。對于任一結(jié)點(diǎn)，如果其右子樹的最大層。對于任一結(jié)點(diǎn)，如果其右子樹的最大層次為層次為l，則其左子樹的最大層次為，則其左子樹的最大層次為l或或l+1 1。性質(zhì)性質(zhì)4：n個結(jié)點(diǎn)的完全二叉樹深度為：個結(jié)點(diǎn)的完全二叉樹深度為： 2n + +1 1。 其中符號：其中符號： x 表示不大于表示不大于x的最大整數(shù)。的最大整數(shù)。 x 表示不小于表示不小于x的最小整數(shù)。的最小整數(shù)。證明：證明：假設(shè)完全二叉樹的深度為假設(shè)完全二叉樹的深度為k，則根據(jù)性質(zhì)，則根據(jù)性質(zhì)2及完及完全二叉樹的定義有：全二叉樹的定義有：2k-1-1n2k-1 或或 2 k-1n2

19、k 取對數(shù)得：取對數(shù)得：k-12n1，則其雙親結(jié)點(diǎn)編號是，則其雙親結(jié)點(diǎn)編號是 i/2 。 如果如果2in：則結(jié)點(diǎn)：則結(jié)點(diǎn)i為葉子結(jié)點(diǎn)，無左孩子；否則，為葉子結(jié)點(diǎn)，無左孩子；否則，其左孩子結(jié)點(diǎn)編號是其左孩子結(jié)點(diǎn)編號是2i。 如果如果2i+1n：則結(jié)點(diǎn)：則結(jié)點(diǎn)i無右孩子；否則，其右孩無右孩子；否則，其右孩子結(jié)點(diǎn)編號是子結(jié)點(diǎn)編號是2i+1。 證明證明：用數(shù)學(xué)歸納法證明。首先證明和，然后用數(shù)學(xué)歸納法證明。首先證明和，然后由和導(dǎo)出。由和導(dǎo)出。 當(dāng)當(dāng)i=1時時，由完全二叉樹的定義知，結(jié)點(diǎn)，由完全二叉樹的定義知，結(jié)點(diǎn)i的左孩子的左孩子的編號是的編號是2，右孩子的編號是，右孩子的編號是3。 若若2n，則二叉樹

20、中不存在編號為，則二叉樹中不存在編號為2的結(jié)點(diǎn)，說明的結(jié)點(diǎn)，說明結(jié)點(diǎn)結(jié)點(diǎn)i的左的左孩子孩子不存在。不存在。 若若3n，則二叉樹中不存在編號為，則二叉樹中不存在編號為3的結(jié)點(diǎn)，說明的結(jié)點(diǎn)，說明結(jié)點(diǎn)結(jié)點(diǎn)i的右的右孩子孩子不存在。不存在。 現(xiàn)假設(shè)對于編號為現(xiàn)假設(shè)對于編號為j(1ji)的結(jié)點(diǎn)的結(jié)點(diǎn)，(2)(2)和和(3)(3)成立。成立。即：即： 當(dāng)當(dāng)2jn ：結(jié)點(diǎn)：結(jié)點(diǎn)j的左孩子編號是的左孩子編號是2j；當(dāng)；當(dāng)2jn時時，結(jié)點(diǎn)結(jié)點(diǎn)j的左孩子結(jié)點(diǎn)不存在。的左孩子結(jié)點(diǎn)不存在。 當(dāng)當(dāng)2j+1n ：結(jié)點(diǎn)：結(jié)點(diǎn)j的右孩子編號是的右孩子編號是2j+1；當(dāng)；當(dāng)2j+1n時，結(jié)點(diǎn)時，結(jié)點(diǎn)j的右孩子結(jié)點(diǎn)不存在。的右孩

21、子結(jié)點(diǎn)不存在。 當(dāng)當(dāng)i=j+1時，由完全二叉樹的定義知，若結(jié)點(diǎn)時，由完全二叉樹的定義知，若結(jié)點(diǎn)i的左的左孩子結(jié)點(diǎn)存在，則其左孩子結(jié)點(diǎn)的編號一定等于編號孩子結(jié)點(diǎn)存在，則其左孩子結(jié)點(diǎn)的編號一定等于編號為為j的右孩子的編號加的右孩子的編號加1，即結(jié)點(diǎn)，即結(jié)點(diǎn)i的左孩子的編號為：的左孩子的編號為： (2j+1)+1=2(j+1)=2i如圖如圖6-5所示，且有所示，且有2in。相反，若。相反，若2in，則左孩子結(jié)，則左孩子結(jié)點(diǎn)不存在。同樣地，若結(jié)點(diǎn)點(diǎn)不存在。同樣地，若結(jié)點(diǎn)i的右孩子結(jié)點(diǎn)存在，則其的右孩子結(jié)點(diǎn)存在，則其右孩子的編號為：右孩子的編號為：2i+1，且有，且有2i+1n。相反，若。相反，若2i+

22、1n，則左孩子結(jié)點(diǎn)不存在。結(jié)論，則左孩子結(jié)點(diǎn)不存在。結(jié)論(2)(2)和和(3)(3)得證。得證。 再由再由(2)(2)和和(3)(3)來證明來證明(1) 。 當(dāng)當(dāng)i=1時時，顯然編號為，顯然編號為1的的是根結(jié)點(diǎn)，無雙親結(jié)點(diǎn)。是根結(jié)點(diǎn)，無雙親結(jié)點(diǎn)。 當(dāng)當(dāng)i1時，設(shè)編號為時，設(shè)編號為i的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號為的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號為m，若編號為若編號為i的結(jié)點(diǎn)是其雙親結(jié)點(diǎn)的左孩子，則由的結(jié)點(diǎn)是其雙親結(jié)點(diǎn)的左孩子，則由(2)有：有：i=2m ，即，即m= i/2 ；若編號為若編號為i的結(jié)點(diǎn)是其的結(jié)點(diǎn)是其雙親結(jié)點(diǎn)的右孩子，則由雙親結(jié)點(diǎn)的右孩子，則由(3)有：有：i=2m+1 ，即，即m= (i-1)

23、/2 ； 當(dāng)當(dāng)i1時時，其雙親結(jié)點(diǎn)的編號為，其雙親結(jié)點(diǎn)的編號為 i/2 。 證畢證畢ii+12i2i+12i+22i+3i/2(a) i和和i+1結(jié)點(diǎn)在同一層結(jié)點(diǎn)在同一層i+12i+22i+3i2i2i+1(b) i和和i+1結(jié)點(diǎn)不在同一層結(jié)點(diǎn)不在同一層圖圖6-5 完全完全二叉二叉樹中結(jié)點(diǎn)樹中結(jié)點(diǎn)i和和i+1的左右孩子的左右孩子1 順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu) 二叉樹存儲結(jié)構(gòu)的類型定義：二叉樹存儲結(jié)構(gòu)的類型定義：#define MAX_SIZE 100 typedef telemtype sqbitreeMAX_SIZE; 用一組地址連續(xù)的存儲單元依次用一組地址連續(xù)的存儲單元依次“自上而下自上而下

24、、自左自左至右至右”存儲完全二叉樹的數(shù)據(jù)元素。存儲完全二叉樹的數(shù)據(jù)元素。 對于完全二叉樹上編號為對于完全二叉樹上編號為i的結(jié)點(diǎn)元素存儲在一維的結(jié)點(diǎn)元素存儲在一維數(shù)組的下標(biāo)值為數(shù)組的下標(biāo)值為i-1的分量中的分量中，如圖，如圖6-6(c)所示。所示。 對于一般的二叉樹，將其每個結(jié)點(diǎn)與完全二叉樹上對于一般的二叉樹，將其每個結(jié)點(diǎn)與完全二叉樹上的結(jié)點(diǎn)相對照，的結(jié)點(diǎn)相對照，存儲在一維數(shù)組中存儲在一維數(shù)組中，如圖，如圖6-6(d)所示。所示。abcdhiejklfg(a) 完全二叉樹完全二叉樹(b) 非完全二叉樹非完全二叉樹abcdefgh1 2 3 4 5 6 7 8 9 10 11 12 a b c d

25、 e f g h i j k l (c) 完全二叉樹的順序存儲形式完全二叉樹的順序存儲形式1 2 3 4 5 6 7 8 9 10 11a b c d e h f g(d) 非完全二叉樹的順序存儲形式非完全二叉樹的順序存儲形式圖圖6-6 二叉二叉樹及其樹及其順序存儲形式順序存儲形式 最壞的情況下，一個深度為最壞的情況下，一個深度為k且只有且只有k個結(jié)點(diǎn)的單支個結(jié)點(diǎn)的單支樹需要長度為樹需要長度為2k-1的一維數(shù)組的一維數(shù)組。2 鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu) 設(shè)計不同的結(jié)點(diǎn)結(jié)構(gòu)可構(gòu)成不同的鏈?zhǔn)酱鎯Y(jié)構(gòu)。設(shè)計不同的結(jié)點(diǎn)結(jié)構(gòu)可構(gòu)成不同的鏈?zhǔn)酱鎯Y(jié)構(gòu)。(1) 結(jié)點(diǎn)的類型及其定義結(jié)點(diǎn)的類型及其定義 二叉鏈表結(jié)

26、點(diǎn)二叉鏈表結(jié)點(diǎn)。有三個域：一個數(shù)據(jù)域，兩個分。有三個域：一個數(shù)據(jù)域，兩個分別指向左右子結(jié)點(diǎn)的指針域，如圖別指向左右子結(jié)點(diǎn)的指針域，如圖6-7(a)所示。所示。 typedef struct BiTNode TElemType data ;struct BiTNode *lchild , *rchild ;BiTNode, *BiTree ; 三三叉鏈表結(jié)點(diǎn)叉鏈表結(jié)點(diǎn)。除二叉鏈表的三個域外，再增加一。除二叉鏈表的三個域外，再增加一個指針域，用來指向結(jié)點(diǎn)的父結(jié)點(diǎn)，如圖個指針域，用來指向結(jié)點(diǎn)的父結(jié)點(diǎn)，如圖6-7(b)所示。所示。lchild data rchildlchild data parent

27、 rchild(a) 二叉鏈表結(jié)點(diǎn)二叉鏈表結(jié)點(diǎn)(b) 三三叉鏈表結(jié)點(diǎn)叉鏈表結(jié)點(diǎn)圖圖6-7 鏈表結(jié)點(diǎn)結(jié)構(gòu)鏈表結(jié)點(diǎn)結(jié)構(gòu)形式形式(2) 二叉樹的鏈?zhǔn)酱鎯π问蕉鏄涞逆準(zhǔn)酱鎯π问?例有一棵一般的二叉樹，如圖例有一棵一般的二叉樹，如圖6-8(a)所示。以二叉所示。以二叉鏈表和三叉鏈表方式存儲的結(jié)構(gòu)圖分別如圖鏈表和三叉鏈表方式存儲的結(jié)構(gòu)圖分別如圖6-8(b) 、 6-8(c)所示。所示。圖圖6-8 二叉樹及其二叉樹及其鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)(a) 二叉樹二叉樹afedcbg(c) 三三叉鏈表叉鏈表 a b c d e f g T(b) 二二叉鏈表叉鏈表 a b c d e g f T遍歷二叉樹遍歷二叉樹

28、(Traversing Binary Tree)：是指是指按指定按指定的規(guī)律的規(guī)律對二叉樹中的對二叉樹中的每個結(jié)點(diǎn)訪問一次且僅訪問一次每個結(jié)點(diǎn)訪問一次且僅訪問一次。 所謂所謂訪問訪問是指對結(jié)點(diǎn)做某種處理。如：輸出信息是指對結(jié)點(diǎn)做某種處理。如：輸出信息、修改結(jié)點(diǎn)的值等修改結(jié)點(diǎn)的值等。 二叉樹是一種非線性結(jié)構(gòu)，每個結(jié)點(diǎn)都可能有左二叉樹是一種非線性結(jié)構(gòu)，每個結(jié)點(diǎn)都可能有左、右兩棵子樹，因此，需要尋找一種規(guī)律，使二叉樹上的右兩棵子樹，因此，需要尋找一種規(guī)律，使二叉樹上的結(jié)點(diǎn)能排列在一個線性隊列上，從而便于遍歷。結(jié)點(diǎn)能排列在一個線性隊列上，從而便于遍歷。 二叉樹的基本組成：根結(jié)點(diǎn)二叉樹的基本組成：根結(jié)點(diǎn)

29、、左子樹左子樹、右子樹。若右子樹。若能依次遍歷這三部分，就是遍歷了二叉樹。能依次遍歷這三部分，就是遍歷了二叉樹。 若以若以L、D、R分別表示遍歷左子樹、遍歷根結(jié)點(diǎn)和分別表示遍歷左子樹、遍歷根結(jié)點(diǎn)和遍歷右子樹，遍歷右子樹，則有六種遍歷方案：則有六種遍歷方案：DLR、LDR、LRD、DRL、RDL、RLD。若規(guī)定若規(guī)定先左后右先左后右，則只有，則只有前三種前三種情況情況三種情況，分別是：三種情況，分別是：DLR先先( (根根) )序遍歷。序遍歷。LDR中中( (根根) )序遍歷。序遍歷。LRD后后( (根根) )序遍歷。序遍歷。 對于二叉樹的遍歷，分別討論遞歸遍歷算法和非遞對于二叉樹的遍歷，分別討

30、論遞歸遍歷算法和非遞歸遍歷算法。遞歸遍歷算法具有非常清晰的結(jié)構(gòu)，但初歸遍歷算法。遞歸遍歷算法具有非常清晰的結(jié)構(gòu)，但初學(xué)者往往難以接受或懷疑，不敢使用。實際上，遞歸算學(xué)者往往難以接受或懷疑，不敢使用。實際上，遞歸算法是由系統(tǒng)通過使用堆棧來實現(xiàn)控制的。而非遞歸算法法是由系統(tǒng)通過使用堆棧來實現(xiàn)控制的。而非遞歸算法中的控制是由設(shè)計者定義和使用堆棧來實現(xiàn)的。中的控制是由設(shè)計者定義和使用堆棧來實現(xiàn)的。1 遞歸算法遞歸算法算法的遞歸定義是：算法的遞歸定義是： 若二叉樹為空，則空操作；否則若二叉樹為空，則空操作；否則 訪問根結(jié)點(diǎn)；訪問根結(jié)點(diǎn)； 先序遍歷左子樹先序遍歷左子樹(遞歸調(diào)用本算法遞歸調(diào)用本算法)； 先

31、序遍歷右子樹先序遍歷右子樹(遞歸調(diào)用本算法遞歸調(diào)用本算法)。先序遍歷的遞歸算法先序遍歷的遞歸算法void PreorderTraverse(BiTree T) if (T!=NULL) visit(T-data) ; /* 訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn) */ PreorderTraverse(T-lchild) ; PreorderTraverse(T-rchild) ; 說明：說明：visit( )函數(shù)是訪問結(jié)點(diǎn)的數(shù)據(jù)域，其要求視具體函數(shù)是訪問結(jié)點(diǎn)的數(shù)據(jù)域，其要求視具體問題而定。樹采用二叉鏈表的存儲結(jié)構(gòu)，用指針變量問題而定。樹采用二叉鏈表的存儲結(jié)構(gòu)，用指針變量T T來指向。來指向。2 非遞歸算法非遞

32、歸算法設(shè)設(shè)T是指向二叉樹根結(jié)點(diǎn)的指針變量，非遞歸算法是：是指向二叉樹根結(jié)點(diǎn)的指針變量，非遞歸算法是：若二叉樹為空，則返回；否則，令若二叉樹為空，則返回；否則，令p=T； 訪問訪問p所指向的結(jié)點(diǎn)；所指向的結(jié)點(diǎn)； q=p-rchild ，若，若q不為空，則不為空，則q進(jìn)棧；進(jìn)棧； p=p-lchild ，若，若p不為空，轉(zhuǎn)不為空，轉(zhuǎn)(1)，否則轉(zhuǎn)，否則轉(zhuǎn)(4)； 退棧到退棧到p ，轉(zhuǎn)，轉(zhuǎn)(1)。重復(fù)以上過程直到?？諡橹?。重復(fù)以上過程直到?？諡橹?。算法實現(xiàn)算法實現(xiàn)：#define MAX_NODE 50void PreorderTraverse( BiTree T) BiTree StackMAX_

33、NODE ,*p=T, *q ;int top=0 ;if (T=NULL) printf(“ Binary Tree is Empty!n”) ;else do visit( p- data ) ; q=p-rchild ; if ( q!=NULL ) stacktop+=q ; p=p-lchild ; if (p=NULL) p=stack-top ; while (p!=NULL) ;1 遞歸算法遞歸算法算法的遞歸定義是：算法的遞歸定義是： 若二叉樹為空，則遍歷結(jié)束；否則若二叉樹為空，則遍歷結(jié)束；否則 中序遍歷左子樹中序遍歷左子樹(遞歸調(diào)用本算法遞歸調(diào)用本算法)； 訪問根結(jié)點(diǎn)；訪問根

34、結(jié)點(diǎn)； 中序遍歷右子樹中序遍歷右子樹(遞歸調(diào)用本算法遞歸調(diào)用本算法)。中序遍歷的遞歸算法中序遍歷的遞歸算法void InorderTraverse(BiTree T) if (T!=NULL) InorderTraverse(T-lchild) ; visit(T-data) ; /* 訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn) */ InorderTraverse(T-rchild) ; /*圖圖6-8(a) 的二叉樹，輸出的次序是：的二叉樹，輸出的次序是： cbegdfa */2 非遞歸算法非遞歸算法設(shè)設(shè)T是指向二叉樹根結(jié)點(diǎn)的指針變量，非遞歸算法是：是指向二叉樹根結(jié)點(diǎn)的指針變量，非遞歸算法是：若二叉樹為空，則返

35、回；否則，令若二叉樹為空，則返回；否則，令p=T 若若p不為空，則不為空，則 p進(jìn)棧，進(jìn)棧， p=p-lchild ；否則，否則， 當(dāng)當(dāng)p為空而棧不空時：為空而棧不空時： 退棧，棧頂元素出棧給退棧，棧頂元素出棧給p，訪問，訪問p所指向的結(jié)所指向的結(jié)點(diǎn)，點(diǎn)，p=p-rchild ，轉(zhuǎn)，轉(zhuǎn)(1)；重復(fù)以上過程直到重復(fù)以上過程直到p和棧均為空。和棧均為空。void InorderTraverse( BiTree T) InitStack(S); p=T; while (p!=NULL | !StackEmpty(S) ) if (p!=NULL) Push(S,p); p=p-lchild ; el

36、se Pop(S,p); visit( p-data ) ; p=p-rchild ; / if.else. / while 算法實現(xiàn)算法實現(xiàn)：1 遞歸算法遞歸算法算法的遞歸定義是：算法的遞歸定義是： 若二叉樹為空，則空操作；否則若二叉樹為空，則空操作；否則 后序遍歷左子樹后序遍歷左子樹(遞歸調(diào)用本算法遞歸調(diào)用本算法)； 后序遍歷右子樹后序遍歷右子樹(遞歸調(diào)用本算法遞歸調(diào)用本算法) ； 訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn) 。后序遍歷的遞歸算法后序遍歷的遞歸算法void PostorderTraverse(BiTree T) if (T!=NULL) PostorderTraverse(T-lchild) ;

37、PostorderTraverse(T-rchild) ; visit(T-data) ; /* 訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn) */ / /* *圖圖6-8(a) 的二叉樹，輸出的次序是：的二叉樹，輸出的次序是： cgefdba cgefdba * */ / 遍歷二叉樹的算法中基本操作是訪問結(jié)點(diǎn)，因此，遍歷二叉樹的算法中基本操作是訪問結(jié)點(diǎn)，因此，無論是哪種次序的遍歷，對有無論是哪種次序的遍歷，對有n個結(jié)點(diǎn)的二叉樹，其時個結(jié)點(diǎn)的二叉樹，其時間復(fù)雜度均為間復(fù)雜度均為O(n) 。 如圖如圖6-9所示的二叉樹表示表達(dá)式：所示的二叉樹表示表達(dá)式：(a+b*(c-d)-e/f)按不同的次序遍歷此二叉樹，將訪問的結(jié)

38、點(diǎn)按先后次序按不同的次序遍歷此二叉樹，將訪問的結(jié)點(diǎn)按先后次序排列起來的次序是：排列起來的次序是： 其先序序列為：其先序序列為： -+a*b-cd/ef 其中序序列為：其中序序列為： a+b*c-d-e/f 其后序序列為：其后序序列為： abcd-*+ef/-/fe-dcb*a+圖圖6-9 表達(dá)式表達(dá)式 (a+b*(c-d)-e/f)二叉樹二叉樹2 非遞歸算法非遞歸算法 在后序遍歷中，根結(jié)點(diǎn)是最后被訪問的。因此，在在后序遍歷中，根結(jié)點(diǎn)是最后被訪問的。因此，在遍歷過程中，當(dāng)搜索指針指向某一根結(jié)點(diǎn)時，不能立即遍歷過程中，當(dāng)搜索指針指向某一根結(jié)點(diǎn)時，不能立即訪問，而要先遍歷其左子樹，此時訪問，而要先遍

39、歷其左子樹，此時根結(jié)點(diǎn)進(jìn)棧根結(jié)點(diǎn)進(jìn)棧。當(dāng)其左。當(dāng)其左子樹遍歷完后再搜索到該根結(jié)點(diǎn)時，還是不能訪問，還子樹遍歷完后再搜索到該根結(jié)點(diǎn)時，還是不能訪問，還需遍歷其右子樹。所以，此需遍歷其右子樹。所以，此根結(jié)點(diǎn)還需再次進(jìn)棧根結(jié)點(diǎn)還需再次進(jìn)棧，當(dāng)其，當(dāng)其右子樹遍歷完后再退棧到到該根結(jié)點(diǎn)時，才能被訪問。右子樹遍歷完后再退棧到到該根結(jié)點(diǎn)時，才能被訪問。 因此，設(shè)立一個狀態(tài)標(biāo)志變量因此，設(shè)立一個狀態(tài)標(biāo)志變量tag ：0 ： 結(jié)點(diǎn)暫不能訪問結(jié)點(diǎn)暫不能訪問1 ： 結(jié)點(diǎn)可以被訪問結(jié)點(diǎn)可以被訪問tag= 其次，設(shè)兩個堆棧其次，設(shè)兩個堆棧S1、S2 ，S1保存結(jié)點(diǎn)，保存結(jié)點(diǎn)，S2保存結(jié)保存結(jié)點(diǎn)的點(diǎn)的狀態(tài)標(biāo)志變量狀態(tài)標(biāo)志

40、變量tag 。S1和和S2共用一個棧頂共用一個棧頂指針。指針。 設(shè)設(shè)T是指向根結(jié)點(diǎn)的指針變量，非遞歸算法是：是指向根結(jié)點(diǎn)的指針變量，非遞歸算法是：若二叉樹為空，則返回；否則，令若二叉樹為空，則返回；否則，令p=T； 第一次經(jīng)過根結(jié)點(diǎn)第一次經(jīng)過根結(jié)點(diǎn)p，不訪問：，不訪問： p進(jìn)棧進(jìn)棧S1 ， tag 賦值賦值0，進(jìn)棧，進(jìn)棧S2，p=p-lchild 。 若若p不為空，轉(zhuǎn)不為空，轉(zhuǎn)(1)，否則，取狀態(tài)標(biāo)志值，否則，取狀態(tài)標(biāo)志值tag ： 若若tag=0：對棧：對棧S1，不訪問，不出棧；修改，不訪問，不出棧；修改S2棧頂棧頂元素值元素值(tag賦值賦值1) ，取，取S1棧頂元素的右子樹，即棧頂元素的

41、右子樹，即p=S1top-1-rchild ，轉(zhuǎn)，轉(zhuǎn)(1)； 若若tag=1：S1退棧，訪問該結(jié)點(diǎn)；取標(biāo)志退棧，訪問該結(jié)點(diǎn)；取標(biāo)志tag，轉(zhuǎn)，轉(zhuǎn)（3）。）。重復(fù)以上過程直到棧空為止。重復(fù)以上過程直到棧空為止。算法實現(xiàn)算法實現(xiàn)：#define MAX_NODE 50void PostorderTraverse( BiTree T) BiTree S1MAX_NODE ,p=T ;int S2MAX_NODE , top=0 , bool=1 ;if (T=NULL) printf(“Binary Tree is Empty!n”) ;else do while (p!=NULL) S1top=p

42、 ; S2top=0 ; top+; p=p-lchild ; if (top=0) bool=0 ; /?？?，結(jié)束棧空，結(jié)束 else if (S2top-1=0) S2top-1=1 ; p=S1top-1-rchild ; else p=S1-top ; visit( p-data ) ; p=NULL ; /* 使循環(huán)繼續(xù)進(jìn)行而不至于死循環(huán)使循環(huán)繼續(xù)進(jìn)行而不至于死循環(huán) */ while (bool!=0) ; 層次遍歷二叉樹，是從根結(jié)點(diǎn)開始遍歷，按層次次層次遍歷二叉樹，是從根結(jié)點(diǎn)開始遍歷，按層次次序序“自上而下自上而下，從左至右從左至右”訪問樹中的各結(jié)點(diǎn)。訪問樹中的各結(jié)點(diǎn)。 為保證是按

43、層次遍歷，必須設(shè)置一個隊列，初始化為保證是按層次遍歷，必須設(shè)置一個隊列，初始化時為空。時為空。 設(shè)設(shè)T是指向根結(jié)點(diǎn)的指針變量，層次遍歷非遞歸算是指向根結(jié)點(diǎn)的指針變量，層次遍歷非遞歸算法是：法是：若二叉樹為空，則返回；否則，令若二叉樹為空，則返回；否則，令p=T，p入隊；入隊； 隊首元素出隊到隊首元素出隊到p；訪問訪問p所指向的結(jié)點(diǎn)；所指向的結(jié)點(diǎn)； 將將p所指向的結(jié)點(diǎn)的左、右子結(jié)點(diǎn)依次入隊。所指向的結(jié)點(diǎn)的左、右子結(jié)點(diǎn)依次入隊。重復(fù)以上過程直到隊空為止。重復(fù)以上過程直到隊空為止。void LevelorderTraverse( BiTree T) InitQueue(Q) ; p=T ;if (p

44、!=NULL) EnQueue(Q,p) ; /* 根指針入隊根指針入隊 */while ( !QueueEmpty(Q) DeQueue(Q,p) ; visit( p-data ); if (p-lchild!=NULL) EnQueue(Q,p-lchild); / 左指針入隊左指針入隊 if (p-rchild!=NULL) EnQueue(Q,p-rchild); / 右指針入隊右指針入隊 /while / if “遍歷遍歷”是二叉樹最重要的基本操作，是各種其它是二叉樹最重要的基本操作，是各種其它操作的基礎(chǔ)，二叉樹的許多其它操作都可以通過遍歷來操作的基礎(chǔ)，二叉樹的許多其它操作都可以通

45、過遍歷來實現(xiàn)。如建立二叉樹的存儲結(jié)構(gòu)、求二叉樹的結(jié)點(diǎn)數(shù)、實現(xiàn)。如建立二叉樹的存儲結(jié)構(gòu)、求二叉樹的結(jié)點(diǎn)數(shù)、求二叉樹的深度等。求二叉樹的深度等。二叉樹的二叉鏈表創(chuàng)建二叉樹的二叉鏈表創(chuàng)建 按先序遍歷方式建立按先序遍歷方式建立 對一棵二叉樹進(jìn)行對一棵二叉樹進(jìn)行“擴(kuò)充擴(kuò)充”，就可以得到有該二叉，就可以得到有該二叉樹所擴(kuò)充的二叉樹。有兩棵二叉樹樹所擴(kuò)充的二叉樹。有兩棵二叉樹T1及其擴(kuò)充的及其擴(kuò)充的二叉樹二叉樹T2如圖如圖6-10所示。所示。圖圖6-10 二叉樹二叉樹T1及其擴(kuò)充及其擴(kuò)充二叉樹二叉樹T2ABCDEFG(a) 二叉樹二叉樹T1(b) T1的擴(kuò)充的擴(kuò)充二叉樹二叉樹T2ABCDEFG? 二叉樹的擴(kuò)

46、充方法是：在二叉樹中結(jié)點(diǎn)的每一個空二叉樹的擴(kuò)充方法是：在二叉樹中結(jié)點(diǎn)的每一個空鏈域處增加一個擴(kuò)充的結(jié)點(diǎn)鏈域處增加一個擴(kuò)充的結(jié)點(diǎn)(總是葉子結(jié)點(diǎn)，用方框總是葉子結(jié)點(diǎn)，用方框“”表示表示)。對于二叉樹的結(jié)點(diǎn)值：。對于二叉樹的結(jié)點(diǎn)值： 是是char類型：擴(kuò)充結(jié)點(diǎn)值為類型：擴(kuò)充結(jié)點(diǎn)值為“？”； 是是int類型：擴(kuò)充結(jié)點(diǎn)值為類型：擴(kuò)充結(jié)點(diǎn)值為0或或-1； 下面的算法是二叉樹的前序創(chuàng)建的遞歸算法，讀入下面的算法是二叉樹的前序創(chuàng)建的遞歸算法，讀入一棵二叉樹對應(yīng)的擴(kuò)充二叉樹的前序遍歷的結(jié)點(diǎn)值序列。一棵二叉樹對應(yīng)的擴(kuò)充二叉樹的前序遍歷的結(jié)點(diǎn)值序列。每讀入一個結(jié)點(diǎn)值就進(jìn)行分析：每讀入一個結(jié)點(diǎn)值就進(jìn)行分析： 若是擴(kuò)充

47、結(jié)點(diǎn)值：令根指針為若是擴(kuò)充結(jié)點(diǎn)值：令根指針為NULL； 若是若是(正常正常)結(jié)點(diǎn)值：動態(tài)地為根指針分配一個結(jié)結(jié)點(diǎn)值：動態(tài)地為根指針分配一個結(jié)點(diǎn)，將該值賦給根結(jié)點(diǎn)，然后遞歸地創(chuàng)建根的左子點(diǎn)，將該值賦給根結(jié)點(diǎn)，然后遞歸地創(chuàng)建根的左子樹和右子樹。樹和右子樹。算法實現(xiàn)算法實現(xiàn)：typedef struct BiTNode char data ;struct BTNode *lchild , *rchild ;BiTNode ;Status Preorder_Create_BTree(BiTree &T) /* 建立鏈?zhǔn)蕉鏄洌祷刂赶蚋Y(jié)點(diǎn)的指針變量建立鏈?zhǔn)蕉鏄?，返回指向根結(jié)點(diǎn)的指針變量 */ sc

48、anf(&ch); if (ch=?) T=NULL; else T=(BiTree)malloc(sizeof(BiTNode) ; Tdata=ch ; Preorder_Create_BTree(T-lchild) ; Preorder_Create_BTree(T-rchild) ; return OK ; 當(dāng)希望創(chuàng)建圖當(dāng)希望創(chuàng)建圖6-10(a)所示的二叉樹時，輸入的字符所示的二叉樹時，輸入的字符序列應(yīng)當(dāng)是：序列應(yīng)當(dāng)是：ABD?E?G?CF?2 求二叉樹的葉子結(jié)點(diǎn)數(shù)求二叉樹的葉子結(jié)點(diǎn)數(shù) 可以直接利用先序遍歷二叉樹算法求二叉樹的葉子可以直接利用先序遍歷二叉樹算法求二叉樹的葉子結(jié)點(diǎn)數(shù)。只要

49、將先序遍歷二叉樹算法中結(jié)點(diǎn)數(shù)。只要將先序遍歷二叉樹算法中vist( )函數(shù)簡單函數(shù)簡單地進(jìn)行修改就可以。地進(jìn)行修改就可以。算法實現(xiàn)算法實現(xiàn)：void CountLeaf (BiTree T, int &count)/ 求葉子結(jié)點(diǎn)的個數(shù)，T為根結(jié)點(diǎn)的指針 if (T) if (!T-lchild)& (!T-rchild) count+; /若若T是是葉子結(jié)點(diǎn)葉子結(jié)點(diǎn)，對對其其計數(shù)計數(shù) CountLeaf( T-lchild, count); /對左子樹中葉結(jié)點(diǎn)計數(shù)對左子樹中葉結(jié)點(diǎn)計數(shù) CountLeaf( T-rchild, count); /對右子樹中葉結(jié)點(diǎn)計數(shù)對右子樹中葉結(jié)點(diǎn)計數(shù) / Co

50、untLeaf注：在主調(diào)函數(shù)中應(yīng)將注：在主調(diào)函數(shù)中應(yīng)將count的實參賦初值為的實參賦初值為0。二叉樹的深度應(yīng)為其左、右子樹深度的最大值加二叉樹的深度應(yīng)為其左、右子樹深度的最大值加1 1。利用后序遍歷，求得左、右子樹深度利用后序遍歷，求得左、右子樹深度hL，hRh =3.求二叉樹的深度求二叉樹的深度 max(hL,hR)+1 , TNULL0 , T=NULLint BiTreeDepth (BiTree T ) / 返回二叉樹的深度返回二叉樹的深度, T為樹根的指針為樹根的指針 if ( !T ) h = 0; else hL = BiTreeDepth( T-lchild ); hR= B

51、iTreeDepth( T-rchild ); h= 1 + (hL hR ? hL : hR); return h; 遍歷二叉樹是按一定的規(guī)則將樹中的結(jié)點(diǎn)排列成一遍歷二叉樹是按一定的規(guī)則將樹中的結(jié)點(diǎn)排列成一個線性序列個線性序列，即是對非線性結(jié)構(gòu)的線性化操作。如何找，即是對非線性結(jié)構(gòu)的線性化操作。如何找到到遍歷過程中動態(tài)得到遍歷過程中動態(tài)得到的每個結(jié)點(diǎn)的直接前驅(qū)和直接后的每個結(jié)點(diǎn)的直接前驅(qū)和直接后繼繼( (第一個和最后一個除外第一個和最后一個除外)?)?如何保存這些信息如何保存這些信息? ? 設(shè)一棵二叉樹有設(shè)一棵二叉樹有n個結(jié)點(diǎn)個結(jié)點(diǎn)，則有，則有n-1條邊條邊(指針連線指針連線) ， 而而n個

52、結(jié)點(diǎn)共有個結(jié)點(diǎn)共有2n個指針域個指針域(lchild和和rchild) ，顯然，顯然有有n+1個空閑指針域個空閑指針域未用未用。則可以利用這些。則可以利用這些空閑的指針域來存空閑的指針域來存放結(jié)點(diǎn)的放結(jié)點(diǎn)的直接前驅(qū)和直接后繼信息。直接前驅(qū)和直接后繼信息。對結(jié)點(diǎn)的指針域做如下規(guī)定對結(jié)點(diǎn)的指針域做如下規(guī)定： 若結(jié)點(diǎn)有左孩子，則若結(jié)點(diǎn)有左孩子，則lchild指向其左孩子，否則，指向其左孩子，否則，指向其直接前驅(qū)；指向其直接前驅(qū)； 若結(jié)點(diǎn)有右孩子若結(jié)點(diǎn)有右孩子，則則rchild指向其右孩子指向其右孩子，否則，否則，指向其直接后繼；指向其直接后繼；為避免混淆為避免混淆, ,對結(jié)點(diǎn)結(jié)構(gòu)加以改進(jìn)，增加兩個標(biāo)

53、志域，對結(jié)點(diǎn)結(jié)構(gòu)加以改進(jìn)，增加兩個標(biāo)志域，如圖如圖6-10所示。所示。lchild Ltag data rchild Rtag圖圖6-10 線索二叉樹的結(jié)點(diǎn)結(jié)構(gòu)線索二叉樹的結(jié)點(diǎn)結(jié)構(gòu)0：lchild域指示結(jié)點(diǎn)的左孩子域指示結(jié)點(diǎn)的左孩子1 1：lchild域指示結(jié)點(diǎn)的前驅(qū)域指示結(jié)點(diǎn)的前驅(qū)Ltag=0 0：rchild域指示結(jié)點(diǎn)的右孩子域指示結(jié)點(diǎn)的右孩子1 1：rchild域指示結(jié)點(diǎn)的后繼域指示結(jié)點(diǎn)的后繼Rtag= 用這種結(jié)點(diǎn)結(jié)構(gòu)構(gòu)成的二叉樹的存儲結(jié)構(gòu)；叫做線用這種結(jié)點(diǎn)結(jié)構(gòu)構(gòu)成的二叉樹的存儲結(jié)構(gòu)；叫做線索鏈表；指向結(jié)點(diǎn)前驅(qū)和后繼的指針叫做線索；按照某索鏈表；指向結(jié)點(diǎn)前驅(qū)和后繼的指針叫做線索；按照某種

54、次序遍歷，加上線索的二叉樹稱之為線索二叉樹。種次序遍歷，加上線索的二叉樹稱之為線索二叉樹。線索二叉樹的結(jié)點(diǎn)結(jié)構(gòu)與示例線索二叉樹的結(jié)點(diǎn)結(jié)構(gòu)與示例typedef struct BiThrNode TElemType data;struct BiTreeNode *lchild , *rchild ; int Ltag , Rtag ;BiThrNode ,*BiThrTree; 如圖如圖6-11是二叉樹及相應(yīng)的各種線索樹示例。是二叉樹及相應(yīng)的各種線索樹示例。AFHIEGBDC(a) 二叉樹二叉樹 (b) 先序線索樹的邏輯形式先序線索樹的邏輯形式 結(jié)點(diǎn)序列：結(jié)點(diǎn)序列：ABDCEGFHIAFHIEGB

55、DCNIL(d) 后序線索樹的邏輯形式后序線索樹的邏輯形式 結(jié)點(diǎn)序列：結(jié)點(diǎn)序列：DBGEHIFCA(c) 中序線索樹的邏輯形式中序線索樹的邏輯形式 結(jié)點(diǎn)序列：結(jié)點(diǎn)序列：DBAGECHFIAFHIEGBDCNILNILAFHIEGBDCNIL 0 A 0 0 B 1 0 C 0 1 D 1 0 E 1 0 F 0 1 G 1 1 H 1 1 I 1 (e) 中序線索樹的鏈表結(jié)構(gòu)中序線索樹的鏈表結(jié)構(gòu)圖圖6-11 線索二叉樹及其存儲結(jié)構(gòu)線索二叉樹及其存儲結(jié)構(gòu)說明說明：畫線索二叉樹時，畫線索二叉樹時，實線實線表示指針，指向其左表示指針，指向其左、右孩子；右孩子；虛線虛線表示線索，指向其直接前驅(qū)或直接后

56、繼。表示線索，指向其直接前驅(qū)或直接后繼。 在線索樹上進(jìn)行遍歷，只要先找到序列中的第一個在線索樹上進(jìn)行遍歷，只要先找到序列中的第一個結(jié)點(diǎn)，然后就可以依次找結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)直到后繼結(jié)點(diǎn)，然后就可以依次找結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)直到后繼為空為止。為空為止。DBAGECHFI 如何在線索樹中找結(jié)點(diǎn)的直接后繼如何在線索樹中找結(jié)點(diǎn)的直接后繼? ?以圖以圖6-11(d) ，(e)所示的中序線索樹為例：所示的中序線索樹為例： 樹中樹中所有無右子樹結(jié)點(diǎn)的右鏈都是所有無右子樹結(jié)點(diǎn)的右鏈都是線索線索。右鏈直右鏈直接指示了結(jié)點(diǎn)的直接后繼接指示了結(jié)點(diǎn)的直接后繼，如結(jié)點(diǎn)，如結(jié)點(diǎn)G的直接后繼是結(jié)的直接后繼是結(jié)點(diǎn)點(diǎn)E。 樹中樹中

57、所有有右子樹結(jié)點(diǎn)的右鏈都是所有有右子樹結(jié)點(diǎn)的右鏈都是指針指針。根據(jù)中序。根據(jù)中序遍歷的規(guī)律，遍歷的規(guī)律，非葉子結(jié)點(diǎn)的直接后繼是遍歷其右子樹非葉子結(jié)點(diǎn)的直接后繼是遍歷其右子樹時訪問的第一個結(jié)點(diǎn)時訪問的第一個結(jié)點(diǎn)，即右子樹中最左下的結(jié)點(diǎn)。如，即右子樹中最左下的結(jié)點(diǎn)。如結(jié)點(diǎn)結(jié)點(diǎn)C的直接后繼的直接后繼：沿右指針找到右子樹的根結(jié)點(diǎn)：沿右指針找到右子樹的根結(jié)點(diǎn)F，然后沿左鏈往下直到然后沿左鏈往下直到Ltag=1的結(jié)點(diǎn)即為的結(jié)點(diǎn)即為C的直接后繼的直接后繼結(jié)點(diǎn)結(jié)點(diǎn)H。 如何在線索樹中找結(jié)點(diǎn)的直接前驅(qū)如何在線索樹中找結(jié)點(diǎn)的直接前驅(qū)? ?若若結(jié)點(diǎn)的結(jié)點(diǎn)的Ltag=1，則左鏈?zhǔn)蔷€索，指示其直接前驅(qū)；否則，遍歷，則左

58、鏈?zhǔn)蔷€索，指示其直接前驅(qū)；否則，遍歷左子樹時訪問的最后一個結(jié)點(diǎn)左子樹時訪問的最后一個結(jié)點(diǎn)( (即沿左子樹中最右往下即沿左子樹中最右往下的結(jié)點(diǎn)的結(jié)點(diǎn)) ) 為其為其直接前驅(qū)結(jié)點(diǎn)。直接前驅(qū)結(jié)點(diǎn)。 對于后序遍歷的線索樹中找結(jié)點(diǎn)的直接后繼比較復(fù)對于后序遍歷的線索樹中找結(jié)點(diǎn)的直接后繼比較復(fù)雜，可分以下三種情況雜，可分以下三種情況： 若若結(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)是

59、其父結(jié)點(diǎn)的左孩子且其父結(jié)點(diǎn)有右子樹：直接后繼是對其直接后繼是對其父父結(jié)點(diǎn)的右子樹按后序遍歷的第一個結(jié)點(diǎn)的右子樹按后序遍歷的第一個結(jié)點(diǎn)結(jié)點(diǎn)。 二叉樹的線索化二叉樹的線索化指的是依照某種遍歷次序使二叉樹指的是依照某種遍歷次序使二叉樹成為線索二叉樹的過程。成為線索二叉樹的過程。 線索化的過程就是線索化的過程就是在遍歷過程中修改空指針使其指向在遍歷過程中修改空指針使其指向直接前驅(qū)或直接后繼直接前驅(qū)或直接后繼的過程。的過程。 仿照線性表的存儲結(jié)構(gòu)，在二叉樹的線索鏈表上也添仿照線性表的存儲結(jié)構(gòu)，在二叉樹的線索鏈表上也添加一個頭結(jié)點(diǎn)加一個頭結(jié)點(diǎn)Thrt，頭結(jié)點(diǎn)的指針域的安排是：，頭結(jié)點(diǎn)的指針域的安排是： l

60、child域：指向二叉樹的根結(jié)點(diǎn)；域：指向二叉樹的根結(jié)點(diǎn)； rchild域：指向中序遍歷時的最后一個結(jié)點(diǎn)；域：指向中序遍歷時的最后一個結(jié)點(diǎn)； 二叉樹中序序列中的二叉樹中序序列中的第一個結(jié)點(diǎn)第一個結(jié)點(diǎn)lchild指針域指針域和和最后一個結(jié)點(diǎn)最后一個結(jié)點(diǎn)rchild指針域指針域均指向頭結(jié)點(diǎn)均指向頭結(jié)點(diǎn)Thrt。 如同為二叉樹建立了一個雙向線索鏈表，對一棵線如同為二叉樹建立了一個雙向線索鏈表，對一棵線索二叉樹既可從頭結(jié)點(diǎn)開始按尋找直接后繼進(jìn)行遍歷也索二叉樹既可從頭結(jié)點(diǎn)開始按尋找直接后繼進(jìn)行遍歷也可從最后一個結(jié)點(diǎn)開始按尋找直接前驅(qū)進(jìn)行遍歷。顯然，可從最后一個結(jié)點(diǎn)開始按尋找直接前驅(qū)進(jìn)行遍歷。顯然，這種遍