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

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

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

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

4、CEGFHIMJNKL(a) 只有根結(jié)點(diǎn)只有根結(jié)點(diǎn)(b) 一般的樹(shù)一般的樹(shù) 如圖如圖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，樹(shù)的度是，樹(shù)的度是3 。 葉子葉子(leaf)結(jié)點(diǎn)結(jié)點(diǎn)、非葉子結(jié)點(diǎn)非葉子結(jié)點(diǎn)：樹(shù)中樹(shù)中度為度為0的的結(jié)點(diǎn)稱為結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)葉子結(jié)點(diǎn)( (或終端結(jié)點(diǎn)或終端結(jié)點(diǎn)) )。相對(duì)應(yīng)地，。相對(duì)應(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) 一個(gè)結(jié)點(diǎn)的一個(gè)結(jié)點(diǎn)的子樹(shù)的根子樹(shù)的根稱為該結(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)。或父結(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ī)定樹(shù)中根結(jié)點(diǎn)的層次為規(guī)定樹(shù)中根結(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)開(kāi)始，到達(dá)某結(jié)點(diǎn)從根結(jié)點(diǎn)開(kāi)始，到達(dá)某結(jié)點(diǎn)p所經(jīng)過(guò)的所有結(jié)點(diǎn)稱所經(jīng)過(guò)的所有結(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)為根的子樹(shù)中的任意結(jié)點(diǎn)稱為該結(jié)點(diǎn)的以某一結(jié)點(diǎn)為根的子樹(shù)中的任意結(jié)點(diǎn)稱為該結(jié)點(diǎn)的子孫結(jié)點(diǎn)子孫結(jié)點(diǎn)(descent)。 樹(shù)的深度樹(shù)的深度(depth)：樹(shù)中結(jié)點(diǎn)的最大層次值，又樹(shù)中結(jié)點(diǎn)的最大層次值，又稱為樹(shù)的高度，如圖稱為樹(shù)的高度，如圖6-1(b)中樹(shù)的高度為中樹(shù)的高度為4。 有序樹(shù)和無(wú)序樹(shù)有序樹(shù)和無(wú)序樹(shù)：對(duì)

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

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

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

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

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

