數(shù)據(jù)結(jié)構(gòu)課件第8章.ppt

1、第 8 章 樹與二叉樹,8.1 樹的基本概念 8.2 二叉樹 8.3 線索二叉樹 8.4 排序二叉樹 8.5 樹與森林 8.6 哈夫曼樹 8.7 實(shí)習(xí)八： 二叉樹遍歷演示程序,8.1 樹的基本概念,8.1.1 樹的定義及應(yīng)用 樹型結(jié)構(gòu)的例子廣泛存在于現(xiàn)實(shí)生活中。 例如， 圖8.1(a) 表示了一家的父子關(guān)系。其中，圓圈代表了家族中的某個(gè)人，圓圈之間的連線則反映了對(duì)應(yīng)的人之間存在父子關(guān)系：李富貴有兩個(gè)兒子李元盛和李元清，其中，李元盛又有三個(gè)兒子李明秀、李明英和李明杰。這種表示看上去就像一棵倒立的樹，層次分明地反映了家族成員間的關(guān)系。同樣，一個(gè)機(jī)構(gòu)中的行政關(guān)系也可表示成樹型結(jié)構(gòu)，如圖8.1(b)所

2、示。其中，圓圈代表了機(jī)構(gòu)中的各個(gè)部門，連線則反映了各部門間的領(lǐng)導(dǎo)與被領(lǐng)導(dǎo)關(guān)系。 圖8.1(b)表示的是某學(xué)校的行政建制。,圖 8.1 樹的例子,在這種樹型的表示方法中，代表著某個(gè)實(shí)體的圓圈通常被稱作結(jié)點(diǎn)，而在所有的結(jié)點(diǎn)中，會(huì)有一個(gè)處于最高層次的結(jié)點(diǎn)。 在圖8.1(a)中， 代表李富貴的結(jié)點(diǎn)是處于最高層次的結(jié)點(diǎn)，因?yàn)槔罡毁F是其他所有人的祖先；在圖8.1(b)中，代表長沙大學(xué)的結(jié)點(diǎn)是處于最高層次的結(jié)點(diǎn)，因?yàn)樗I(lǐng)導(dǎo)著所有其他結(jié)點(diǎn)所代表的機(jī)構(gòu)。這個(gè)處于最高層次的結(jié)點(diǎn)通常被稱為根結(jié)點(diǎn)，它就如同樹的根一般，其他的所有結(jié)點(diǎn)均是以這個(gè)“根”為基礎(chǔ)得到的， 全部結(jié)點(diǎn)在一起就構(gòu)成了一棵“樹”。,例如，一個(gè)算術(shù)表達(dá)

3、式也可以用樹型結(jié)構(gòu)來表示。運(yùn)算符作為根結(jié)點(diǎn)，參與運(yùn)算的兩個(gè)運(yùn)算對(duì)象分別作為根結(jié)點(diǎn)的左、 右兩棵子樹。圖8.1(c)所示的樹表示的算術(shù)表達(dá)式可理解為 ab+(c-d/e)f 。 作為一種數(shù)據(jù)結(jié)構(gòu)，樹的定義如下：樹(tree)是n0個(gè)結(jié)點(diǎn)的有限集合。n0的樹稱為空樹。在任何一棵非空樹T中， 有一個(gè)特定的結(jié)點(diǎn)tT，稱為T的根結(jié)點(diǎn)； 其余的結(jié)點(diǎn)T-t被分割成m0個(gè)不相交的有窮子集T1-Tm，其中每個(gè)這樣的子集Ti(im)本身又是一棵樹， 稱為根結(jié)點(diǎn)的子樹。 由此可見， 樹的定義是一個(gè)遞歸定義。,圖 8.2 樹的示意圖,圖8.2所示是一棵具有14個(gè)結(jié)點(diǎn)的樹T=A，B，N。 其中，A為T的根結(jié)點(diǎn)；其余結(jié)點(diǎn)

4、T-A被分割成三個(gè)不相交的子集T1=B, E, F, K, L， T2=C, G, H, I, M，N， T3=D，J。 T1、T2、T3都是T的子樹。其中，T1的根結(jié)點(diǎn)為B，其余結(jié)點(diǎn)T-B又分為兩個(gè)不相交的子集T11=E，T12=F, K, L，它們都是T1的子樹。T12的根結(jié)點(diǎn)為F，并且包含兩棵結(jié)點(diǎn)數(shù)為1的子樹， T11的根結(jié)點(diǎn)為E，沒有子樹。,在一棵樹中，一個(gè)結(jié)點(diǎn)被定義為其子樹的根結(jié)點(diǎn)的父結(jié)點(diǎn)，而其子樹的根結(jié)點(diǎn)就是它的子女結(jié)點(diǎn)。如在圖8.2中，A為B、 C、D的父結(jié)點(diǎn)，B、C、D則為A的子女結(jié)點(diǎn)；而B又為E和F的父結(jié)點(diǎn)。 從定義可以看出， 樹結(jié)構(gòu)具有以下特點(diǎn)： 有且僅有根結(jié)點(diǎn)沒有父結(jié)點(diǎn)；

5、 除根結(jié)點(diǎn)外， 其余所有結(jié)點(diǎn)有且僅有一個(gè)父結(jié)點(diǎn)； 包括根結(jié)點(diǎn)在內(nèi)，每個(gè)結(jié)點(diǎn)可以有多個(gè)子女結(jié)點(diǎn)。總而言之，樹的數(shù)據(jù)元素之間存在著一對(duì)多的關(guān)系。,8.1.2 樹的邏輯表示,1. 樹形表示法 如圖8.2所示，樹形結(jié)構(gòu)被形象地表示為一棵倒置的、樹根在上、樹葉在下的樹。樹的每個(gè)結(jié)點(diǎn)都用一個(gè)圓圈表示，圓圈內(nèi)的符號(hào)代表該結(jié)中的數(shù)據(jù)，結(jié)點(diǎn)之間的關(guān)系通過連線表示。連線上方的結(jié)點(diǎn)為連線下方的結(jié)點(diǎn)的父結(jié)點(diǎn)，而連線下方的結(jié)點(diǎn)則為連線上方結(jié)點(diǎn)的子女結(jié)點(diǎn)。這種表示方法形象、直觀，大多數(shù)書中都采用這種方法。,2. 文氏圖表示法 文氏圖表示法也稱集合圖表示法，其中每一個(gè)圓形對(duì)應(yīng)著一棵樹，圓內(nèi)包含根結(jié)點(diǎn)和子樹。圖8.2所示的以

6、B為根結(jié)點(diǎn)的子樹為例， 其文氏圖表示法如圖8.3(a)所示。,圖 8.3 樹的邏輯表示方法 (a) 文氏圖表示法； (b) 凹入表示法； (c) 嵌套括號(hào)表示法,3. 凹入表示法 凹入表示法中的每個(gè)條形對(duì)應(yīng)著一個(gè)樹根，子樹的樹根對(duì)應(yīng)的條形較短，并在其直接前驅(qū)對(duì)應(yīng)的條形之下，圖8.3(a)所示的子樹若采用凹入表示法，則如圖8.3(b)所示。 4. 嵌套括號(hào)表示法 嵌套括號(hào)表示法也稱為廣義表表示法，每棵樹的根可作為由子樹構(gòu)成的表的名字，放在表的左邊，如圖8.3(c)所示。,8.1.3 基本術(shù)語 1. 結(jié)點(diǎn)的度和樹的度 每個(gè)結(jié)點(diǎn)具有的子樹數(shù)或者說后繼結(jié)點(diǎn)數(shù)被定義為該結(jié)點(diǎn)的度(degree)。所有結(jié)點(diǎn)

