精品數(shù)據(jù)結(jié)構(gòu)講義第四章樹(shù)

1、第四章 樹(shù)4.1 樹(shù)的基本概念直觀(guān)地說(shuō)，樹(shù)是按分支關(guān)系將數(shù)據(jù)連接起來(lái)的數(shù)據(jù)結(jié)構(gòu)，就像自然界中的具有樹(shù)杈分支的樹(shù)一樣。4.1.1 樹(shù)的定義為方便計(jì)，有時(shí)常將“樹(shù)”稱(chēng)之為“樹(shù)形” ，或“樹(shù)形結(jié)構(gòu)”。定義 4.11 一個(gè) 樹(shù) （或 樹(shù)形 ）就是一個(gè)有限非空的結(jié)點(diǎn)集合T，其中：1 有一個(gè)特別標(biāo)出的被稱(chēng)為該樹(shù)（或樹(shù)形）之 根 root(T)的結(jié)點(diǎn)；2 其余結(jié)點(diǎn)被分成 m 0 個(gè)不相交的集合 T1, T2, , Tm，且 T1, T2, , Tm又都是樹(shù)（或樹(shù)形） 。樹(shù)（或樹(shù)形） T1,T2, , T m被稱(chēng)作 root(T)的子樹(shù) （或 子樹(shù)形 ）。上面給出的定義是遞歸的，就是說(shuō)用樹(shù)來(lái)定義樹(shù)。樹(shù)形的 遞

2、歸定義 似乎是更合適的，因?yàn)檫f歸是樹(shù)形結(jié)構(gòu)的固有特征。在自然界中可觀(guān)察到，樹(shù)上的幼芽可長(zhǎng)成為具有自己的幼芽的子樹(shù)，樹(shù)長(zhǎng)出子樹(shù)，子樹(shù)又長(zhǎng)出它的子樹(shù)（子樹(shù)的子樹(shù)） 。圖 4.1(a)是一棵根結(jié)點(diǎn)為 A 的樹(shù)，由定義 4.1可知，該樹(shù)中除結(jié)點(diǎn) A 之外的每個(gè)結(jié)點(diǎn)，又都是該樹(shù)中某個(gè)子樹(shù)的根。AB C DE G H IF 圖 4.1 (a) 樹(shù)為了從另外一個(gè)角度來(lái)理解樹(shù)結(jié)構(gòu)的概念，我們給出了樹(shù)的 非遞歸定義 。定義 4.2 樹(shù)是包含 n ( n 1 )個(gè)結(jié)點(diǎn)且滿(mǎn)足如下條件的有限集合：1) 存在一個(gè)唯一的 結(jié)點(diǎn) v0，它沒(méi)有前驅(qū)結(jié)點(diǎn)，稱(chēng)為樹(shù)的 根 （或 根結(jié)點(diǎn) ）；2) 任何非根結(jié)點(diǎn)都有且僅有一個(gè)前驅(qū)結(jié)點(diǎn)

3、，稱(chēng)為該結(jié)點(diǎn)的 父結(jié)點(diǎn) ；3) 任何結(jié)點(diǎn)都可能有多個(gè)（ n 1）后繼結(jié)點(diǎn)，稱(chēng)之為該結(jié)點(diǎn)的 子結(jié)點(diǎn) ；若某結(jié)點(diǎn)沒(méi)有后繼結(jié)點(diǎn)，則稱(chēng)之為 葉結(jié)點(diǎn) 。4) 任一非根結(jié)點(diǎn) vk都有且僅有一條從 根節(jié)點(diǎn) v0 到該結(jié)點(diǎn)的結(jié)點(diǎn)序列（或曰 路徑 ） v0 v1 vk，其中 vi是vi 1 的子結(jié)點(diǎn)（ 1 i k）。如對(duì)于圖 4.1(a)中的結(jié)點(diǎn) F 來(lái)說(shuō)，存在唯一一條從根結(jié)點(diǎn) A 到它的結(jié)點(diǎn)序列 A B E F ；對(duì)于結(jié)點(diǎn) H ，存在唯一一條從根結(jié)點(diǎn) A 到它的結(jié)點(diǎn)序列 A C H .AB C DE G H IF 圖 4.1 (a) 樹(shù)4.1.2 樹(shù)的相關(guān)術(shù)語(yǔ)1度一個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)的數(shù)目，稱(chēng)為該結(jié)點(diǎn)的數(shù) 。 一

4、棵 樹(shù)的度 為 maxi=1, , n D (i)，其中度 或者 次n 為樹(shù)中結(jié)點(diǎn)總數(shù)， i 指樹(shù)中的第 i 個(gè)結(jié)點(diǎn)， D(i)表結(jié)點(diǎn)2葉結(jié)點(diǎn)、分支結(jié)點(diǎn)度為 0 的結(jié)點(diǎn)被稱(chēng)為 葉結(jié)點(diǎn) ；度結(jié)點(diǎn) 。i 的度。0 的結(jié)點(diǎn)被稱(chēng)為 分支在圖 4.1(a)中： B 有一個(gè)子結(jié)點(diǎn) E，度為子結(jié)點(diǎn) B 、 C 和 D （換言之， A 是 B 、 C 和 D度為 3，故這棵樹(shù)的度也為 3 .A1； A 有三個(gè)的父結(jié)點(diǎn)） ，B CE G H IF 圖 4.1 (a) 樹(shù)3結(jié)點(diǎn)的層數(shù)樹(shù)形 T 中 結(jié)點(diǎn)的層數(shù) 遞歸定義如下： root(T)層數(shù)為零； 其余結(jié)點(diǎn)的層數(shù)為其前驅(qū)結(jié)點(diǎn)的層數(shù)加D1 .4路徑樹(shù)形中結(jié)點(diǎn)間的連

5、線(xiàn)被稱(chēng)為 邊 。若樹(shù)形 T 中存在結(jié)點(diǎn)序列 vm vm+1 vm k， 1 k T 的最大層數(shù)，滿(mǎn)足vi+1 是 vi （m i m k 1）的子結(jié)點(diǎn)，則稱(chēng)此結(jié)點(diǎn)序列為 vm到 vm k的路徑 ，該路徑所經(jīng)歷的邊數(shù) k被稱(chēng)為 路徑長(zhǎng)度 。5. 子孫結(jié)點(diǎn)、祖先結(jié)點(diǎn)一棵樹(shù)中若存在結(jié)點(diǎn) vm到 vn 的路徑，則稱(chēng) vn為 vm 的子孫結(jié)點(diǎn) ， vm為 vn的祖先結(jié)點(diǎn) 。AB C DE G H IF 圖 4.1 (a) 樹(shù)不難看出，一個(gè)結(jié)點(diǎn)到它的某個(gè)子孫結(jié)點(diǎn)有且僅有一條路徑。樹(shù)形 T 的任一結(jié)點(diǎn) p 都是 T 的一棵子樹(shù)的根結(jié)點(diǎn)，該子樹(shù)由結(jié)點(diǎn) p 和其所有子孫結(jié)點(diǎn)構(gòu)成。圖 4.1(a)中的結(jié)點(diǎn) B是由