13、于二個(gè)結(jié)點(diǎn)。由于二叉樹(shù)每個(gè)結(jié)點(diǎn)的度最大為叉樹(shù)每個(gè)結(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的二叉樹(shù)的最大的結(jié)點(diǎn)數(shù)為二叉樹(shù)中每的二叉樹(shù)的最大的結(jié)點(diǎn)數(shù)為二叉樹(shù)中每層上的最大結(jié)點(diǎn)數(shù)之和。層上的最大結(jié)點(diǎn)數(shù)之和。 由性質(zhì)由性質(zhì)1知知，二叉樹(shù)的第，二叉樹(shù)的第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：對(duì)任何一棵二叉樹(shù)，若

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

15、度為1和和2的結(jié)點(diǎn)射出的。設(shè)的結(jié)點(diǎn)射出的。設(shè)B為二叉樹(shù)中的分支總數(shù)，則有：為二叉樹(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 證畢證畢滿二叉樹(shù)和完全二叉樹(shù)滿二叉樹(shù)和完全二叉樹(shù) 一棵深度為一棵深度為k且有且有2k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)稱為個(gè)結(jié)點(diǎn)的二叉樹(shù)稱為滿二叉滿二叉樹(shù)樹(shù)(Full Binary Tree)。 如圖如圖6-4(a) 就是一棵深度為就是一棵深度為4的滿二叉樹(shù)。的滿二叉樹(shù)。894101151213614157213894101152112673(a) 滿二叉樹(shù)滿二叉樹(shù)(b) 完全二叉樹(shù)完全

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

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

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

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

20、中不存在編號(hào)為，則二叉樹(shù)中不存在編號(hào)為2的結(jié)點(diǎn)，說(shuō)明的結(jié)點(diǎn)，說(shuō)明結(jié)點(diǎn)結(jié)點(diǎn)i的左的左孩子孩子不存在。不存在。 若若3n，則二叉樹(shù)中不存在編號(hào)為，則二叉樹(shù)中不存在編號(hào)為3的結(jié)點(diǎn)，說(shuō)明的結(jié)點(diǎn)，說(shuō)明結(jié)點(diǎn)結(jié)點(diǎn)i的右的右孩子孩子不存在。不存在。 現(xiàn)假設(shè)對(duì)于編號(hào)為現(xiàn)假設(shè)對(duì)于編號(hào)為j(1ji)的結(jié)點(diǎn)的結(jié)點(diǎn)，(2)(2)和和(3)(3)成立。成立。即：即： 當(dāng)當(dāng)2jn ：結(jié)點(diǎn)：結(jié)點(diǎn)j的左孩子編號(hào)是的左孩子編號(hào)是2j；當(dāng)；當(dāng)2jn時(shí)時(shí)，結(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的右孩子編號(hào)是的右孩子編號(hào)是2j+1；當(dāng)；當(dāng)2j+1n時(shí)，結(jié)點(diǎn)時(shí)，結(jié)點(diǎn)j的右孩子結(jié)點(diǎn)不存在。的右孩

21、子結(jié)點(diǎn)不存在。 當(dāng)當(dāng)i=j+1時(shí)，由完全二叉樹(shù)的定義知，若結(jié)點(diǎn)時(shí)，由完全二叉樹(shù)的定義知，若結(jié)點(diǎn)i的左的左孩子結(jié)點(diǎn)存在，則其左孩子結(jié)點(diǎn)的編號(hào)一定等于編號(hào)孩子結(jié)點(diǎn)存在，則其左孩子結(jié)點(diǎn)的編號(hào)一定等于編號(hào)為為j的右孩子的編號(hào)加的右孩子的編號(hào)加1，即結(jié)點(diǎn)，即結(jié)點(diǎn)i的左孩子的編號(hào)為：的左孩子的編號(hào)為： (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)存在，則其右孩子的編號(hào)為：右孩子的編號(hào)為：2i+1，且有，且有2i+1n。相反，若。相反，若2i+

22、1n，則左孩子結(jié)點(diǎn)不存在。結(jié)論，則左孩子結(jié)點(diǎn)不存在。結(jié)論(2)(2)和和(3)(3)得證。得證。 再由再由(2)(2)和和(3)(3)來(lái)證明來(lái)證明(1) 。 當(dāng)當(dāng)i=1時(shí)時(shí)，顯然編號(hào)為，顯然編號(hào)為1的的是根結(jié)點(diǎn)，無(wú)雙親結(jié)點(diǎn)。是根結(jié)點(diǎn)，無(wú)雙親結(jié)點(diǎn)。 當(dāng)當(dāng)i1時(shí)，設(shè)編號(hào)為時(shí)，設(shè)編號(hào)為i的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)為的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)為m，若編號(hào)為若編號(hào)為i的結(jié)點(diǎn)是其雙親結(jié)點(diǎn)的左孩子，則由的結(jié)點(diǎn)是其雙親結(jié)點(diǎn)的左孩子，則由(2)有：有：i=2m ，即，即m= i/2 ；若編號(hào)為若編號(hào)為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時(shí)時(shí)，其雙親結(jié)點(diǎn)的編號(hào)為，其雙親結(jié)點(diǎn)的編號(hào)為 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 完全完全二叉二叉樹(shù)中結(jié)點(diǎn)樹(shù)中結(jié)點(diǎn)i和和i+1的左右孩子的左右孩子1 順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu) 二叉樹(shù)存儲(chǔ)結(jié)構(gòu)的類型定義：二叉樹(shù)存儲(chǔ)結(jié)構(gòu)的類型定義：#define MAX_SIZE 100 typedef telemtype sqbitreeMAX_SIZE; 用一組地址連續(xù)的存儲(chǔ)單元依次用一組地址連續(xù)的存儲(chǔ)單元依次“自上而下自上而下