7、的度的最大值被定義為該樹的度。如在圖8.2的樹T中，B、F、H結(jié)點(diǎn)的度為2，A、C結(jié)點(diǎn)的度均為3， D結(jié)點(diǎn)的度為1，其余結(jié)點(diǎn)的度均為0。因結(jié)點(diǎn)中度最大的為3， 所以樹T的度為3。,2. 分支結(jié)點(diǎn)和葉結(jié)點(diǎn) 度大于0的結(jié)點(diǎn)稱作分支結(jié)點(diǎn)或非終端結(jié)點(diǎn)；度等于0的結(jié)點(diǎn)稱作葉結(jié)點(diǎn)或終端結(jié)點(diǎn)。在分支結(jié)點(diǎn)中，又把度為1的結(jié)點(diǎn)叫做單分支結(jié)點(diǎn)， 度為2的結(jié)點(diǎn)叫做雙分支結(jié)點(diǎn)，以此類推。如在圖8.2的樹T中，A、 B、 C、 D、 F、 H都是分支結(jié)點(diǎn)， E、 K、 L、 G、 M、 N、 I、 J都是葉結(jié)點(diǎn)。在分支結(jié)點(diǎn)中， D為單分支結(jié)點(diǎn)， B、 F、 H分別為雙分支結(jié)點(diǎn)，A、C為三分支結(jié)點(diǎn)。,3. 兒子結(jié)點(diǎn)、 雙

8、親結(jié)點(diǎn)和兄弟結(jié)點(diǎn) 每個(gè)結(jié)點(diǎn)的子樹的根，或者說每個(gè)結(jié)點(diǎn)的后繼，被習(xí)慣地稱作該結(jié)點(diǎn)的兒子或孩子(child)，相應(yīng)地，該結(jié)點(diǎn)被稱作兒子結(jié)點(diǎn)的雙親。 具有同一雙親的孩子互稱兄弟(sibiling)。 每個(gè)結(jié)點(diǎn)的所有子樹中的結(jié)點(diǎn)被稱作該結(jié)點(diǎn)的子孫。每個(gè)結(jié)點(diǎn)的祖先被定義為從樹根結(jié)點(diǎn)到達(dá)該結(jié)點(diǎn)的路徑上經(jīng)過的所有結(jié)點(diǎn)。如在圖8.2的樹T中， B結(jié)點(diǎn)的孩子為E、 F結(jié)點(diǎn)，雙親為A結(jié)點(diǎn)；E、F互為兄弟； B結(jié)點(diǎn)的子孫為E、F、K、L結(jié)點(diǎn)。I結(jié)點(diǎn)的祖先為A、C結(jié)點(diǎn)。對(duì)于樹T中的其他結(jié)點(diǎn)亦可進(jìn)行同樣的分析。由孩子結(jié)點(diǎn)和雙親結(jié)點(diǎn)的定義及樹結(jié)構(gòu)的特點(diǎn)可知：在一棵樹中，根結(jié)點(diǎn)沒有雙親結(jié)點(diǎn)， 葉結(jié)點(diǎn)沒有兒子結(jié)點(diǎn)。如在圖8.

9、2的樹T中，A結(jié)點(diǎn)沒有雙親結(jié)點(diǎn)， E、K、L等結(jié)點(diǎn)沒有兒子結(jié)點(diǎn)。 ,4. 結(jié)點(diǎn)的層數(shù)和樹的高度 樹既是一種遞歸結(jié)構(gòu)，也是一種層次結(jié)構(gòu)。 樹中的每個(gè)結(jié)點(diǎn)都處在一定的層次上。結(jié)點(diǎn)的層數(shù)(level)從樹根開始定義， 根結(jié)點(diǎn)為第一層，它的孩子結(jié)點(diǎn)為第二層，以此類推。樹中結(jié)點(diǎn)的最大層數(shù)稱為樹的深度(depth)或高度(height)。如在圖8.2的樹T中， A結(jié)點(diǎn)處于第一層，B、 C、 D結(jié)點(diǎn)處于第二層， E、 F、 G、 H、 I、 J結(jié)點(diǎn)處于第三層， K、 L、 M、 N結(jié)點(diǎn)處于第四層。 K、 L、 M、 N結(jié)點(diǎn)所處的第四層為樹T中結(jié)點(diǎn)的最大層數(shù)， 所以樹T的高度為4。,5. 有序樹和無序樹 若樹

10、中各結(jié)點(diǎn)的子樹是按照一定的次序從左向右安排的， 則稱之為有序樹，否則稱之為無序樹。如圖8.4中的兩棵樹， 若看作無序樹，則是相同的；但若看作有序樹，則不同。 因?yàn)楦Y(jié)點(diǎn)A的兩棵子樹的次序不同。又如，對(duì)于一棵反映父子關(guān)系的家族樹，若兄弟結(jié)點(diǎn)之間是按照排行大小有序的， 則它是一棵有序樹。,圖 8.4 兩棵不同的有序樹,6. 森林 森林是m(m0)棵互不相交的樹的集合。例如，對(duì)于樹中每個(gè)分支結(jié)點(diǎn)來說， 其子樹的集合就是森林。如圖8.2的樹T中， 由A結(jié)點(diǎn)的子樹所構(gòu)成的森林為T1, T2, T3，由B結(jié)點(diǎn)的子樹所構(gòu)成的森林為T11, T12。,8.1.4 樹的基本操作 設(shè)T為一棵樹， 則T的基本操作主

11、要有以下幾種： (1) initiate( )： 初始化操作， 置T為空樹。 (2) parent(x)： 求樹T中結(jié)點(diǎn)x的雙親結(jié)點(diǎn)。 (3) child(x, i)： 求樹T中結(jié)點(diǎn)x的第i個(gè)孩子結(jié)點(diǎn)。 (4) right-sibling(x)： 求樹T中結(jié)點(diǎn)x右邊的兄弟結(jié)點(diǎn)。 (5) insert-child(y, i, x)： 在T中插入以結(jié)點(diǎn)x為根的樹作為結(jié)點(diǎn)y的第i個(gè)子樹。 (6) del-child(x, i)： 在T中刪除結(jié)點(diǎn)x的第i棵子樹。 (7) traverse( )： 遍歷操作。 按某個(gè)次序依次訪問樹T中各結(jié)點(diǎn)。,8.2 二 叉 樹,8.2.1 定義 二叉樹的遞歸定義為：二

12、叉樹或者是一棵空樹， 或者是一棵由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的左子樹和右子樹所組成的非空樹， 左子樹和右子樹又同樣都是二叉樹。二叉樹的特點(diǎn)是每個(gè)結(jié)點(diǎn)最多只有兩個(gè)子女。即，在二叉樹中，不存在度大于2的結(jié)點(diǎn)。 二叉樹的子樹有左右之分， 左右子樹的順序不能顛倒。因此， 根據(jù)該定義，二叉樹有如圖8.5所示的五種基本形態(tài)。其中， （a）為空二叉樹，（b）為只有一個(gè)根結(jié)點(diǎn)的二叉樹，（c）為只有左子樹的二叉樹，（d）為只有右子樹的二叉樹，（e）為左、 右子樹均為非空的二叉樹。,圖 8.5 二叉樹的基本形態(tài),8.2.2 基本性質(zhì) 二叉樹有一些特殊的性質(zhì)，簡單歸納如下： (1) 任意非空二叉樹中，若葉結(jié)點(diǎn)的數(shù)目為