6、結(jié)點(diǎn) B 、 E 、 F 組成的子樹(shù)的根，而結(jié)點(diǎn) C 是由結(jié)點(diǎn)C 、 G 、 H 組成的子樹(shù)的根。6樹(shù)的高度樹(shù)的高度 為 maxi=1, , n NL (i)，其中 n 為樹(shù)中結(jié)點(diǎn)總數(shù)， i 指樹(shù)中第 i 個(gè)結(jié)點(diǎn)， NL(i)之值為結(jié)點(diǎn) i 的層數(shù)。例 如，圖 4.1(b)中，結(jié)點(diǎn) A 的層數(shù)為 0 ， B 、 C 、 D 的層數(shù)為1， E 、 G 、 H 、 I 的層數(shù)為 2， F 的層數(shù)為 之樹(shù)的高度為 3 .AB C DE G H IF圖 4.1 (b) 結(jié)點(diǎn)的層數(shù)3，故圖 4.1(b)中第 0 層第 1 層第 2 層第 3 層圖 4.2 給出了一個(gè)高度為 5 的世系樹(shù)。圖 4.2 世系

7、樹(shù)4.2 二叉樹(shù)二叉樹(shù)是一種常用的樹(shù)結(jié)構(gòu)，它是樹(shù)結(jié)構(gòu)的另一種重要類(lèi)型，其特征是：樹(shù)中每個(gè)結(jié)點(diǎn)最多有兩個(gè)子樹(shù)形。4.2.1 二叉樹(shù)定義和主要性質(zhì)定義 4.3 二叉樹(shù) （形）是結(jié)點(diǎn)的有限集合，它或者是空集，或者由一個(gè)根及兩個(gè)不相交的稱(chēng)為這個(gè)根的左、右子樹(shù)形的二叉樹(shù)組成。abc d e 圖 4.3 公式 a b(c/d e/f)的二叉樹(shù)表示f二叉樹(shù)有如下重要性質(zhì)：引理 4.1 二叉樹(shù)中層數(shù)為 i 的結(jié)點(diǎn)至多有證明：用數(shù)學(xué)歸納法。當(dāng) i 0 時(shí)，僅有一個(gè)根結(jié)點(diǎn)，其層數(shù)為2i個(gè)， i 0 .0，因此 i 0時(shí)引理成立。假定當(dāng) i j ( j 0) 時(shí)，引理成立，即第 j 層上至多有 2j 個(gè)結(jié)點(diǎn)。對(duì)于二

8、叉樹(shù)的任意結(jié)點(diǎn)，其子結(jié)點(diǎn)個(gè)數(shù)最多為 2，故第 j 1 層上至多有 2 2j 2j+ 1 個(gè)結(jié)點(diǎn)，故 i j1 時(shí)，引理亦成立。證畢 ?容易看出高度為 k (k 1)的二叉樹(shù)中至少有 k 1 個(gè)結(jié)點(diǎn)。含有 k (k 1)個(gè)結(jié)點(diǎn)的二叉樹(shù)高度至多為 k 1 . 如圖 4.5是高度為 3 結(jié)點(diǎn)最少的二叉樹(shù)之一。圖點(diǎn)最多的二叉樹(shù)。4.6(a)是高度為 3 結(jié)ABCD圖 4.5 有 4 個(gè)結(jié)點(diǎn)、高度為 3 的二叉樹(shù)12 34 5 68 9 10 11 12 13(a) 15 個(gè)結(jié)點(diǎn)的滿(mǎn)二叉樹(shù)714 15k i21k引理 4.2 高度為 k 的二叉樹(shù)中至多有 2k+1 1( k 0)個(gè)結(jié)點(diǎn)。證明：從第 0

9、層到第和，由引理 4.1 知 i 0k 層，對(duì)每層的最大結(jié)點(diǎn)數(shù)求2 1，證畢 ?引理 4.3 設(shè) T 是由 n 個(gè)結(jié)點(diǎn)構(gòu)成的二叉樹(shù)，其中葉結(jié)點(diǎn)個(gè)數(shù)為 n0，次數(shù)為 2 的結(jié)點(diǎn)個(gè)數(shù)為 n2，則有 n0 n2 1 .證明：設(shè) n1 是 T 中次數(shù)為 1 的結(jié)點(diǎn)個(gè)數(shù)，則n n0 n1 n2 (1)設(shè)二叉樹(shù) T 的邊個(gè)數(shù)為 E . 我們知道，除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)和父結(jié)點(diǎn)之間都有且僅有一條邊，即一個(gè)結(jié)點(diǎn)對(duì)應(yīng)一條邊，因此， n 比邊的個(gè)數(shù)多 1 （根結(jié)點(diǎn)不對(duì)應(yīng)邊） ，即n =E 1 (2)從另一個(gè)角度看，次數(shù)為 1 的結(jié)點(diǎn)對(duì)應(yīng)一條邊，次數(shù)為 2 的結(jié)點(diǎn)對(duì)應(yīng)兩條邊，因此E = n1 2n2 (3)由(1)

10、、 (2)和(3)可以得到 n0 n2 1. 證畢 ?定義 4.4 一棵非空高度為 k( k 0)的滿(mǎn)二叉樹(shù) ，是有2k+1 1 個(gè)結(jié)點(diǎn)的二叉樹(shù)。我們可按層次順序（即按從第 0 層到第 k 層，每層由左向右的次序）將一棵滿(mǎn)二叉樹(shù)的所有結(jié)點(diǎn)用自然數(shù)從 1開(kāi)始編號(hào)。例如，圖24 1 個(gè)結(jié)點(diǎn)的編號(hào)。248 9 104.6(a) 給出了高度為 3 的滿(mǎn)二叉樹(shù)的135 6 711 12 13 14 15(a) 15 個(gè)結(jié)點(diǎn)的滿(mǎn)二叉樹(shù)定義 4.5 一棵包含 n 個(gè)結(jié)點(diǎn)高為 k 的二叉樹(shù) T，當(dāng)按層次順序編號(hào) T 的所有結(jié)點(diǎn)，對(duì)應(yīng)于一棵高為 k 的滿(mǎn)二叉樹(shù)中編號(hào)由 1 至 n 的那些結(jié)點(diǎn)時(shí)， T 被稱(chēng)為 完

11、全二叉樹(shù) 。滿(mǎn)二叉樹(shù)和完全二叉樹(shù)是二叉樹(shù)的兩種特殊情形。12 34 5 6 78 9 10 11 12 13 14(a) 15 個(gè)結(jié)點(diǎn)的滿(mǎn)二叉樹(shù)12 34 5 68 9 10(b) 10 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)圖 4.6 滿(mǎn)二叉樹(shù)與完全二叉樹(shù)157引理 4.4 若將一棵有 n 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)按層次順序用自然數(shù)從 1 開(kāi)始編號(hào)，則編號(hào)為 i (1 i n)的結(jié)點(diǎn)滿(mǎn)足如下性質(zhì)： 若 i 1，則編號(hào)為 i 的結(jié)點(diǎn)之父結(jié)點(diǎn)的編號(hào)為 若 2i n，則編號(hào)為 i 的結(jié)點(diǎn)的左孩子編號(hào)為i 無(wú)左孩子； 若 2i 1 n，則 i 結(jié)點(diǎn)的右孩子編號(hào)為 2i無(wú)右孩子。i/2 ；2i，否則1，否則 i證明：用歸納法可