24、、自左自左至右至右”存儲(chǔ)完全二叉樹(shù)的數(shù)據(jù)元素。存儲(chǔ)完全二叉樹(shù)的數(shù)據(jù)元素。 對(duì)于完全二叉樹(shù)上編號(hào)為對(duì)于完全二叉樹(shù)上編號(hào)為i的結(jié)點(diǎn)元素存儲(chǔ)在一維的結(jié)點(diǎn)元素存儲(chǔ)在一維數(shù)組的下標(biāo)值為數(shù)組的下標(biāo)值為i-1的分量中的分量中，如圖，如圖6-6(c)所示。所示。 對(duì)于一般的二叉樹(shù)，將其每個(gè)結(jié)點(diǎn)與完全二叉樹(shù)上對(duì)于一般的二叉樹(shù)，將其每個(gè)結(jié)點(diǎn)與完全二叉樹(shù)上的結(jié)點(diǎn)相對(duì)照，的結(jié)點(diǎn)相對(duì)照，存儲(chǔ)在一維數(shù)組中存儲(chǔ)在一維數(shù)組中，如圖，如圖6-6(d)所示。所示。abcdhiejklfg(a) 完全二叉樹(shù)完全二叉樹(shù)(b) 非完全二叉樹(shù)非完全二叉樹(shù)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) 完全二叉樹(shù)的順序存儲(chǔ)形式完全二叉樹(shù)的順序存儲(chǔ)形式1 2 3 4 5 6 7 8 9 10 11a b c d e h f g(d) 非完全二叉樹(shù)的順序存儲(chǔ)形式非完全二叉樹(shù)的順序存儲(chǔ)形式圖圖6-6 二叉二叉樹(shù)及其樹(shù)及其順序存儲(chǔ)形式順序存儲(chǔ)形式 最壞的情況下，一個(gè)深度為最壞的情況下，一個(gè)深度為k且只有且只有k個(gè)結(jié)點(diǎn)的單支個(gè)結(jié)點(diǎn)的單支樹(shù)需要長(zhǎng)度為樹(shù)需要長(zhǎng)度為2k-1的一維數(shù)組的一維數(shù)組。2 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 設(shè)計(jì)不同的結(jié)點(diǎn)結(jié)構(gòu)可構(gòu)成不同的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。設(shè)計(jì)不同的結(jié)點(diǎn)結(jié)構(gòu)可構(gòu)成不同的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。(1) 結(jié)點(diǎn)的類型及其定義結(jié)點(diǎn)的類型及其定義 二叉鏈表結(jié)

26、點(diǎn)二叉鏈表結(jié)點(diǎn)。有三個(gè)域：一個(gè)數(shù)據(jù)域，兩個(gè)分。有三個(gè)域：一個(gè)數(shù)據(jù)域，兩個(gè)分別指向左右子結(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)。除二叉鏈表的三個(gè)域外，再增加一。除二叉鏈表的三個(gè)域外，再增加一個(gè)指針域，用來(lái)指向結(jié)點(diǎn)的父結(jié)點(diǎn)，如圖個(gè)指針域，用來(lái)指向結(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) 二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)形式二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)形式 例有一棵一般的二叉樹(shù)，如圖例有一棵一般的二叉樹(shù)，如圖6-8(a)所示。以二叉所示。以二叉鏈表和三叉鏈表方式存儲(chǔ)的結(jié)構(gòu)圖分別如圖鏈表和三叉鏈表方式存儲(chǔ)的結(jié)構(gòu)圖分別如圖6-8(b) 、 6-8(c)所示。所示。圖圖6-8 二叉樹(shù)及其二叉樹(shù)及其鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(a) 二叉樹(shù)二叉樹(shù)afedcbg(c) 三三叉鏈表叉鏈表 a b c d e f g T(b) 二二叉鏈表叉鏈表 a b c d e g f T遍歷二叉樹(shù)遍歷二叉樹(shù)

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

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

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

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