13、n0，度為2的結(jié)點(diǎn)數(shù)目為n2， 則有關(guān)系：n0=n2+1 證明： 設(shè)度為1的結(jié)點(diǎn)數(shù)目為n1， 則二叉樹的結(jié)點(diǎn)總數(shù)n為 n=n0+n1+n2,由于二叉樹中除根結(jié)點(diǎn)以外，每個(gè)結(jié)點(diǎn)都有一個(gè)分支指向它，因此二叉樹中總的分支數(shù)Z為 Z=n-1 所有這些分支均是由度為1或的2的結(jié)點(diǎn)發(fā)出的， 而每個(gè)度為1的結(jié)點(diǎn)發(fā)出一個(gè)分支，每個(gè)度為2的結(jié)點(diǎn)發(fā)出兩個(gè)分支。 于是有 Z= n1+2n2 由以上三式可推得： n0=n2+1,(2) 一棵非空二叉樹的第i層最多有2i-1個(gè)結(jié)點(diǎn)(i1)。 該性質(zhì)可用歸納法證明： 當(dāng)i=1時(shí)，二叉樹只有一個(gè)結(jié)點(diǎn)，即二叉樹的根結(jié)點(diǎn)。顯然性質(zhì)(1)成立。 假設(shè)對(duì)所有k(1ki-1)性質(zhì)(1

14、)成立，即第k 層上最多有2k-1個(gè)結(jié)點(diǎn)。面證明當(dāng)k=i 時(shí)性質(zhì)（2）也成立。 根據(jù)歸納假設(shè)，第i-1層上最多有2i-2個(gè)結(jié)點(diǎn)，又由于每個(gè)結(jié)點(diǎn)最多有2棵子樹，所以第i層的結(jié)點(diǎn)數(shù)目最多是第i-1層上最大結(jié)點(diǎn)數(shù)目的2倍，即有22i-2=2i-1。性質(zhì)（2）得證。,(3) 高度為k的二叉樹最多有2k-1個(gè)結(jié)點(diǎn)(k1)。 顯然，高度為k的二叉樹只有在每一層都達(dá)到最大結(jié)點(diǎn)數(shù)時(shí)， 整個(gè)二叉樹的結(jié)點(diǎn)數(shù)才能達(dá)到最大。即當(dāng)每層的結(jié)點(diǎn)數(shù)目都達(dá)到該層的最大結(jié)點(diǎn)數(shù)2i-1時(shí)（性質(zhì)(2)），對(duì)應(yīng)的二叉樹的結(jié)點(diǎn)數(shù)目取得最大值：,故性質(zhì)(3)得證。 若一棵二叉樹高度為k且有2k-1個(gè)結(jié)點(diǎn)，則稱該二叉樹為滿二叉樹。滿二叉樹的

15、特點(diǎn)就是每層的結(jié)點(diǎn)數(shù)目都達(dá)到該層的最大結(jié)點(diǎn)數(shù)。圖8.6(a) 所示的是一棵高度為4的滿二叉樹。,圖 8.6 滿二叉樹與完全二叉樹 (a) 滿二叉樹； (b) 完全二叉樹,若在一棵二叉樹中，除最后一層外，其余層都是滿的（結(jié)點(diǎn)數(shù)目達(dá)到該層的最大結(jié)點(diǎn)數(shù)），并且最后一層或者是滿的，或者是在右邊缺少連續(xù)若干個(gè)結(jié)點(diǎn)， 則稱此樹為完全二叉樹。滿二叉樹是完全二叉樹的特例。圖8.6(b)為一棵高度為4的完全二叉樹， 與等高度的滿二叉樹相比，它在最后一層的右邊缺少了5個(gè)結(jié)點(diǎn)。 由圖8.6還可看出， 對(duì)于一棵完全二叉樹，若按照高度相同的滿二叉樹的同樣方法對(duì)其結(jié)點(diǎn)進(jìn)行編號(hào)，則其每個(gè)結(jié)點(diǎn)的編號(hào)都與滿二叉樹的結(jié)點(diǎn)編號(hào)相同

16、。 完全二叉樹有如下特點(diǎn)： 葉結(jié)點(diǎn)僅在層數(shù)最大的兩層上出現(xiàn)； 對(duì)其中任意結(jié)點(diǎn)，若右子樹的高度為kr，則左子樹的高度為kr或kr+1。 完全二叉樹有(4)、 (5)兩個(gè)重要性質(zhì)：,(4) 具有n 0個(gè)結(jié)點(diǎn)的完全二叉樹的高度k=log2n+1。 符號(hào) 表示取不超過符號(hào)內(nèi)的數(shù)字的最大的整數(shù)。 性質(zhì)(4)證明如下： 根據(jù)完全二叉樹定義以及二叉樹的性質(zhì)(3)，有 2k-11 n2k1 或 2k-1n2k 由上式可推出 k1log2nk 由于k為正整數(shù)，因此 k=log2n+1,(5) 若對(duì)具有n個(gè)結(jié)點(diǎn)的完全二叉樹按層次從上到下，每層從左至右的規(guī)則對(duì)結(jié)點(diǎn)編號(hào)，則序號(hào)為i的結(jié)點(diǎn)具有以下性質(zhì)： 若i 1，則序

17、號(hào)為i的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的序號(hào)為i/2； 當(dāng)i=1時(shí)， 則對(duì)應(yīng)結(jié)點(diǎn)為二叉樹的根結(jié)點(diǎn)，沒有雙親結(jié)點(diǎn)。 若2in，則序號(hào)為i的結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的序號(hào)為2i； 若2i n，則序號(hào)為i的結(jié)點(diǎn)無左孩子。 若2i1n，則序號(hào)為i的結(jié)點(diǎn)的右孩子結(jié)點(diǎn)的序號(hào)為2i+1；若2i+1n，則序號(hào)為i的結(jié)點(diǎn)無右孩子。 該性質(zhì)可采用歸納法證明，此處從略。通過具體實(shí)例也可以驗(yàn)證性質(zhì)（5）的正確性。,8.2.3 存儲(chǔ)結(jié)構(gòu),1. 數(shù)組表示 當(dāng)在數(shù)據(jù)處理過程中，二叉樹的大小和形態(tài)不發(fā)生大的變化時(shí)，可以采用數(shù)組方式來表示二叉樹的抽象數(shù)據(jù)類型。 使用數(shù)組方式存儲(chǔ)二叉樹結(jié)構(gòu)，就是用一組連續(xù)的存儲(chǔ)單元存儲(chǔ)二叉樹的數(shù)據(jù)元素。為了反映各結(jié)點(diǎn)在

18、二叉樹中的位置及相互關(guān)系， 必須適當(dāng)安排各結(jié)點(diǎn)的存儲(chǔ)次序。 設(shè)有一棵完全二叉樹，對(duì)它所有的結(jié)點(diǎn)按照層次次序自頂向下，同一層自左向右順序編號(hào)1, , n，就得到一個(gè)結(jié)點(diǎn)的順序（線性）序列。按這個(gè)線性序列，可把這棵完全二叉樹放在一個(gè)一維數(shù)組中，如圖8.7(a)所示。,圖 8.7 二叉樹的數(shù)組表示 (a) 完全二叉樹； (b) 一般二叉樹,設(shè)有一棵一般的二叉樹，需要將它存放在一個(gè)一維數(shù)組中。為了能夠簡單地找到二叉樹中任意一個(gè)結(jié)點(diǎn)的上下左右的關(guān)系，必須仿照滿二叉樹的編號(hào)方式對(duì)其結(jié)點(diǎn)進(jìn)行編號(hào)， 然后按編號(hào)存放到向量中去，如圖8.7(b)所示。編號(hào)時(shí)，如遇到空子樹， 應(yīng)在編號(hào)時(shí)假定有此子樹進(jìn)行編號(hào)，而在順