12、證明 .若 i 1，如果 n 2，則左孩子編號(hào)顯然為 2 .假定對(duì)所有 j(1 j i， 2i n)， j 的左孩子編號(hào)為 2j，則往證結(jié)點(diǎn) j i 1 之左孩子的編號(hào)為 2(i+1)的情況。如果 2(i1) n，則由層次順序知， i 1 的左孩子之前的兩個(gè)結(jié)點(diǎn)就是 i 的左孩子和右孩子，因?yàn)?i 的左孩子編號(hào)為 2i （由歸納假設(shè)） ，故 i 的右孩子編號(hào)為 2i 1，從而 i 1 的左孩子編號(hào)為 2i 2 2(i 1) .因?yàn)橛煽芍苯油瞥觯珊陀挚傻玫剑C畢 ?k k+1例如：圖 4.6 (b)中編號(hào)為 4 的結(jié)點(diǎn)的父結(jié)點(diǎn)編號(hào)為 2，其左孩子編號(hào)為 8，右孩子編號(hào)為父結(jié)點(diǎn)編號(hào)為 2，其左孩

13、子編號(hào)為124 59，而編號(hào)為 5 的結(jié)點(diǎn)的10，無(wú)右孩子。36 78 9 10(b) 10 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)圖 4.6 滿(mǎn)二叉樹(shù)與完全二叉樹(shù)引理 4.5 具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的高度是 log2 n .證明：設(shè)二叉樹(shù)高度為 k，由定義的結(jié)點(diǎn)個(gè)數(shù)介于高度為 k 和高度為 k數(shù)之間，即有：4.5 知，完全二叉樹(shù)1 的滿(mǎn)二叉樹(shù)的結(jié)點(diǎn)2 1 n 2 1，從而有 2k n 2k+1 1，即 k log2 nk 1，有 log2 n 1 k log2 n，因?yàn)?k 為整數(shù)，故有 k log2 n ，證畢 ?4.2.2 二叉樹(shù) 順序存儲(chǔ)要存儲(chǔ)一棵二叉樹(shù)，必須存儲(chǔ)其所有結(jié)點(diǎn)的數(shù)據(jù)信息、左孩子和右孩子

14、地址，既可用順序結(jié)構(gòu)存儲(chǔ)，也可用鏈接結(jié)構(gòu)存儲(chǔ)。二叉樹(shù)的順序存儲(chǔ)是指將二叉樹(shù)中所有結(jié)點(diǎn)按層次順序存放在一塊地址連續(xù)的存儲(chǔ)空間中，同時(shí)反映出二叉樹(shù)中結(jié)點(diǎn)間的邏輯關(guān)系。對(duì)于完全二叉樹(shù)，結(jié)點(diǎn)的層次順序反映了其結(jié)構(gòu)，可按層次順序給出一棵完全二叉樹(shù)之結(jié)點(diǎn)的編號(hào)，事實(shí)上，這就是完全二叉樹(shù)的順序存儲(chǔ)方法，結(jié)點(diǎn)編號(hào)恰好反映了結(jié)點(diǎn)間的邏輯關(guān)系。只要對(duì)二叉樹(shù)之結(jié)點(diǎn)按照層次順序進(jìn)行編號(hào)，就可利用一維數(shù)組 A 來(lái)存儲(chǔ)一棵含有 n 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，其中 A1存儲(chǔ)二叉樹(shù)的根結(jié)點(diǎn)， Ai存儲(chǔ)二叉樹(shù)中編號(hào)為 i 的結(jié)點(diǎn)，并且結(jié)點(diǎn) Ai的左孩子（若存在）存放在 A2i處，而 Ai的右孩子（若存在）存放在 A2i 1處。圖 4

15、.7 (b) 描述了圖 4.7 (a) 所示的完全二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)。A 1B 2 E 3C 4 D 5(a) 5 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)A B E C DA1 A2 A3 A4 A5(b) 圖(a)的順序存儲(chǔ)結(jié)構(gòu)圖 4.7 完全二叉樹(shù)與順序存儲(chǔ)結(jié)構(gòu)這種順序存儲(chǔ)方式是完全二叉樹(shù)最簡(jiǎn)單、最節(jié)省空間的存儲(chǔ)方式，多數(shù)完全二叉樹(shù)應(yīng)用算法都采用了這種順序存儲(chǔ)方式。它實(shí)際上只存儲(chǔ)了結(jié)點(diǎn)信息域之值，而未存儲(chǔ)其左孩子和右孩子地址，通過(guò)計(jì)算可找到它的左孩子、右孩子和父結(jié)點(diǎn)，尋找子孫結(jié)點(diǎn)和祖先結(jié)點(diǎn)也非常方便。但是，這種方法應(yīng)用到非完全二叉樹(shù)時(shí)，卻有很多缺點(diǎn)。如果采用上述的順序存儲(chǔ)方式，按照層次順序，對(duì)非完全二叉樹(shù)之

16、結(jié)點(diǎn)進(jìn)行編號(hào)，則這時(shí)的編號(hào)不能與結(jié)點(diǎn)一一對(duì)應(yīng)。為此，先加入若干虛結(jié)點(diǎn)將其轉(zhuǎn)換成一棵“完全二叉樹(shù)”，然后再對(duì)原來(lái)的結(jié)點(diǎn)和虛結(jié)點(diǎn)統(tǒng)一編號(hào)，最后完成順序存儲(chǔ)。但這增加了用于存儲(chǔ)虛結(jié)點(diǎn)的空間。B A3A A1C A7C如圖 4.8(a) 所示，二叉樹(shù)中只有 4 個(gè)結(jié)點(diǎn)，轉(zhuǎn)換為“完全二叉樹(shù)”后如圖 4.8 (b) 所示，圖中的方形結(jié)點(diǎn)為增加的虛結(jié)點(diǎn)，其順序存儲(chǔ)結(jié)構(gòu)如圖 4.8(c)所示，需要 15 個(gè)數(shù)組元素，但AABBCDD(a) 非完全二叉樹(shù)(b) 完全二叉樹(shù)DA15(c)非完全二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)圖 4.8 非完全二叉樹(shù)與順序存儲(chǔ)結(jié)構(gòu)實(shí)際上只有 A1 、 A3 、 A7和 A15 等 4 個(gè)數(shù)組元