32、歸算法設(shè)設(shè)T是指向二叉樹(shù)根結(jié)點(diǎn)的指針變量，非遞歸算法是：是指向二叉樹(shù)根結(jié)點(diǎn)的指針變量，非遞歸算法是：若二叉樹(shù)為空，則返回；否則，令若二叉樹(shù)為空，則返回；否則，令p=T； 訪問(wèn)訪問(wèn)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ù)以上過(guò)程直到?？諡橹埂Ｖ貜?fù)以上過(guò)程直到?？諡橹埂Ｋ惴▽?shí)現(xiàn)算法實(shí)現(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 遞歸算法遞歸算法算法的遞歸定義是：算法的遞歸定義是： 若二叉樹(shù)為空，則遍歷結(jié)束；否則若二叉樹(shù)為空，則遍歷結(jié)束；否則 中序遍歷左子樹(shù)中序遍歷左子樹(shù)(遞歸調(diào)用本算法遞歸調(diào)用本算法)； 訪問(wèn)根結(jié)點(diǎn)；訪問(wèn)根

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

35、回；否則，令若二叉樹(shù)為空，則返回；否則，令p=T 若若p不為空，則不為空，則 p進(jìn)棧，進(jìn)棧， p=p-lchild ；否則，否則， 當(dāng)當(dāng)p為空而棧不空時(shí)：為空而棧不空時(shí)： 退棧，棧頂元素出棧給退棧，棧頂元素出棧給p，訪問(wèn)，訪問(wèn)p所指向的結(jié)所指向的結(jié)點(diǎn)，點(diǎn)，p=p-rchild ，轉(zhuǎn)，轉(zhuǎn)(1)；重復(fù)以上過(guò)程直到重復(fù)以上過(guò)程直到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 算法實(shí)現(xiàn)算法實(shí)現(xiàn)：1 遞歸算法遞歸算法算法的遞歸定義是：算法的遞歸定義是： 若二叉樹(shù)為空，則空操作；否則若二叉樹(shù)為空，則空操作；否則 后序遍歷左子樹(shù)后序遍歷左子樹(shù)(遞歸調(diào)用本算法遞歸調(diào)用本算法)； 后序遍歷右子樹(shù)后序遍歷右子樹(shù)(遞歸調(diào)用本算法遞歸調(diào)用本算法) ； 訪問(wèn)根結(jié)點(diǎn)訪問(wèn)根結(jié)點(diǎn) 。后序遍歷的遞歸算法后序遍歷的遞歸算法void PostorderTraverse(BiTree T) if (T!=NULL) PostorderTraverse(T-lchild) ;

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

38、點(diǎn)按先后次序按不同的次序遍歷此二叉樹(shù)，將訪問(wèn)的結(jié)點(diǎn)按先后次序排列起來(lái)的次序是：排列起來(lái)的次序是： 其先序序列為：其先序序列為： -+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)二叉樹(shù)二叉樹(shù)2 非遞歸算法非遞歸算法 在后序遍歷中，根結(jié)點(diǎn)是最后被訪問(wèn)的。因此，在在后序遍歷中，根結(jié)點(diǎn)是最后被訪問(wèn)的。因此，在遍歷過(guò)程中，當(dāng)搜索指針指向某一根結(jié)點(diǎn)時(shí)，不能立即遍歷過(guò)程中，當(dāng)搜索指針指向某一根結(jié)點(diǎn)時(shí)，不能立即訪問(wèn)，而要先遍歷其左子樹(shù)，此時(shí)訪問(wèn)，而要先遍