19、序存儲(chǔ)時(shí)當(dāng)作有此子樹那樣把位置留出來。這樣才能反映二叉樹結(jié)點(diǎn)之間的相互關(guān)系，并由其存儲(chǔ)位置找到它的雙親、兒子、兄弟結(jié)點(diǎn)的位置，但是，這樣做有可能會(huì)消耗大量的存儲(chǔ)空間。例如，圖8.7(b)給出的高度為4的二叉樹，按照這種方式存儲(chǔ)時(shí)，要求一個(gè)可存放15個(gè)結(jié)點(diǎn)的一維數(shù)組，但其結(jié)點(diǎn)數(shù)只有8個(gè)。除此之外，采用數(shù)組順序地存儲(chǔ)二叉樹將會(huì)使二叉樹插入、刪除操作的實(shí)現(xiàn)變得十分不方便。因此， 對(duì)于二叉樹來說，更合適的還是采用鏈?zhǔn)酱鎯?chǔ)方式。,2. 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是指用一個(gè)鏈表來表示一棵二叉樹。通常有下面兩種形式。 1) 二叉鏈結(jié)構(gòu) 在二叉鏈結(jié)構(gòu)中，鏈表的每個(gè)鏈結(jié)點(diǎn)由三個(gè)域組成。除了數(shù)據(jù)域data

20、用來存結(jié)點(diǎn)的數(shù)據(jù)信息外，還有兩個(gè)指針域lchild與rchild分別用來存放指向該結(jié)點(diǎn)左子樹與右子樹的指針，如圖8.8(a)所示。,圖 8.8 二叉樹鏈?zhǔn)酱鎯?chǔ)鏈結(jié)點(diǎn)構(gòu)造 (a) 二叉鏈表； (b) 三叉鏈表,(a),(b),圖 8.9 二叉樹及其鏈表表示 (a) 二叉樹； (b) 二叉鏈表； (c) 三叉鏈表,當(dāng)左子樹或右子樹不存在時(shí)， 相應(yīng)的指針域值為空（用符號(hào)或nil表示）。圖8.9(b)為圖8.9(a)二叉樹的二叉鏈表示。 我們可以給出二叉鏈表鏈結(jié)點(diǎn)數(shù)據(jù)類型描述如下： type Tlink = Tnode; Tnode = record data: elemtp; lchild, rch

21、ild: Tlink; end;,其中，Tnode為二叉鏈表鏈結(jié)點(diǎn)類型名，Tlink為指向鏈結(jié)點(diǎn)的指針類型， elemtp為結(jié)點(diǎn)數(shù)據(jù)的類型。 那么，如何根據(jù)輸入的數(shù)據(jù)來建立二叉鏈表呢？我們可以采取以下的方法：首先建立二叉樹根結(jié)點(diǎn)所對(duì)應(yīng)的鏈結(jié)點(diǎn)，然后再從這個(gè)鏈結(jié)點(diǎn)出發(fā)，分別建立根結(jié)點(diǎn)的左子樹與右子樹。 假設(shè)二叉樹結(jié)點(diǎn)數(shù)據(jù)按照類似圖8.7(b)的方式存儲(chǔ)在一個(gè)數(shù)組中， 則我們首先創(chuàng)建一個(gè)鏈結(jié)點(diǎn)，在其數(shù)據(jù)域中存放數(shù)組中的第一個(gè)元素， 這樣就建立了二叉樹的根結(jié)點(diǎn)；接下來，需要分別建立根結(jié)點(diǎn)的左子樹與右子樹，而建立子樹又必須先建立子樹的根結(jié)點(diǎn)。顯然，這個(gè)過程可以用遞歸過程來描述。,設(shè)二叉樹結(jié)點(diǎn)數(shù)據(jù)類型為

22、字符型，各結(jié)點(diǎn)數(shù)據(jù)按照二叉樹的數(shù)組表示方式存儲(chǔ)在字符串str中，字符串變量為s: string、 整型變量為n: integer及指針為root: Tlink， 它們已在外部說明， 則二叉鏈表的建立過程可表示為procedure build(str: string)； 其功能為根據(jù)字符串str的內(nèi)容建立二叉樹的二叉鏈表，并讓root指向這個(gè)二叉鏈表。 其處理過程為：以1為參數(shù)調(diào)用遞歸子函數(shù)function build0 (i: integer): Tlink完成二叉鏈表的建立，并讓root指向該鏈表。遞歸子函數(shù)function build0 (i: integer): Tlink的功能為：以字

23、符串str的第i個(gè)元素為二叉樹的根結(jié)點(diǎn)遞歸地建立二叉鏈表，并返回指向該鏈表的指針。 其處理過程為：,(1) 若i小于字符串的長度， 且字符串的第i個(gè)元素為非空格符， 則創(chuàng)建一個(gè)鏈結(jié)點(diǎn)，在其數(shù)據(jù)域中存放字符串的第i個(gè)元素； (2) 以2*i為參數(shù)，調(diào)用build0建立這個(gè)結(jié)點(diǎn)的左子樹； (3) 以2*i+1為參數(shù)，調(diào)用build0建立這個(gè)結(jié)點(diǎn)的右子樹。 這里用到了二叉樹的性質(zhì)(5)。即n個(gè)結(jié)點(diǎn)的完全二叉樹按層次從上到下，同一層中從左至右的規(guī)則對(duì)結(jié)點(diǎn)編號(hào)時(shí)，序號(hào)為i的結(jié)點(diǎn)若有左子樹結(jié)點(diǎn)，則其結(jié)點(diǎn)序號(hào)為2i；若有右子樹結(jié)點(diǎn)， 則其結(jié)點(diǎn)序號(hào)為2i1。由于二叉樹的數(shù)組表示采取了與完全二叉樹相同的標(biāo)號(hào)規(guī)則

24、，故通過父結(jié)點(diǎn)的序號(hào)可推出兒子結(jié)點(diǎn)的序號(hào)。 以下是程序清單：,procedure build(str: string); 根據(jù)str中的內(nèi)容建立二叉鏈表 begin s:= str; n:= length(s); root:= build0(1); 調(diào)用遞歸子過程 end; function build0(i: integer): Tlink; 以字符串str中第i個(gè)元素為 var p: Tlink; l, r : integer; 二叉樹的根結(jié)點(diǎn)建立二叉鏈表,begin if (i ) then begin new(p); p.data:=si; l:=2*i; r:=2*i+1; p.lc

25、hild:= build0(l); p.rchild:= build0(r); result:= p; end else result:=nil; end;,2) 三叉鏈結(jié)構(gòu) 使用二叉鏈表這種存儲(chǔ)結(jié)構(gòu)，可以很方便地根據(jù)結(jié)點(diǎn)指針lchild與rchild找到二叉樹中結(jié)點(diǎn)的左孩子與右孩子，但要找到它的雙親卻不太方便。 為了便于查找任一結(jié)點(diǎn)的雙親結(jié)點(diǎn)，可以在二叉鏈表鏈結(jié)點(diǎn)中再增加一個(gè)雙親指針域，如圖8.8(b)所示。 這種鏈表被稱為三叉鏈表，圖8.9(c)為圖8.9(a)二叉樹的三叉鏈表示。 類似地， 我們給出三叉鏈表鏈結(jié)點(diǎn)數(shù)據(jù)類型描述如下： type Tlink = Tnode; Tnode =