17、素的存儲(chǔ)空間能被充分利用，而其它 11 個(gè)數(shù)組元素所占用的空間卻被浪費(fèi)。顯然，對(duì)非完全二叉樹(shù)，順序存儲(chǔ)結(jié)構(gòu)可能會(huì)浪費(fèi)大量存儲(chǔ)空間。此外，同線(xiàn)性表的順序存儲(chǔ)一樣，二叉樹(shù)順序存儲(chǔ)方式對(duì)插入或刪除結(jié)點(diǎn)等操作不夠方便。4.2.3 二叉樹(shù)鏈接存儲(chǔ)二叉樹(shù)的鏈接存儲(chǔ)系指 二叉樹(shù)諸結(jié)點(diǎn)被隨機(jī)存放在內(nèi)存空間中，結(jié)點(diǎn)之間的關(guān)系用指針說(shuō)明。在二叉樹(shù)的鏈接存儲(chǔ)中，二叉樹(shù)結(jié)點(diǎn)應(yīng)包含三個(gè)域：數(shù)據(jù)域域 Left 和右指針域 Right，結(jié)點(diǎn)結(jié)構(gòu)如下：Left Data Right其中數(shù)據(jù)域 Data 存放結(jié)點(diǎn)自身的信息，域分別存放指向該結(jié)點(diǎn)之左孩子和右孩子的指針。Data、左指針Left 和 Right在二叉樹(shù)的鏈接存儲(chǔ)中

18、，有一個(gè)指向根結(jié)點(diǎn)的指針，稱(chēng)為 根指針 ，二叉樹(shù)由根指針唯一確定。若二叉樹(shù)為空，則根指針為 NULL （即 ）；若結(jié)點(diǎn)的某個(gè)孩子不存在，則相應(yīng)的指針域存放 NULL . 顯然，葉結(jié)點(diǎn)的左、右指針域皆存放 NULL . 在包含 n 個(gè)結(jié)點(diǎn)之二叉樹(shù)的鏈接存儲(chǔ)中，需要2n 個(gè)指針域，但其中只有 n 1 個(gè)用來(lái)指示結(jié)點(diǎn)的左、右孩子，其余 n 1 個(gè)指針域?yàn)榭眨ㄒ?jiàn)引理 4.3， E = n 1）。B圖 4.9 (a) 為一棵二叉樹(shù)，其鏈接存儲(chǔ)結(jié)構(gòu)如圖 4.9(b)，結(jié)點(diǎn) A 的 Left 指針指向其左子結(jié)點(diǎn) B， Right 指針指向其右子結(jié)點(diǎn) C，結(jié)點(diǎn) B 的 Left 指針為空， Right 指針指

19、向其子結(jié)點(diǎn) D .ACD E(a) 二叉樹(shù)rootA B C D E (b) 二叉樹(shù)的鏈接表示圖 4.9 二叉樹(shù)的鏈接存儲(chǔ)結(jié)構(gòu)下面用三個(gè)算法來(lái)說(shuō)明，二叉樹(shù)的鏈接存儲(chǔ)可方便地進(jìn)行二叉樹(shù)的一些操作。 在二叉樹(shù)中搜索給定結(jié)點(diǎn)的父結(jié)點(diǎn)算法 Father ( t, p . q )/* 指針 t 指向二叉樹(shù) T 之根，在 T 中搜索給定結(jié)點(diǎn) p 之父結(jié)點(diǎn)； q指向 p之父結(jié)點(diǎn)；本算法使用了遞歸 */Father1. t ? IF t THEN ( q . RETURN. )Father2. t 為所求 ? IF Left ( t ) p OR Right ( t ) pTHEN ( q t. RETURN

20、. )Father3. 遞歸Father ( Left ( t ) , p . qL).IF qL THEN ( q qL . RETURN. )ELSE (Father ( Right ( t ), p . qR). q qR . RETURN. )? 搜索二叉樹(shù)中符合數(shù)據(jù)域條件的結(jié)點(diǎn)算法 Find( t, item . q )/* 在二叉樹(shù) T 中搜索 Data 域之值為 item的結(jié)點(diǎn)，指針 t指向 T 之 根，指針 q指向欲搜索的結(jié)點(diǎn) */Find1. t ? IF t THEN ( q . RETURN. ).IF Data( t ) itemTHEN ( q t . RETURN.

21、 ).Find2 .遞歸Find ( Left(t), item . p ).IF p THEN ( q p . RETURN. ).Find (Right(t), item . q ).RETURN. ? 從二叉樹(shù)中刪除給定結(jié)點(diǎn)及其左右子樹(shù)算法 DST ( t )/* root指向一棵二叉樹(shù) T 之根，本算法從 T 中刪除給定結(jié)點(diǎn) t (是簡(jiǎn)稱(chēng)，其含義是： t是指向該結(jié)點(diǎn)的指針 )及其左右子樹(shù)； DST 是DelSubTree之縮寫(xiě) */DST1. t ? IF t THEN RETURN .DST 2. t root ? IF t rootTHEN ( Del(t) . root . RE

22、TURN. )DST3. 找 t 的父結(jié)點(diǎn) q p t . Father(root, p. q).DST 4. 修改q的指針域 IF Left(q) p THEN Left(q) .IF Right(q) p THEN Right(q) .DST 5. 刪除p及其子樹(shù) Del(p).?算法 Del( p )/* 刪除結(jié)點(diǎn) p及其左右子樹(shù) */Del1. p ? IF p THEN RETURN.Del2. 遞歸刪除 Del (Left (p).Del (Right (p).AVAIL p .?4.2.4 二叉樹(shù)遍歷對(duì)于樹(shù)結(jié)構(gòu)的操作有許多算法，并且在這些算法中將反復(fù)對(duì)樹(shù)進(jìn)行“遍歷” 。 遍歷 樹(shù)

23、形是系統(tǒng)地考察樹(shù)形之結(jié)點(diǎn)，使得樹(shù)形的每個(gè)結(jié)點(diǎn)恰好被訪(fǎng)問(wèn)一次的方法。在計(jì)算機(jī)內(nèi)一般的樹(shù)是借助某個(gè)等價(jià)的二叉樹(shù)來(lái)表示的。為此，我們先考慮二叉樹(shù)的遍歷問(wèn)題。我們知道，線(xiàn)性表是一種線(xiàn)性結(jié)構(gòu)，對(duì)于鏈接存儲(chǔ)的線(xiàn)性表可通過(guò)指針域 Next 進(jìn)行順序遍歷。但二叉樹(shù)是一種非線(xiàn)性結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)可能有一個(gè)以上的直接后繼，因此無(wú)法像線(xiàn)性表一樣進(jìn)行簡(jiǎn)單的順序遍歷。遍歷方法步驟步驟一 步驟二 步驟三先根序訪(fǎng)問(wèn)根 遍歷左子樹(shù) 遍歷右子樹(shù)中根序遍歷左子樹(shù) 訪(fǎng)問(wèn)根遍歷右子樹(shù)后根序遍歷左子樹(shù)遍歷右子樹(shù)訪(fǎng)問(wèn)根例 2: 用上述三種方法遍歷圖A B 4.11 中的二叉樹(shù) .FEC D圖 4.11 (A+B) (C D) E+F) 對(duì)應(yīng)