39、歷其左子樹(shù)，此時(shí)根結(jié)點(diǎn)進(jìn)棧根結(jié)點(diǎn)進(jìn)棧。當(dāng)其左。當(dāng)其左子樹(shù)遍歷完后再搜索到該根結(jié)點(diǎn)時(shí)，還是不能訪問(wèn)，還子樹(shù)遍歷完后再搜索到該根結(jié)點(diǎn)時(shí)，還是不能訪問(wèn)，還需遍歷其右子樹(shù)。所以，此需遍歷其右子樹(shù)。所以，此根結(jié)點(diǎn)還需再次進(jìn)棧根結(jié)點(diǎn)還需再次進(jìn)棧，當(dāng)其，當(dāng)其右子樹(shù)遍歷完后再退棧到到該根結(jié)點(diǎn)時(shí)，才能被訪問(wèn)。右子樹(shù)遍歷完后再退棧到到該根結(jié)點(diǎn)時(shí)，才能被訪問(wèn)。 因此，設(shè)立一個(gè)狀態(tài)標(biāo)志變量因此，設(shè)立一個(gè)狀態(tài)標(biāo)志變量tag ：0 ： 結(jié)點(diǎn)暫不能訪問(wèn)結(jié)點(diǎn)暫不能訪問(wèn)1 ： 結(jié)點(diǎn)可以被訪問(wèn)結(jié)點(diǎn)可以被訪問(wèn)tag= 其次，設(shè)兩個(gè)堆棧其次，設(shè)兩個(gè)堆棧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共用一個(gè)棧頂共用一個(gè)棧頂指針。指針。 設(shè)設(shè)T是指向根結(jié)點(diǎn)的指針變量，非遞歸算法是：是指向根結(jié)點(diǎn)的指針變量，非遞歸算法是：若二叉樹(shù)為空，則返回；否則，令若二叉樹(shù)為空，則返回；否則，令p=T； 第一次經(jīng)過(guò)根結(jié)點(diǎn)第一次經(jīng)過(guò)根結(jié)點(diǎn)p，不訪問(wèn)：，不訪問(wèn)： 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：對(duì)棧：對(duì)棧S1，不訪問(wèn)，不出棧；修改，不訪問(wèn)，不出棧；修改S2棧頂棧頂元素值元素值(tag賦值賦值1) ，取，取S1棧頂元素的右子樹(shù)，即棧頂元素的

41、右子樹(shù)，即p=S1top-1-rchild ，轉(zhuǎn)，轉(zhuǎn)(1)； 若若tag=1：S1退棧，訪問(wèn)該結(jié)點(diǎn)；取標(biāo)志退棧，訪問(wèn)該結(jié)點(diǎn)；取標(biāo)志tag，轉(zhuǎn)，轉(zhuǎn)（3）。）。重復(fù)以上過(guò)程直到?？諡橹?。重復(fù)以上過(guò)程直到棧空為止。算法實(shí)現(xiàn)算法實(shí)現(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é)束?？眨Y(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) ; 層次遍歷二叉樹(shù)，是從根結(jié)點(diǎn)開(kāi)始遍歷，按層次次層次遍歷二叉樹(shù)，是從根結(jié)點(diǎn)開(kāi)始遍歷，按層次次序序“自上而下自上而下，從左至右從左至右”訪問(wèn)樹(shù)中的各結(jié)點(diǎn)。訪問(wèn)樹(shù)中的各結(jié)點(diǎn)。 為保證是按

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

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

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

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