26、record data: elemtp; parent, lchild, rchild: Tlink; end; ,8.2.4 二叉樹的遍歷 二叉樹的遍歷是指按照一定次序訪問樹中所有結(jié)點(diǎn)， 并且每個(gè)結(jié)點(diǎn)僅被訪問一次的過程。 所謂訪問某結(jié)點(diǎn)可以理解為打印該結(jié)點(diǎn)的數(shù)據(jù)信息。但在實(shí)際處理過程中，訪問某個(gè)結(jié)點(diǎn)并不一定就是如此。例如，修改結(jié)點(diǎn)的數(shù)據(jù)，或者判斷結(jié)點(diǎn)是不是滿足條件的結(jié)點(diǎn)等都可認(rèn)為是對(duì)結(jié)點(diǎn)的訪問。,根據(jù)二叉樹的遞歸定義，一棵非空二叉樹由根結(jié)點(diǎn)、左子樹和右子樹組成，因此，遍歷一棵非空二叉樹的問題可分解為三個(gè)子問題，即訪問根結(jié)點(diǎn)、遍歷左子樹和遍歷右子樹。若分別用D、L和R表示上述三個(gè)子問題，則有D

27、LR、 LDR、 LRD、 DRL、 RDL、 RLD六種次序的遍歷方案。其中前三種方案都是先遍歷左子樹，后遍歷右子樹，而后三種則相反，都是先遍歷右子樹，后遍歷左子樹。由于兩者對(duì)稱，故我們只討論前三種次序的遍歷方案。,在遍歷方案DLR中， 因?yàn)樵L問根結(jié)點(diǎn)的操作在遍歷左、 右子樹之前，故稱之為前序遍歷(preorder)或先根遍歷。類似地， 在LDR方案中， 訪問根結(jié)點(diǎn)的操作在遍歷左子樹之后和遍歷右子樹之前，故稱之為中序(inorder)遍歷或中根遍歷; 在LRD方案中，訪問根結(jié)點(diǎn)的操作在遍歷左、右子樹之后，故稱之為后序(postorder)遍歷或后根遍歷。 顯然，遍歷左、右子樹的問題仍然是遍歷

28、二叉樹的問題，所以二叉樹的這三種遍歷方式可以用遞歸算法實(shí)現(xiàn)。,1. 遞歸算法 1) 中序遍歷(LDR) 中序遍歷的過程是， 若二叉樹不為空， 則 (1) 以中序遍歷方式遍歷根結(jié)點(diǎn)的左子樹； (2) 訪問根結(jié)點(diǎn)； (3) 以中序遍歷方式遍歷根結(jié)點(diǎn)的右子樹。,因此，中序遍歷過程可用遞歸算法描述。設(shè)p為指向二叉樹根結(jié)點(diǎn)的指針，則中序遍歷過程可表示為procedure inorder0(p: Tlink)，其功能為對(duì)p所指的二叉樹進(jìn)行中序遍歷， 輸出中序遍歷的結(jié)點(diǎn)序列，其處理過程為： 若p非空， 則 (1) 中序遍歷p所指結(jié)點(diǎn)的左子樹； (2) 顯示p所指的結(jié)點(diǎn)數(shù)據(jù)； (3) 中序遍歷p所指結(jié)點(diǎn)的右子

29、樹。,這里過程名以0結(jié)尾是為了區(qū)別下面相同功能的非遞歸過程。以下為程序清單： procedure inorder0(p: Tlink); 中序遍歷以p為根結(jié)點(diǎn)的二叉樹 begin if p nil then begin inorder0(p.lchild); 中序遍歷p的左子樹 顯示p.data; 訪問p所指的根結(jié)點(diǎn)數(shù)據(jù) inorder0(p.rchild); 中序遍歷p的右子樹 end; end; ,圖 8.10 表達(dá)式語法樹,圖 8.11 二叉樹中序遍歷遞歸執(zhí)行過程,2) 前序遍歷(DLR) 二叉樹前序遍歷的過程是， 若二叉樹不為空， 則 (1) 訪問根結(jié)點(diǎn)； (2) 以前序遍歷方式遍歷根

30、結(jié)點(diǎn)的左子樹； (3) 以前序遍歷方式遍歷根結(jié)點(diǎn)的右子樹。 設(shè)p為指向二叉樹根結(jié)點(diǎn)的指針， 則前序遍歷過程可表示為procedure preorder0(p: Tlink)，其功能為對(duì)p所指的二叉樹進(jìn)行前序遍歷， 輸出前序遍歷的結(jié)點(diǎn)序列，其處理過程為：,若p非空， 則 顯示p所指的結(jié)點(diǎn)數(shù)據(jù)； 前序遍歷p所指結(jié)點(diǎn)的左子樹； 前序遍歷p所指結(jié)點(diǎn)的右子樹。,以下為程序清單： procedure preorder0(p: Tlink); 前序遍歷以p為根結(jié)點(diǎn)的二叉樹 begin if p nil then begin 顯示p.data; 訪問p所指的根結(jié)點(diǎn)數(shù)據(jù) preorder0(p.lchild);

31、 前序遍歷p的左子樹 preorder0(p.rchild); 前序遍歷p的右子樹 end; end;,3) 后序遍歷(LRD) 后序遍歷的過程是， 若二叉樹不為空， 則 (1) 以后序遍歷方式遍歷根結(jié)點(diǎn)的左子樹； (2) 以后序遍歷方式遍歷根結(jié)點(diǎn)的右子樹； (3) 訪問根結(jié)點(diǎn)。,設(shè)p為指向二叉樹根結(jié)點(diǎn)的指針，則后序遍歷過程可表示為procedure postoder0(p: Tlink)， 其功能為對(duì)p所指的二叉樹進(jìn)行后序遍歷， 輸出后序遍歷的結(jié)點(diǎn)序列，其處理過程為： 若p非空， 則 后序遍歷p所指二叉樹的左子樹； 后序遍歷p所指二叉樹的右子樹； 顯示p所指的結(jié)點(diǎn)數(shù)據(jù)。,以下為程序清單： p

32、rocedure postorder0(p: Tlink); 后序遍歷以p為根結(jié)點(diǎn)的二叉樹 begin if p nil then do begin postorder0(p.lchild); 后序遍歷p的左子樹 postorder0(p.rchild); 后序遍歷p的右子樹 顯示p.data; 訪問p所指的根結(jié)點(diǎn)數(shù)據(jù) end; end;,對(duì)于圖8.10所示的二叉樹，按后序遍歷方式得到的表達(dá)式為a b * c。這種由后序遍歷所得的表達(dá)式被稱為后綴表達(dá)式，也常被稱為逆波蘭式。 從上面給出的三種不同次序的遍歷二叉樹的遞歸算法可知， 它們只是訪問根結(jié)點(diǎn)及遍歷左子樹、遍歷右子樹的先后次序不同。 如果把