24、的二叉樹(shù)先根序得到的結(jié)點(diǎn)序列： AB CDEF中根序得到的結(jié)點(diǎn)序列：后根序得到的結(jié)點(diǎn)序列：A+B C D E+FAB+CD E F+這三種排列方式都非常重要，因?yàn)樗鼈兎謩e對(duì)應(yīng)表達(dá)式的前綴、中綴和后綴表示法（其中，中綴表示還需要括號(hào)和優(yōu)先級(jí)，稍有差別） 。先根序、中根序、后根序這些名稱(chēng)來(lái)自于根相對(duì)它的子樹(shù)的位置。在二叉樹(shù)的許多應(yīng)用中，左子樹(shù)和右子樹(shù)之間存在著對(duì)稱(chēng)性，故對(duì)稱(chēng)序可作為中根序的同義詞。有上述定義，對(duì)于給定的一棵二叉樹(shù)，我們可給出在先根序、中根序和后根序下的唯一結(jié)點(diǎn)排列。但反過(guò)來(lái)，也就是由先根序或中根序或后根序所得到的結(jié)點(diǎn)序列，我們并不能確定相應(yīng)二叉樹(shù)之結(jié)構(gòu)（因?yàn)椴晃ㄒ唬?。1遞歸遍歷算

25、法根據(jù)二叉樹(shù)先根、中根和后根序遍歷的遞歸定義，可設(shè)計(jì)出先根 、 中 根 和 后 根 序 遍 歷 的 遞 歸 算 法 PreOrder 、 InOrder 和PostOrder . 先根遍歷算法算法 PreOrder ( t )IF t THEN RETURN.PRINT ( Data ( t ) .PreOrder ( Left ( t ) .PreOrder( Right ( t ) . ? 中根遍歷算法算法 InOrder ( t )IF t THEN RETURN .InOrder ( Left ( t ) .PRINT ( Data ( t ) .InOrder ( Right ( t

26、 ) . ? 后根遍歷算法算法 PostOrder ( t )IF t THEN RETURN .PostOrder( Left ( t ) .PostOrder( Right ( t ) .PRINT ( Data ( t ) . ?從算法來(lái)看，二叉樹(shù)的先根、中根和后根遍歷三種遞歸算法， 只是算法中的 PRINT( Data(t)語(yǔ)句與兩條遞歸語(yǔ)句的相對(duì)位置不 同。從遍歷序列來(lái)看，三種不同遍歷序列的葉結(jié)點(diǎn)間的相對(duì)次序是 相同的，葉結(jié)點(diǎn)都是按著從左到右的次序排列，三種遍歷序列間的 區(qū)別僅在于非葉結(jié)點(diǎn)間的次序以及非葉結(jié)點(diǎn)和葉結(jié)點(diǎn)間的次序有所不同。2非遞歸遍歷算法為了在計(jì)算機(jī)上直接實(shí)現(xiàn)上述遍歷方法

27、，下面給出非遞歸遍歷算法。 非遞歸中根遍歷算法算法 NIO ( t )/* 設(shè) t是指向與圖 4.9(b)中之表示相同的一棵二叉樹(shù) T 的根的指針，本算法利用一個(gè)輔助堆棧NorecInOrder 之縮寫(xiě) */NIO1. 初始化 CREATE ( S ). pNIO2. 入棧WHILE p DO( S p . p NIO3. 棧為空 ? S 以中根序訪(fǎng)問(wèn) T 的所有結(jié)點(diǎn)； NIO 是t.Left ( p) . )IF S 為空 THEN RETURN.ELSE p S .NIO4. 訪(fǎng)問(wèn) p，更新 pPRINT ( Data ( p ) ). p Right ( p ).NIO5. 返回GOTO

28、 NIO2 . ?例如，圖 4.12(b) 給出了對(duì)圖 4.12(a)中二叉樹(shù)進(jìn)行中根遍歷時(shí)堆棧的變化過(guò)程：AB CD E F(a) 二叉樹(shù)BA訪(fǎng)問(wèn) BDA A訪(fǎng)問(wèn) DA訪(fǎng)問(wèn) AEC訪(fǎng)問(wèn) EC訪(fǎng)問(wèn) CF訪(fǎng)問(wèn) F(b) 中根遍歷 (a)中二叉樹(shù) , 堆棧內(nèi)容變化過(guò)程圖 4.12 非遞歸中根遍歷二叉樹(shù)類(lèi)似于算法 NIO ，不難形成先根序的非遞歸遍歷二叉樹(shù)之算法，我們將該算法留作習(xí)題，下面我們討論后根序非遞歸二叉樹(shù)遍歷算法。 非遞歸后根遍歷算法非遞歸后根遍歷算法也需要一個(gè)輔助堆棧來(lái)記憶訪(fǎng)問(wèn)路徑，算法中棧元素結(jié)構(gòu)如下：結(jié)點(diǎn) 標(biāo)號(hào) i其中標(biāo)號(hào) i 0, 1, 2 . 樹(shù)中任一結(jié)點(diǎn) q都需進(jìn)棧三次，出棧三

29、次。第一次出棧是為遍歷結(jié)點(diǎn) q 的左子樹(shù)，第二次出棧是為遍歷結(jié)點(diǎn) q 的右子樹(shù)，第三次出棧是為訪(fǎng)問(wèn)結(jié)點(diǎn) q . 具體方法如下：（1） 將（根結(jié)點(diǎn)， 0 ）壓入堆棧。（2） 彈棧，對(duì)出棧元素（ p， i ）中標(biāo)號(hào) i進(jìn)行判斷， 若 i 0，則將（ p， 1）壓入堆棧；若結(jié)點(diǎn) p的左指針不為空，則將（ Left(p), 0) 壓入堆棧） ，準(zhǔn)備遍歷其左子樹(shù) . 若 i 1，此時(shí)已遍歷完結(jié)點(diǎn) p 的左子樹(shù)，則將 （ p， 2） 壓 入 堆 棧； 若 右 指 針 不 為 空， 則 將 （Right(p), 0)壓入堆棧，準(zhǔn)備遍歷其右子樹(shù) . 若 i 2 ，此時(shí)已遍歷完結(jié)點(diǎn) p 的右子樹(shù)，訪(fǎng)問(wèn)結(jié)點(diǎn) p.

30、算法 NPO( t )/* 設(shè) t是指向與圖 4.9(b)中之表示相同的一棵二叉樹(shù) T 的根的指針，本非遞歸算法利用堆棧 S 以后根序訪(fǎng)問(wèn) T 的所有結(jié)點(diǎn) */NPO1. 初始化IF t THEN RETURN .CREATE( S) . S ( t , 0) .NPO2. 后根遍歷 WHILE S 非空 DO( (p , i) S .IF i 0 THEN ( S (p, 1) . IF Left (p)(p), 0) ).IF i 1 THEN ( S (p , 2). IF Right (p)(p),0) ) .IF i 2 THEN PRINT ( Data (p) ). )?THEN

31、 S (LeftTHEN S (Right圖4.13 算法 NPO 對(duì)圖 4.12(a)中二叉樹(shù)進(jìn)行遍歷時(shí)，棧 S之變化。A,0E,1 C,1 A,2B,0 A,1E,2 C,1 A,2B,1A,1C,1A,2訪(fǎng)問(wèn) ED,0B,2A,1F ,0C,2A,2D,1B,2A,1F ,1C,2A,2D,2 B,2 A,1F ,2C,2A,2B,2A,1 訪(fǎng)問(wèn) DC,2A,2訪(fǎng)問(wèn) FA,1 訪(fǎng)問(wèn) BA,2訪(fǎng)問(wèn) CC,0A,2訪(fǎng)問(wèn) AE,0C,1A,2圖 4.13 棧 S 之變化3層次遍歷除了上述先根序、中根序和后根序等三種遍歷方法外，還有一種較常用的遍歷方式，被稱(chēng)為 層次遍歷 。層次遍歷按層數(shù)由小到大

32、，即從第 0 層開(kāi)始逐層向下，同層中由左到右的次序訪(fǎng)問(wèn)二叉樹(shù)的所有結(jié)點(diǎn)。對(duì)于圖 4.12(a) 所示的二叉樹(shù)，其層次遍歷的次序?yàn)?A B C D E F .AB CD E F(a) 二叉樹(shù)二叉樹(shù)層次遍歷算法需要一個(gè)輔助隊(duì)列，具體方法如下：（1） 根結(jié)點(diǎn)入隊(duì) .（2） 重復(fù)本步驟直至隊(duì)為空 :若隊(duì)非空，取隊(duì)頭結(jié)點(diǎn)并訪(fǎng)問(wèn)；若其左指針不空，將其左孩子入隊(duì)，若其右指針不空，將其右孩子入隊(duì).算法 LevelOrder ( t )/* 設(shè) t是指向一棵二叉樹(shù) T 之根的指針，本算法層次遍歷 T */CREATE ( Q ).p t . IF pWHILETHEN Q p . Q 非空 DO( p Q .P

33、RINT ( Data (p) ) .IF Left (p) THEN QIF Right (p) THEN Q) ?BLeft (p) .Right (p) .ACD E F(a) 二叉樹(shù)圖 4.14 對(duì)圖 4.12(a)中的二叉樹(shù)進(jìn)行層次遍歷時(shí)，隊(duì)列的變化過(guò)程.訪(fǎng)問(wèn) B、訪(fǎng)問(wèn) C， E、A 入隊(duì)訪(fǎng)問(wèn) AD 入隊(duì)F 入隊(duì)訪(fǎng)問(wèn) D訪(fǎng)問(wèn) EABCDEFCDE FF訪(fǎng)問(wèn) F圖 4.14 層次遍歷二叉樹(shù)的隊(duì)列變化過(guò)程4.2.5 創(chuàng)建二叉樹(shù)由二叉樹(shù)的遍歷算法，很容易想到用遍歷方法去創(chuàng)建二叉樹(shù)。遞歸算法 CreateBinTree （簡(jiǎn)記為 CBT ）以根指針 t 為輸入?yún)?shù)，以包含空指針信息的先根序列

34、為輸入序列 . 當(dāng)讀入 #字符時(shí)，將其初始化為一個(gè)空指針；否則生成一個(gè)新結(jié)點(diǎn)并初始化其父結(jié)點(diǎn)之左、右指針 . 由于序列中用“ #”表示空指針，故在算法中設(shè)置的“#”。算法 CBT (tostop. t )tostop #，以便判斷序列中/* 構(gòu)造以結(jié)點(diǎn) t為根的二叉樹(shù)； tostop #*/CBT1. 讀數(shù)據(jù) READ ( ch) . /* 順序讀入序列中的一個(gè)符號(hào) */CBT2. ch tostop? IF ch tostopTHEN ( t ELSE ( t AVAIL . Data(t)CBT3. 構(gòu)造左子樹(shù) CBT ( . Left (t) ).CBT4. 構(gòu)造右子樹(shù) CBT ( .

35、Right(t) ). ?. RETURN t . )ch . )當(dāng)輸入序列為二叉樹(shù) .ABD#E#C#時(shí)，可創(chuàng)建圖 4.15(b)所示AB CDE圖 4.15 (b)4.2.6 復(fù)制二叉樹(shù)先復(fù)制子結(jié)點(diǎn)，后復(fù)制父結(jié)點(diǎn)，然后再將父結(jié)點(diǎn)與子結(jié)點(diǎn)連接起來(lái)，就可 自底向上 地復(fù)制一棵新樹(shù)。AB DC E圖 4.16 二叉樹(shù) Tree_1算法 CopyTree(t . p )/* t指向一棵二叉樹(shù) T 的根， 二叉樹(shù) T 為 T 的復(fù)制品， p指向 T 之根 */CopyTree1.遞歸出口 IF t THEN RETURN .CopyTree2.復(fù)制左子樹(shù) IF Left(t) THEN CopyTr

36、ee(Left(t) . newlptr) ELSEnewlptr .CopyTree3.復(fù)制右子樹(shù) IF Right(t) THEN CopyTree(Right (t). newrptr) ELSEnewrptr .CopyTree4.生成結(jié)點(diǎn) pAVAIL.Data(p) Data (t) . Left (p) newlptr . Right(p) newrptr.RETURN p. ?4.3 線(xiàn)索二叉樹(shù)4.3.1 線(xiàn)索二叉樹(shù)定義以 Left/Right 鏈接表示的二叉樹(shù)結(jié)構(gòu)，可看作是有很多從根結(jié)點(diǎn)一直到葉結(jié)點(diǎn)的單鏈表組成的，一個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)是其父結(jié)點(diǎn)，一個(gè)結(jié)點(diǎn)的后繼結(jié)點(diǎn)是它的兒子結(jié)點(diǎn)

37、。這種結(jié)構(gòu)有兩方面不足：其一是從一個(gè)結(jié)點(diǎn)只能訪(fǎng)問(wèn)它的兒子結(jié)點(diǎn)，而不能訪(fǎng)問(wèn)它的父結(jié)點(diǎn)；其二是這種結(jié)構(gòu)通常包含很多未被有效使用的指針字段（或域） ，譬如包含i 個(gè)結(jié)點(diǎn)的二叉樹(shù)，在其 2i 個(gè)指針域中僅有 i 1 個(gè)被使用 .為使二叉樹(shù)之結(jié)點(diǎn)的訪(fǎng)問(wèn)更方便，其空間的利用更高效 . 1960 年， Perlis A J 和 Thornton C 提出了巧妙的線(xiàn)索二叉樹(shù)表示。圖 4.18(a)中二叉樹(shù)的中根遍歷序列為 BCAED ，其中 C是 A的中根前驅(qū)結(jié)點(diǎn)， A是 C的中根后繼結(jié)點(diǎn)。類(lèi)似也可給出先根前驅(qū)（先根后繼）結(jié)點(diǎn)、后根前驅(qū)（后根后繼）結(jié)A點(diǎn)之概念 .B DC E(a) 二叉樹(shù)正象線(xiàn)性表的雙向鏈表

38、一樣，二叉樹(shù)也可采用雙向鏈接 . 如圖 4.17 所示，針對(duì)某種遍歷順序，可為二叉樹(shù)的每個(gè)結(jié)點(diǎn)增加兩個(gè)指針域，分別存放指向其前驅(qū)和后繼結(jié)點(diǎn)的指針 Pred 和 Succ，并稱(chēng) Pred 和 Succ 為 線(xiàn)索 . 在這樣的二叉樹(shù)中搜索一結(jié)點(diǎn)在某種遍歷順序下的前驅(qū)或后繼結(jié)點(diǎn)將變得更加容易，但將增加一些存儲(chǔ)空間 .Pred Left Data Right Succ圖 4.17 線(xiàn)索二叉樹(shù)的結(jié)點(diǎn)結(jié)構(gòu)定義 4.6 設(shè) T* 是由增加某種遍歷順序之 線(xiàn)索域 的結(jié)點(diǎn)（如圖 4.17）所構(gòu)成的一棵二叉樹(shù)，在 T * 中可直接查找任一結(jié)點(diǎn)在這種遍歷順序下的前驅(qū)和后繼結(jié)點(diǎn)，則稱(chēng) T* 為 線(xiàn)索二叉樹(shù) (Thre

39、aded Binary Tree) .若在一棵線(xiàn)索二叉樹(shù)中，指針 Pred 和 Succ分別指向結(jié)點(diǎn)的先根（中根、后根）前驅(qū)和先根后繼，則稱(chēng)其為 先序（中序、后序）線(xiàn)索二叉樹(shù) .PredSuccA圖 4.18 (a)所示二叉樹(shù)之中根遍歷序列為 BCAED ，它的中序線(xiàn)索二叉樹(shù)的鏈接表示如圖 4.18 (b)所示；其后根序列為 CBEDA ，它的后序線(xiàn)索二叉樹(shù)的鏈接表示如圖所示。PredArootA4.18 (c)SuccB D BSucc PredC EC E(a) 二叉樹(shù) Succ Pred(b) 中序線(xiàn)索二叉樹(shù)的鏈接表示DSuccPred rootSuccB DPred Succ Pred

40、 SuccC EPred(c) 后序線(xiàn)索二叉樹(shù)的鏈接表示圖 4.18 線(xiàn)索二叉樹(shù)的鏈接表示，圖中虛線(xiàn)箭頭表示線(xiàn)索4.3.2 線(xiàn)索二叉樹(shù)存儲(chǔ)由上節(jié)圖 4.18 可看出，線(xiàn)索二叉樹(shù)的結(jié)點(diǎn)中仍有很多空指針，顯然存儲(chǔ)空間的浪費(fèi)問(wèn)題還未得到有效解決。那么能否通過(guò)對(duì)上述線(xiàn)索二叉樹(shù)的改進(jìn)來(lái)解決呢？答案是肯定的。指針域需占用較多的存儲(chǔ)空間，例如一個(gè)空間容量為 4GB 的內(nèi)存儲(chǔ)器需要 32 個(gè)二進(jìn)制位來(lái)表示地址，若將指針域中的 Pred 和 Succ換成 1 個(gè)二進(jìn)制位則會(huì)節(jié)省許多空間?；诖耍腥私o出了線(xiàn)索二叉樹(shù)的改進(jìn)方案： 將原指針域 Pred 和 Succ 分別改成存儲(chǔ)一個(gè)二進(jìn)制位的域 LThread 和

41、 RThread . 若結(jié)點(diǎn) t 有左孩子，則 Left 指向 t 的左孩子，且LThread 的值為的前驅(qū)結(jié)點(diǎn)，且索）.0；若 t 沒(méi)有左孩子，則 Left 指向 tLThread 的值為 1 （此時(shí)稱(chēng) Left 為線(xiàn) 若結(jié)點(diǎn) t 有右孩子，則 Right 指向 t 的右孩子，且RThread 的值為的后繼結(jié)點(diǎn)，且線(xiàn)索） .0；若 t 沒(méi)有右孩子，則 Right 指向 tRThread 的值為 1 （此時(shí)稱(chēng) Right 為經(jīng)改進(jìn)，不僅釋放了指針域 Pred 和 Succ所占的較多空間，而且使存放空指針的域 Left 和 Right 得以充分利用。在線(xiàn)索二叉樹(shù)中，葉結(jié)點(diǎn)的充要條件為： LThr

42、ead 和 RThread的值均是 1. 改進(jìn)后，圖 4.18 ( a)的中序線(xiàn)索二叉樹(shù)的鏈接表D 1Succ11D 1示 如 圖 4.19(a)所 示， 后 序 線(xiàn) 索 二 叉 樹(shù) 的 鏈 接 表 示 如 圖4.19(b)所示。在圖針用虛線(xiàn)箭頭表示。1 BPred11 BPredPred 14.19 中指向一結(jié)點(diǎn)前驅(qū)或后繼結(jié)點(diǎn)的指0C0Succ1rootA 0Pred01 E(a) 改進(jìn)的中序線(xiàn)索二叉樹(shù)root0 A 0Succ0 0SuccSuccC 1 1 E(b) 改進(jìn)的后序線(xiàn)索二叉樹(shù)圖 4.19 改進(jìn)的線(xiàn)索二叉樹(shù)在改進(jìn)的中序線(xiàn)索二叉樹(shù)（圖 4.19(a)）中，有兩個(gè)空指針，它們分別是

43、中根遍歷序列的第一個(gè)結(jié)點(diǎn)的 Left 指針和最后一個(gè)結(jié)點(diǎn)的 Right 指針。因此，可設(shè)置一個(gè)所謂的表頭結(jié)點(diǎn) root （文中常將指向某結(jié)點(diǎn) p 的指針，簡(jiǎn)稱(chēng)為 p 的名字） ，讓這兩個(gè)指針指向 root，同時(shí)令 root結(jié)點(diǎn)的 Left 指針指向線(xiàn)索二叉樹(shù)的根結(jié)點(diǎn)，并令 root結(jié)點(diǎn)的 Right 指針指向中根遍歷線(xiàn)索二叉樹(shù)的最后一個(gè)結(jié)點(diǎn)。這就像為二叉樹(shù)建立了一個(gè)雙向線(xiàn)索鏈表，既可從第一個(gè)結(jié)點(diǎn)起，沿著后繼進(jìn)行遍歷，又可從最后一個(gè)結(jié)點(diǎn)起沿著前驅(qū)進(jìn)行遍歷。4.3.3 線(xiàn)索二叉樹(shù)基本算法 查找中根序列的第一個(gè)和最后一個(gè)結(jié)點(diǎn)如何在一棵中序線(xiàn)索二叉樹(shù)中查找在中根遍歷順序下的第一個(gè)和最后一個(gè)結(jié)點(diǎn)呢？從二

44、叉樹(shù)根結(jié)點(diǎn)出發(fā)，沿左指針鏈往下查找，直至找到一個(gè)沒(méi)有左孩子的結(jié)點(diǎn)為止，它是中根遍歷順序下二叉樹(shù)中第一個(gè)被訪(fǎng)問(wèn)的結(jié)點(diǎn)； 即從二叉樹(shù)根結(jié)點(diǎn)出發(fā)，沿右指針鏈往下查找，直至找到一個(gè)沒(méi)有右孩子的結(jié)點(diǎn)為止， 它是中根遍歷順序下二叉樹(shù)中最后被訪(fǎng)問(wèn)的結(jié)點(diǎn)。 算法 FIO 和算法 LIO 正是根據(jù)這些思想設(shè)計(jì)的。算法 FIO ( t . q )/* t指向中序線(xiàn)索二叉樹(shù) T* 之根，本算法返回 T* 的中根序列的首結(jié)點(diǎn)，并用 q指向它 */FIO1. 初始化 q t .FIO2. 找中根遍歷順序下二叉樹(shù)中第一個(gè)被訪(fǎng)問(wèn)的結(jié)點(diǎn) WHILE LThread (q) 0 DO q Left (q).RETURN q .

45、?算法 LIO ( t . q )/* 給定中序線(xiàn)索二叉樹(shù) T*， t指向 T* 之根，本算法返回 T* 的中根序列末結(jié)點(diǎn)，并用 q指向它 */LIO1. 初始化 q t .LIO2. 找中根遍歷順序下二叉樹(shù)中最后被訪(fǎng)問(wèn)的結(jié)點(diǎn) WHILE RThread(q ) 0 DO q Right (q) .RETURN q .?1 BPred100E 查找中序前驅(qū)結(jié)點(diǎn)和中序后繼結(jié)點(diǎn)在中序線(xiàn)索二叉樹(shù)中，查找結(jié)點(diǎn)要思想如下：若結(jié)點(diǎn) p 是中根序列的第一個(gè)結(jié)點(diǎn)，則 1 */若結(jié)點(diǎn) p非中根序列的第一個(gè)結(jié)點(diǎn)：p 的中序前驅(qū)結(jié)點(diǎn)的主p無(wú)中序前驅(qū)結(jié)點(diǎn)； /* 情況若 LThread(p) 1，則 Left(p)為

46、左線(xiàn)索，直接指向 p的中序前驅(qū)結(jié)點(diǎn)； /* 情況 2 */若 LThread(p) 0， p的中序前驅(qū)結(jié)點(diǎn)是 p之左子樹(shù)中根序列的末結(jié)點(diǎn) . /* 情況 3 */例如，圖 4.19 (a)中的 結(jié)點(diǎn) B 沒(méi)有中序前驅(qū)結(jié)點(diǎn)，對(duì)應(yīng)于第一種情況； 結(jié)點(diǎn) C 的左指針為左線(xiàn)索，直接指向其中序前驅(qū)結(jié)點(diǎn) B，對(duì)應(yīng)于第二種情況； 結(jié)點(diǎn)根遍歷順序下其左子樹(shù)的最后一個(gè)結(jié)點(diǎn)情況。root0 A 0PredSuccC 1 1(a) 改進(jìn)的中序線(xiàn)索二叉樹(shù)A 的中序前驅(qū)是中C，對(duì)應(yīng)于第三種D 1Succ1算法 PIO( t , p . q )/* 給定中序線(xiàn)索二叉樹(shù) T*， t指向 T* 之根，本算法搜索 T* 之結(jié)點(diǎn)

47、 p的中根前驅(qū)結(jié)點(diǎn)，令 q指向該前驅(qū) */PIO1. 求 T* 之中根序列首結(jié)點(diǎn) FIO ( t . first ).PIO2. p first？ IF p first THEN ( q . RETURN q .)PIO3. 取 p之左指針 lp Left (p) .PIO4. LThread(p) 1?IF LThread(p) 1 THEN ( q lp . RETURN q .)ELSE ( LIO ( lp . q ). RETURN q .) ?在中序線(xiàn)索二叉樹(shù)中，找結(jié)點(diǎn) p 的中序后繼結(jié)點(diǎn)的主要思想如下：若結(jié)點(diǎn) p是中序序列的末結(jié)點(diǎn)，則其無(wú)后繼結(jié)點(diǎn)； /* 情況 1 */若結(jié)點(diǎn) p

48、非中序序列的末結(jié)點(diǎn)：若 RThread(p) 1，則 Right(p) 指向 p 之中序后繼 /* 情況 2， Right(p)為右線(xiàn)索 */若 RThread(p) 0，則 p之中序后繼為 p 的右子樹(shù)的中根序列的首結(jié)點(diǎn)。 /* 情況 3 */例如，圖 4.19(a)中的結(jié)點(diǎn) D 沒(méi)有中序后繼結(jié)點(diǎn)，對(duì)應(yīng)于第一種情況；結(jié)點(diǎn) C 的右指針為右線(xiàn)索，直接指向其中序后繼結(jié)點(diǎn) A，對(duì)應(yīng)于第二種情況；結(jié)點(diǎn) A 的中序后繼是中根序列下其右子樹(shù)的首結(jié)點(diǎn) E，對(duì)應(yīng)于第三種情況 .算法 NIO* ( t , p . q)/* 給定中序線(xiàn)索二叉樹(shù) T*， t指向 T* 之根，本算法在 T* 中搜索其 結(jié)點(diǎn) p的中

49、序后繼，并令 q指向該后繼 */NIO*1. 求中根序列末結(jié)點(diǎn) LIO ( t . last ).NIO*2. p last? IF p lastTHEN ( q . RETURN q . )NIO*3. 取 p之右指針 rp Right (p) .NIO*4. RThread(p) 1?IF RThread(p) 1THEN ( q rp . RETURN q .) /* r p是右線(xiàn)索，它指向 p之后繼 */ELSE ( FIO (rp . q). RETURN q .) /* p之后繼是以 rp為根的二 叉樹(shù)的中根序列首結(jié)點(diǎn) */ ? 查找后序前驅(qū)和后繼結(jié)點(diǎn)在后序線(xiàn)索二叉樹(shù)中，查找結(jié)點(diǎn)主

50、要思想如下：若結(jié)點(diǎn) p 是后序序列首結(jié)點(diǎn)，則1 */p 之后序前驅(qū)結(jié)點(diǎn)的p 無(wú)后序前驅(qū)； /* 情況若結(jié)點(diǎn) p非后序序列首結(jié)點(diǎn)：若 LThread(p) 1，則 Left (p)指向 p 的后序前驅(qū)結(jié)點(diǎn)；/* 情況 2， Left (p)為左線(xiàn)索 */若 LThread(p) 0，則：/* 此時(shí) p有左子樹(shù) . 后序遍歷， p之后序前驅(qū)必是兩子樹(shù)中最后被遍歷的結(jié)點(diǎn)，情況 3 */若 p有右子樹(shù)，則 p之右孩子是其后序前驅(qū)；若 p無(wú)右子樹(shù)，則 p之后序前驅(qū)是其左孩子 .例如，圖 4.19 (b)中的結(jié)點(diǎn) C 沒(méi)有后序前驅(qū)結(jié)點(diǎn)，對(duì)應(yīng)于第一種情況；結(jié)點(diǎn) B 的左指針為左線(xiàn)索，直接指向其后序前驅(qū)結(jié)點(diǎn) C，對(duì)應(yīng)于第二種情況；結(jié)點(diǎn) A