47、結(jié)點(diǎn)值：令根指針為若是擴(kuò)充結(jié)點(diǎn)值：令根指針為NULL； 若是若是(正常正常)結(jié)點(diǎn)值：動(dòng)態(tài)地為根指針?lè)峙湟粋€(gè)結(jié)結(jié)點(diǎn)值：動(dòng)態(tài)地為根指針?lè)峙湟粋€(gè)結(jié)點(diǎn)，將該值賦給根結(jié)點(diǎn)，然后遞歸地創(chuàng)建根的左子點(diǎn)，將該值賦給根結(jié)點(diǎn)，然后遞歸地創(chuàng)建根的左子樹(shù)和右子樹(shù)。樹(shù)和右子樹(shù)。算法實(shí)現(xiàn)算法實(shí)現(xiàn)：typedef struct BiTNode char data ;struct BTNode *lchild , *rchild ;BiTNode ;Status Preorder_Create_BTree(BiTree &T) /* 建立鏈?zhǔn)蕉鏄?shù)，返回指向根結(jié)點(diǎn)的指針變量建立鏈?zhǔn)蕉鏄?shù)，返回指向根結(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)所示的二叉樹(shù)時(shí)，輸入的字符所示的二叉樹(shù)時(shí)，輸入的字符序列應(yīng)當(dāng)是：序列應(yīng)當(dāng)是：ABD?E?G?CF?2 求二叉樹(shù)的葉子結(jié)點(diǎn)數(shù)求二叉樹(shù)的葉子結(jié)點(diǎn)數(shù) 可以直接利用先序遍歷二叉樹(shù)算法求二叉樹(shù)的葉子可以直接利用先序遍歷二叉樹(shù)算法求二叉樹(shù)的葉子結(jié)點(diǎn)數(shù)。只要

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

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

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

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

53、志域，對(duì)結(jié)點(diǎn)結(jié)構(gòu)加以改進(jìn)，增加兩個(gè)標(biāo)志域，如圖如圖6-10所示。所示。lchild Ltag data rchild Rtag圖圖6-10 線索二叉樹(shù)的結(jié)點(diǎn)結(jié)構(gòu)線索二叉樹(shù)的結(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)成的二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)；叫做線用這種結(jié)點(diǎn)結(jié)構(gòu)構(gòu)成的二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)；叫做線索鏈表；指向結(jié)點(diǎn)前驅(qū)和后繼的指針叫做線索；按照某索鏈表；指向結(jié)點(diǎn)前驅(qū)和后繼的指針叫做線索；按照某種

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

55、DCNIL(d) 后序線索樹(shù)的邏輯形式后序線索樹(shù)的邏輯形式 結(jié)點(diǎn)序列：結(jié)點(diǎn)序列：DBGEHIFCA(c) 中序線索樹(shù)的邏輯形式中序線索樹(shù)的邏輯形式 結(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) 中序線索樹(shù)的鏈表結(jié)構(gòu)中序線索樹(shù)的鏈表結(jié)構(gòu)圖圖6-11 線索二叉樹(shù)及其存儲(chǔ)結(jié)構(gòu)線索二叉樹(shù)及其存儲(chǔ)結(jié)構(gòu)說(shuō)明說(shuō)明：畫(huà)線索二叉樹(shù)時(shí)，畫(huà)線索二叉樹(shù)時(shí)，實(shí)線實(shí)線表示指針，指向其左表示指針，指向其左、右孩子；右孩子；虛線虛線表示線索，指向其直接前驅(qū)或直接后

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

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

58、鏈?zhǔn)蔷€索，指示其直接前驅(qū)；否則，遍歷左子樹(shù)時(shí)訪問(wèn)的最后一個(gè)結(jié)點(diǎn)左子樹(shù)時(shí)訪問(wèn)的最后一個(gè)結(jié)點(diǎn)( (即沿左子樹(shù)中最右往下即沿左子樹(shù)中最右往下的結(jié)點(diǎn)的結(jié)點(diǎn)) ) 為其為其直接前驅(qū)結(jié)點(diǎn)。直接前驅(qū)結(jié)點(diǎn)。 對(duì)于后序遍歷的線索樹(shù)中找結(jié)點(diǎn)的直接后繼比較復(fù)對(duì)于后序遍歷的線索樹(shù)中找結(jié)點(diǎn)的直接后繼比較復(fù)雜，可分以下三種情況雜，可分以下三種情況： 若若結(jié)點(diǎn)是二叉樹(shù)的根結(jié)點(diǎn)結(jié)點(diǎn)是二叉樹(shù)的根結(jié)點(diǎn)：其：其直接后繼為空直接后繼為空； 若若結(jié)點(diǎn)是其父結(jié)點(diǎn)的右孩子或左孩子且其父結(jié)點(diǎn)結(jié)點(diǎn)是其父結(jié)點(diǎn)的右孩子或左孩子且其父結(jié)點(diǎn)沒(méi)有右子樹(shù)沒(méi)有右子樹(shù)：直接后繼為其直接后繼為其父父結(jié)點(diǎn)結(jié)點(diǎn)； 若若結(jié)點(diǎn)是其父結(jié)點(diǎn)的左孩子且其父結(jié)點(diǎn)有右子樹(shù)結(jié)點(diǎn)是

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

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