33、訪問根結(jié)點(diǎn)這個(gè)不涉及遞歸的語句拋開，則三個(gè)遞歸算法走過的路線是一樣的。圖8.12給出了遞歸遍歷時(shí)走過的路線，其中，向下的箭頭表示更深一層的遞歸調(diào)用，向上的箭頭表示從遞歸調(diào)用退出。,圖 8.12 遍歷的遞歸執(zhí)行路線,三種遞歸遍歷算法的差別在于：前序遍歷是每進(jìn)入一層遞歸調(diào)用時(shí)先訪問根結(jié)點(diǎn)，然后再依次向它的左、右子樹執(zhí)行遞歸調(diào)用；中序遍歷是在執(zhí)行完左子樹遞歸調(diào)用后再訪問根結(jié)點(diǎn)， 然后向它的右子樹遞歸調(diào)用；后序遍歷則是在從右子樹遞歸調(diào)用退出后訪問根結(jié)點(diǎn)。,2. 非遞歸算法 以上給出了二叉樹遍歷的遞歸算法。遞歸算法形式簡潔， 可讀性好，而且其正確性容易得到證明。因此，利用遞歸算法可以給程序的編制和調(diào)試帶

34、來很大的方便。然而，遞歸調(diào)用比非遞歸調(diào)用消耗的時(shí)間與存儲(chǔ)空間多，運(yùn)行的效率較低。 實(shí)際上，所有的遞歸算法都可轉(zhuǎn)化成相應(yīng)的非遞歸算法。一般說來， 將遞歸算法改成相應(yīng)的非遞歸算法需要一個(gè)棧來記錄調(diào)用返回的路徑。通過分析遞歸調(diào)用的執(zhí)行過程，并觀察棧的變化就可得到相應(yīng)的非遞歸算法。,利用中序遍歷的遞歸算法研究圖8.12 所示的二叉樹可知， 最先訪問的結(jié)點(diǎn)是沿二叉鏈的左子樹鏈往下走的最后一個(gè)結(jié)點(diǎn)。 在走向這個(gè)結(jié)點(diǎn)的過程中，沿途經(jīng)過的結(jié)點(diǎn)必須被壓入棧中儲(chǔ)存起來。在訪問完該結(jié)點(diǎn)后，位于棧頂?shù)脑卣檬瞧潆p親結(jié)點(diǎn)。 將這個(gè)雙親結(jié)點(diǎn)從棧退出后，對(duì)其進(jìn)行訪問， 然后再向其右子樹方向走。 若該右子樹非空，則又重復(fù)這

35、一過程。因此， 為實(shí)現(xiàn)二叉樹的中序遍歷， 非遞歸算法中設(shè)立了一個(gè)棧s來記錄遍歷返回的路徑。s被說明成一個(gè)順序棧對(duì)象s: Tsxz，順序棧的類定義已在第 2 章中給出，其中，順序棧中存儲(chǔ)的元素為指向二叉鏈結(jié)點(diǎn)的指針：,type sqstktp = record elem: array 1.max of Tlink; top: 0.max; end;,設(shè)二叉樹的根結(jié)點(diǎn)由指針p: Tlink指示，棧s: Tsxz已在過程外部被說明并被初始化，則非遞歸中序遍歷二叉樹的過程可表示為procedure inorder(p: Tlink)， 其功能為對(duì)p所指的二叉樹進(jìn)行非遞歸的中序遍歷， 輸出中序遍歷的結(jié)點(diǎn)

36、序列， 其處理過程為： (1) 當(dāng)p非空時(shí)，將p所指結(jié)點(diǎn)的地址進(jìn)棧， 并將p指向該結(jié)點(diǎn)的左子樹； (2) 當(dāng)p為空時(shí)， 彈出棧頂元素， 顯示其結(jié)點(diǎn)數(shù)據(jù)， 并將p指向該結(jié)點(diǎn)的右子樹； (3) 重復(fù)過程(1)、 (2)， 直至?？涨襭也為空。,以下是程序清單： procedure inorder(p: Tlink); 非遞歸中序遍歷以p為根結(jié)點(diǎn)的二叉樹 begin if p nil then do begin s.makeempty; 棧清空 while (p nil) and (s.empty = false) do begin while p nil do,begin s.push(p);將p

37、所指的結(jié)點(diǎn)壓入棧 p:=p.lchild;將p指向左子樹 end; p:=s.pop; 取棧頂元素 顯示p.data; 訪問p所指的結(jié)點(diǎn)數(shù)據(jù) p:=p.rchild; end; end; end; ,圖 8.13 非遞歸中序遍歷二叉樹時(shí)棧s狀態(tài)的變化,二叉樹的前序遍歷、中序遍歷與后序遍歷是最常用的三種遍歷方式，除此之外，有時(shí)也使用按層次的遍歷方式。 這種遍歷方式是先遍歷二叉樹第一層的結(jié)點(diǎn)，然后遍歷第二層的結(jié)點(diǎn)， 最后遍歷最下一層的結(jié)點(diǎn)； 對(duì)每一層的遍歷又按照從左至右的先后順序進(jìn)行。圖8.14顯示了按層次序遍歷時(shí)的結(jié)點(diǎn)訪問次序。 層次序遍歷不是一個(gè)遞歸過程，其算法的實(shí)現(xiàn)可參照第 9 章中有關(guān)圖的

38、廣度優(yōu)先搜索遍歷的算法。,圖 8.14 層次序遍歷的結(jié)點(diǎn)訪問順序,3. 二叉樹遍歷的應(yīng)用,1) 計(jì)算二叉樹結(jié)點(diǎn)個(gè)數(shù) 為了計(jì)算二叉樹的結(jié)點(diǎn)個(gè)數(shù)，可以遍歷根結(jié)點(diǎn)的左子樹和右子樹，分別計(jì)算出左子樹和右子樹的結(jié)點(diǎn)個(gè)數(shù)，然后把訪問根結(jié)點(diǎn)的語句改為相加語句：二叉樹根結(jié)點(diǎn)左子樹結(jié)點(diǎn)個(gè)數(shù)加上右子樹結(jié)點(diǎn)個(gè)數(shù)，再加上根結(jié)點(diǎn)數(shù)1，便得到整個(gè)二叉樹的結(jié)點(diǎn)個(gè)數(shù)。 設(shè)p: Tlink為指向二叉樹根結(jié)點(diǎn)的指針，則二叉樹結(jié)點(diǎn)個(gè)數(shù)的計(jì)算可表示為函數(shù)function node-number(p: Tlink): integer， 其功能為返回以p所指二叉樹的結(jié)點(diǎn)個(gè)數(shù)，其處理過程為：,(1) 求p所指二叉樹左子樹的結(jié)點(diǎn)個(gè)數(shù)n1；

39、(2) 求p所指二叉樹右子樹的結(jié)點(diǎn)個(gè)數(shù)n2； (3) 返回n1+n2+1。,程序清單如下： function node-number(p: Tlink): integer; begin if p = nil then result:=0 else result:= node-number(p.lchild)+ node-number(p.rchild)+1; end;,2) 計(jì)算二叉樹的高度 如果二叉樹為空，則高度為0； 否則先遞歸計(jì)算根結(jié)點(diǎn)左子樹的高度和右子樹的高度，再求出兩者中的最大者，并加1（增加根結(jié)點(diǎn)時(shí)高度加1），便得到整個(gè)二叉樹的高度。 設(shè)p: Tlink為指向二叉樹根結(jié)點(diǎn)的指針，

40、則二叉樹高度的計(jì)算可表示為函數(shù)function depth(p: Tlink): integer， 其功能為返回以p所指二叉樹的高度，其處理過程為： (1) 求p所指二叉樹左子樹的高度l1； (2) 求p所指二叉樹右子樹的高度l2； (3) 返回max(l1+l2)+1。,程序清單如下： function depth(p: Tlink): integer; begin if p = nil then result:=0 else result:= max(depth(p.lchild), depth(p.rchild)+1; end;,3) 判斷兩個(gè)二叉樹相等 利用二叉樹的前序遍歷，可實(shí)現(xiàn)判斷

41、兩個(gè)二叉樹是否相等的算法：首先比較兩個(gè)二叉樹根結(jié)點(diǎn)中的數(shù)據(jù)（相當(dāng)于訪問根結(jié)點(diǎn)），然后再比較左子樹和右子樹（依次訪問左子樹與右子樹）。若均相同， 則兩個(gè)二叉樹相等。 設(shè) p, t: Tlink分別為指向兩個(gè)二叉樹的指針， 則兩個(gè)二叉樹相等的判斷可表示為函數(shù)function equal(p, t: Tlink): boolean， 其功能為判斷p、t所指的二叉樹是否相等。,若相等，則返回true，否則返回false，其處理過程為： (1) 若p、t均為空，則返回true； (2) 若p、t均非空，且結(jié)點(diǎn)數(shù)據(jù)和左右子樹均相等，則返回true； (3) 否則返回false。,程序清單如下： funct

42、ion equal(p, t: Tlink): boolean; begin if (a = nil) and (t = nil) then result:= true else if (a nil) and (t nil) and (a.data = b.data) and (equal(a.lchild, t.lchild) and (equal(a.rchild, t.rchild) then result:=true else result:=false; end;,8.2.5 二叉樹的類定義 根據(jù)二叉樹的特點(diǎn)及有關(guān)樹的基本操作，我們可以給出以二叉鏈表為存儲(chǔ)結(jié)構(gòu)的二叉樹類定義如下：,t

43、ype Tnode = class private data: char; lchild, rchild: Tnode end; Trcs=class,private s: string; s用作建立二叉樹的輸入 n: integer; n為二叉樹的結(jié)點(diǎn)個(gè)數(shù) root: Tnode;root為二叉樹的根結(jié)點(diǎn)指針 function build0(i: integer): Tnode; 私有建樹函數(shù) procedure preorder0(p: Tnode); 私有前序遍歷過程,public procedure build(str: string); 根據(jù)字符串str的內(nèi)容建立二叉樹 proced

44、ure preorder; 前序遍歷二叉樹 procedure inorder; 中序遍歷二叉樹 procedure postorder; 后序遍歷二叉樹 procedure prnt; 顯示二叉樹 end; Implementation procedure Trcs. preorder;,begin preorder0(root); 調(diào)用私有前序遍歷過程 end; procedure Trcs. inorder; begin inorder0(root); 調(diào)用私有中序遍歷過程 end; procedure Trcs. postorder; begin postorder0(root); 調(diào)

45、用私有后序遍歷過程 end; ,注意，在上述類定義中，我們將二叉樹的結(jié)點(diǎn)也定義成類Tnode， 因此結(jié)點(diǎn)的指針類型即為Tnode，生成時(shí)要使用Tnode.create， 引用時(shí)也不必加“”符號(hào)。 另外，在這個(gè)類定義中，同時(shí)設(shè)置了私有和公有遍歷過程。 公有遍歷過程通過調(diào)用私有遍歷過程向外界提供服務(wù)，隱藏了二叉樹的私有數(shù)據(jù)root。過程build根據(jù)字符串str的內(nèi)容建立的二叉樹，建樹和遍歷的操作在前面已詳細(xì)討論過，二叉樹的顯示過程prnt可參見本章的演示程序。,8.3 線 索 二 叉 樹,8.3.1 二叉樹的線索化 當(dāng)以某種次序（前序、后序、中序）對(duì)二叉樹進(jìn)行遍歷后，可得到一個(gè)樹中所有結(jié)點(diǎn)組成的

46、序列，這個(gè)結(jié)點(diǎn)序列可以被看作為一個(gè)線性表。 在該線性表中， 除第一個(gè)結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)有且僅有一個(gè)前驅(qū)；除最后一個(gè)結(jié)點(diǎn)外， 每個(gè)結(jié)點(diǎn)有且僅有一個(gè)后繼。根據(jù)這個(gè)序列，可以找到二叉樹中某一個(gè)結(jié)點(diǎn)在這種次序下的前驅(qū)和后繼。在容易混淆的地方，還可以對(duì)序列中結(jié)點(diǎn)的前驅(qū)或后繼冠以某種遍歷次序的名稱。如把中序序列中結(jié)點(diǎn)的前驅(qū)稱作中序前驅(qū)，后繼稱作中序后繼等。,如果我們希望很快找到某一結(jié)點(diǎn)在某種次序下的前驅(qū)或后繼，但不想每次都對(duì)二叉樹遍歷一遍，那么就需要把每個(gè)結(jié)點(diǎn)的前驅(qū)和后繼信息記錄下來。比如，我們可在原來的二叉鏈表結(jié)點(diǎn)中增加一個(gè)前驅(qū)指針域(pre)和一個(gè)后繼指針域(suc)， 讓它們分別指向該結(jié)點(diǎn)在某種次序下

47、的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。圖8.15表示了加有中序前驅(qū)和后繼指針域的二叉鏈表。通過前驅(qū)和后繼指針域，可以很容易地查找任意一個(gè)結(jié)點(diǎn)的前驅(qū)和后繼，而無需遍歷二叉樹。,圖 8.15 增加了前驅(qū)和后繼指針域的二叉鏈表,一般說來，在一棵非完全二叉樹的二叉鏈結(jié)點(diǎn)中，許多兒子指針域中存放的是空指針。為了充分利用存儲(chǔ)空間，我們可以用原有的空指針域來存放結(jié)點(diǎn)的前驅(qū)和后繼指針。一般利用空的lchild域存放結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)指針，而利用空的rchild域存放后繼結(jié)點(diǎn)指針。 這種在結(jié)點(diǎn)的空指針域中存放的該結(jié)點(diǎn)在某次遍歷次序下的前驅(qū)結(jié)點(diǎn)或后繼結(jié)點(diǎn)的指針叫做線索(thread)，其中在空的左指針域中存放的指向其前驅(qū)結(jié)點(diǎn)的指針叫

48、做左線索，在空的右指針域中存放的指向其后繼結(jié)點(diǎn)的指針叫做右線索。對(duì)一棵二叉樹中的所有結(jié)點(diǎn)的空指針域按照某種遍歷次序加線索的過程叫做線索化， 被線索化了的二叉樹就稱作線索二叉樹。圖8.16(a)就是對(duì)圖8.15中的二叉樹加中序線索而得到的中序線索二叉樹。,圖 8.16 線索二叉樹及其鏈表表示,在線索二叉樹中，為了區(qū)別線索和兒子指針，必須在每個(gè)鏈結(jié)點(diǎn)中設(shè)置兩個(gè)標(biāo)志域ltag 和rtag?？梢约s定，當(dāng)ltag (rtag)1時(shí)，則表明lchild (rchild)域中存放的是結(jié)點(diǎn)的左線索（右線索），否則即為指向結(jié)點(diǎn)左子樹（右子樹）的指針。 與之對(duì)應(yīng)的數(shù)據(jù)類型定義可表達(dá)如下： type thTlink

49、 = thTnode; thTnode = record data: elemtp; lchild, rchild: thTlink; ltag, rtag: 0.1; end;,從圖中可看出，有兩個(gè)線索為空指針，即在遍歷中第一個(gè)被訪問的結(jié)點(diǎn)B的前驅(qū)線索和最后一個(gè)被訪問的結(jié)點(diǎn)D的后繼線索。 為此，可引入一個(gè)頭結(jié)點(diǎn)， 并讓原來的線索二叉樹成為它的左子樹。圖8.17顯示了與圖8.16(b)對(duì)應(yīng)的帶頭結(jié)點(diǎn)的線索二叉樹的存儲(chǔ)鏈表。,圖 8.17 帶頭結(jié)點(diǎn)的線索二叉樹的存儲(chǔ)鏈表,8.3.2 二叉樹的線索化算法 二叉樹的線索化實(shí)際上就是將二叉鏈中的空指針改為指向結(jié)點(diǎn)前驅(qū)或后繼的線索。前驅(qū)或后繼的信息可在遍

50、歷二叉樹時(shí)得到。因此，為對(duì)二叉樹進(jìn)行線索化，我們可對(duì)二叉樹進(jìn)行遍歷， 并在遇到的空指針域中，填入前驅(qū)或后繼線索。 設(shè)p: thTlink為指向二叉樹根結(jié)點(diǎn)的指針， 則二叉樹的中序線索化可表示為函數(shù)functioncreate-inthread( p: thTlink): thTlink。 其功能為對(duì)p所指的二叉樹加上一個(gè)頭結(jié)點(diǎn)，進(jìn)行中序線索化后， 返回該頭結(jié)點(diǎn)的指針。其處理過程為：,(1) 創(chuàng)建一個(gè)頭結(jié)點(diǎn)； (2) 若p為空，則令頭結(jié)點(diǎn)的左右子樹指針指向自己； (3) 若p非空，則令頭結(jié)點(diǎn)的左子樹指針指向p，調(diào)用遞歸子過程inthread對(duì)二叉樹進(jìn)行線索化； (4) 返回頭結(jié)點(diǎn)指針。 遞歸子過

51、程procedure inthread(p: thTlink, var pre: thTlink)的功能為利用前驅(qū)指針pre對(duì)指針p所指的二叉樹進(jìn)行中序線索化。 其中， 前驅(qū)指針pre用來指示指針p所指的子樹在中序序列中第一個(gè)結(jié)點(diǎn)的前驅(qū)。其處理過程為：,若p非空， 則 (1) 中序線索化p所指結(jié)點(diǎn)的左子樹； (2) 若p所指結(jié)點(diǎn)無左子樹，則建立前驅(qū)線索；若p所指結(jié)點(diǎn)無右子樹，則建立后繼線索； (3) 中序線索化p所指結(jié)點(diǎn)的右子樹。,以下是程序清單： function create-inthread( p: thTlink): thTlink; 加入頭結(jié)點(diǎn)， 對(duì)p線索化 var 并返回該頭結(jié)點(diǎn)指

52、針 head, pre: thTlink; begin new(head); new(pre); 初始化 head.ltag:=0; head.rtag:=0; if p=nil then 若為空二叉樹， 則頭結(jié)點(diǎn)的左右子樹指針指向自己,begin head.lchild:=head; head.rchild:=head; end else begin head.lchild:=p; pre:=head; inthread(p, pre); 否則對(duì)p進(jìn)行線索化 pre.rchild:=head; pre.rtag:=1; end; result:=head; end;,procedure in

53、thread( p: thTlink, var pre: thTlink); begin if p nil then begin inthread(p.lchild, pre); 線索化左子樹 if p.lchild = nil then begin 建立前驅(qū)線索 p.ltag:=1; p.lchild:= pre; end;,if pre.rchild = nil then begin 建立后繼線索 p.rtag:=1; p.rchild:= p; end; pre指向以p.rchild為根 pre:= p; 的子樹的中序遍歷序列的前驅(qū) inthread(p.rchild, pre); 線索

54、化右子樹 end;,8.3.3 線索二叉樹的應(yīng)用 1. 查找前驅(qū)或后繼 這里所指的前驅(qū)或后繼指的是在某種遍歷次序下的前驅(qū)或后繼。 (1) 在中序線索二叉樹中查找存儲(chǔ)地址為p的結(jié)點(diǎn)的前驅(qū)。 在中序線索二叉樹中查找存儲(chǔ)地址為p的結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的規(guī)律為： 當(dāng)p.ltag = 1時(shí)， p.lchild指出的結(jié)點(diǎn)就是p所指結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)，如圖8.18(a)所示； 當(dāng)p.ltag = 0時(shí)，說明該結(jié)點(diǎn)有左子樹， 則它的中序前驅(qū)結(jié)點(diǎn)應(yīng)該是以p.lchild 為根的左子樹中的最右下方的結(jié)點(diǎn)，如圖8.19(b)所示。順著左子樹的根的右指針鏈往下找，直到某結(jié)點(diǎn)的rchild域是線索（rtag = 1）為止，即

55、可得到所求前驅(qū)結(jié)點(diǎn)。,圖 8.18 中序線索二叉樹中結(jié)點(diǎn)p的前驅(qū) (a) 有前驅(qū)鏈； (b) 無前驅(qū)鏈,圖 8.19 中序線索二叉樹中結(jié)點(diǎn) p的后繼 (a) 有后繼鏈； (b) 無后繼鏈,2. 遍歷 設(shè)指針head: thTlink指向非空中序線索二叉樹的頭結(jié)點(diǎn)，則中序線索二叉樹的遍歷可表示為過程procedure inorder(head: thTlink)， 其功能為對(duì)head所指的非空中序線索二叉樹進(jìn)行中序遍歷，輸出遍歷的結(jié)點(diǎn)序列， 其處理過程為： (1) 訪問線索二叉樹在中序遍歷下的第一個(gè)結(jié)點(diǎn)； (2) 調(diào)用子函數(shù)inorder-suc確定當(dāng)前結(jié)點(diǎn)在中序序列下的后繼結(jié)點(diǎn)，并訪問； (3

56、) 重復(fù)過程(2)， 直至回到頭結(jié)點(diǎn)。,子函數(shù)function inorder-suc( p: thTlink): thTlink的功能為返回p所指結(jié)點(diǎn)的中序后繼結(jié)點(diǎn)的指針，其處理過程為： (1) 若p的右子樹域?yàn)榫€索，則返回p的右子樹指針； (2) 否則從p的右子樹的根結(jié)點(diǎn)開始，沿著左子樹鏈往下走， 返回第一個(gè)左子樹域?yàn)榫€索的結(jié)點(diǎn)指針。,以下是程序清單： procedure inorder( head: thTlink); 遍歷頭結(jié)點(diǎn)為head的非空中序線索二叉樹 var p: thTlink; begin p:= inorder-suc(head); 先將p指向中序遍歷下的第一個(gè)結(jié)點(diǎn) wh

57、ile p head do begin 顯示p.data; 訪問結(jié)點(diǎn)數(shù)據(jù) p:= inorder-suc(p); 將p指向當(dāng)前結(jié)點(diǎn)的后繼,end; end; function inorder-suc( p: thTlink): thTlink; 返回p的后繼 var s: thTlink; begin s:= p.rchild; if p.rtag = 0 then while s.ltag = 0 do s:= s.lchild; result:=s; end;,8.4 排 序 二 叉 樹,8.4.1 排序二叉樹的定義 排序二叉樹或?yàn)榭諛浠驗(yàn)闈M足具有以下特點(diǎn)的二叉樹： （1） 所有結(jié)點(diǎn)的（數(shù)據(jù)）值均不相同； （2） 若左子樹為非空，則左子樹中所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值； （3） 若右子樹為非空，則右子樹中所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值； （4） 左子樹和右子樹均是排序二叉樹。,圖