數(shù)據(jù)結(jié)構(gòu)-第四章樹(shù)微軟2010版2013ldy

第1頁(yè)4.1樹(shù)的基本概念4.2二叉樹(shù)(BinaryTree)4.3線索二叉樹(shù)(ThreadedBinaryTree)4.4樹(shù)與森林(Tree&Forest)4.5壓縮與哈夫曼樹(shù)(HuffmanTree)4.6應(yīng)用第四章樹(shù)第2頁(yè)在現(xiàn)實(shí)世界中，樹(shù)（或曰樹(shù)結(jié)構(gòu)）大量存在，例如用樹(shù)可形象地表示家譜、行政組織機(jī)構(gòu)、著作目錄等。樹(shù)在計(jì)算機(jī)領(lǐng)域中也有著廣泛的應(yīng)用，例如在編譯程序中，用樹(shù)來(lái)表示源程序的語(yǔ)法結(jié)構(gòu)；在數(shù)據(jù)庫(kù)系統(tǒng)中，可用樹(shù)來(lái)組織信息；在分析算法的行為時(shí)，可用樹(shù)來(lái)描述其執(zhí)行過(guò)程。緒論第3頁(yè)例1.大學(xué)層次結(jié)構(gòu)吉林大學(xué)人文學(xué)部哲學(xué)社會(huì)學(xué)院文學(xué)院外國(guó)語(yǔ)學(xué)院藝術(shù)學(xué)院體育學(xué)院社會(huì)科學(xué)部文學(xué)院外國(guó)語(yǔ)學(xué)院藝術(shù)學(xué)院體育學(xué)院理學(xué)部數(shù)學(xué)學(xué)院物理學(xué)院化學(xué)學(xué)院生命科學(xué)學(xué)院第4頁(yè)下圖給出了Joe(喬)的后代的層次結(jié)構(gòu),其中Joe在頂層,Joe的孩子Ann(安),Mary(瑪麗)和John(約翰)列在下一層,在父母和孩子間有一條邊.在層次表示中,很容易找到Ann的兄弟姐妹,Joe的后代,Chris(克里斯)的祖先等.例2.Joe的后代JoeAnnMaryJohnMarkSueChris第5頁(yè)總裁銷(xiāo)售副總裁市場(chǎng)副總裁財(cái)務(wù)副總裁開(kāi)發(fā)副總裁例3.

某公司組織管理機(jī)構(gòu)某公司中地位最高的人為總裁，在最高處；副總裁的地位次之，位于總裁之下.副總裁為總裁的下屬，總裁是其上級(jí)。每個(gè)副總裁都有自己的下屬，而其下屬又可能有自己的下屬。圖中,每個(gè)員工若有直接下屬或直接上級(jí)，則兩者間有一條邊互連。第6頁(yè)聯(lián)邦政府國(guó)防部教育部稅務(wù)部陸軍海軍空軍海軍陸戰(zhàn)隊(duì)下圖是聯(lián)邦政府層次結(jié)構(gòu)圖.頂層元素(亦稱(chēng)機(jī)構(gòu))是聯(lián)邦政府，下一級(jí)是其主要的隸屬單位，如不同的部.每個(gè)部可進(jìn)一步劃分，其分支在下一層示出.例如國(guó)防部包括陸軍,海軍,空軍和海軍陸戰(zhàn)隊(duì).每個(gè)機(jī)構(gòu)，若有分支機(jī)構(gòu)，則兩者間有一條邊。下圖展現(xiàn)了諸元素間的整體-部分關(guān)系.例4.政府機(jī)構(gòu)第7頁(yè)文字處理器文件字體導(dǎo)入光標(biāo)OpenNewSavePrintQuit例5.某文字處理軟件結(jié)構(gòu)下圖給出了某文字處理器的一種模塊分解圖.文字處理器是最頂層模塊,在其下層被劃分成4個(gè)模塊.文件模塊完成與文本文件有關(guān)的操作,如Open,New,Save,Print和Quit等.字體模塊包括與字體處理有關(guān)的所有功能模塊,且它們?cè)谧煮w模塊的下一層.導(dǎo)入模塊用于處理圖形、表格及其他格式的文本文件.光標(biāo)模塊處理屏幕上光標(biāo)的移動(dòng).在接口設(shè)計(jì)好之后,程序員可以相對(duì)獨(dú)立的方式分析、設(shè)計(jì)和開(kāi)發(fā)每個(gè)模塊.

第8頁(yè)軟件的模塊化技術(shù).一方面，模塊化的目標(biāo)是將大而復(fù)雜的軟件系統(tǒng)，分解成許多功能獨(dú)立，較簡(jiǎn)單、較小的模塊，使多人同時(shí)并行開(kāi)發(fā)不同的模塊，可大大縮短整個(gè)軟件的開(kāi)發(fā)時(shí)間.另一方面，分開(kāi)測(cè)試一些小而獨(dú)立的模塊比測(cè)試一個(gè)大而復(fù)雜的模塊要容易得多，有利于保障開(kāi)發(fā)的正確性。第9頁(yè)4.1樹(shù)的基本概念4.2二叉樹(shù)4.3線索二叉樹(shù)4.4樹(shù)和森林4.5壓縮與哈夫曼樹(shù)4.6

應(yīng)用第10頁(yè)樹(shù)的遞歸定義定義4.1.1：一個(gè)樹(shù)(或曰樹(shù)形)就是一個(gè)有限非空的結(jié)點(diǎn)集合T，其中：有一個(gè)特別標(biāo)出的被稱(chēng)為該樹(shù)之根root(T)的結(jié)點(diǎn)；除根之外的其余結(jié)點(diǎn)被分成m0個(gè)不相交的集合T1,T2,…,Tm，且T1,T2,…,Tm又都是樹(shù).樹(shù)T1,T2,…,Tm被稱(chēng)作root(T)的子樹(shù)(或曰子樹(shù)形).4.1.1

樹(shù)的定義第11頁(yè)定義4.1.2

樹(shù)是包含n1個(gè)結(jié)點(diǎn)且滿足如下條件的有限集合:存在唯一的結(jié)點(diǎn)v0,它無(wú)前驅(qū)結(jié)點(diǎn),稱(chēng)為樹(shù)的根(或曰根結(jié)點(diǎn))；任何非根結(jié)點(diǎn)都有且僅有一個(gè)前驅(qū)結(jié)點(diǎn)，稱(chēng)為該結(jié)點(diǎn)的父結(jié)點(diǎn)；若某結(jié)點(diǎn)無(wú)后繼結(jié)點(diǎn),則稱(chēng)之為葉結(jié)點(diǎn);任何非葉結(jié)點(diǎn)P都有1個(gè)后繼結(jié)點(diǎn),稱(chēng)其為P的子結(jié)點(diǎn);任一非根結(jié)點(diǎn)vk都有且僅有一條從v0到vk的結(jié)點(diǎn)序列(或曰路徑)v0

v1

…

vk,其中vi是vi1(1

i

k)

的子結(jié)點(diǎn)。樹(shù)的非遞歸定義線性結(jié)構(gòu)樹(shù)結(jié)構(gòu)首結(jié)點(diǎn)(無(wú)前驅(qū))根結(jié)點(diǎn)(無(wú)前驅(qū))最后1個(gè)元素(無(wú)后繼)葉子結(jié)點(diǎn)可能多個(gè)(無(wú)后繼)其它數(shù)據(jù)元素(一個(gè)前驅(qū),一個(gè)后繼)樹(shù)中其它結(jié)點(diǎn)(一個(gè)前驅(qū),多個(gè)后繼)樹(shù)與線性結(jié)構(gòu)的比較第12頁(yè)1、結(jié)點(diǎn)的度與樹(shù)的度一個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)的數(shù)目,被稱(chēng)為該結(jié)點(diǎn)的度或曰次數(shù).一棵樹(shù)的度為maxi

1nD(i),其中n為樹(shù)中結(jié)點(diǎn)總數(shù),i指樹(shù)中的第i個(gè)結(jié)點(diǎn),D(i)表結(jié)點(diǎn)i的度.2、葉結(jié)點(diǎn)與分支結(jié)點(diǎn)度為零的結(jié)點(diǎn)被稱(chēng)為葉結(jié)點(diǎn)；度大于零的結(jié)點(diǎn)被稱(chēng)為分支結(jié)點(diǎn).4.1.2樹(shù)的相關(guān)術(shù)語(yǔ)第13頁(yè)3．結(jié)點(diǎn)的層數(shù)樹(shù)形T中結(jié)點(diǎn)的層數(shù)遞歸定義如下：⑴root(T)層數(shù)為零；⑵其余結(jié)點(diǎn)的層數(shù)為其前驅(qū)結(jié)點(diǎn)的層數(shù)加1.第14頁(yè)在圖4.1所示的樹(shù)T中：B有一個(gè)子結(jié)點(diǎn)E，度為1；A有三個(gè)子結(jié)點(diǎn)B,C和D(換言之,A是B,C和D的父結(jié)點(diǎn))度為3；因?yàn)樵赥中,結(jié)點(diǎn)A的子結(jié)點(diǎn)數(shù)最多,故這棵樹(shù)的度為3.T

中F,G,H,I

為葉結(jié)點(diǎn),其余結(jié)點(diǎn)為分支結(jié)點(diǎn).T中,結(jié)點(diǎn)A

為樹(shù)T

之根,其層數(shù)為零;結(jié)點(diǎn)F的層數(shù)為3.第15頁(yè)圖4.1樹(shù)TACB層數(shù)0層數(shù)1DEGHIF層數(shù)2層數(shù)3T中,結(jié)點(diǎn)A的子結(jié)點(diǎn)數(shù)最多,故T的度為3第16頁(yè)4．邊，路徑，路徑長(zhǎng)度樹(shù)形中結(jié)點(diǎn)間的連線被稱(chēng)為邊。若樹(shù)T中存在結(jié)點(diǎn)序列vm

vm1…

vmk，1

k

T的最大層數(shù)，滿足vi1是vi（m

i

mk1）的子結(jié)點(diǎn)，則稱(chēng)此結(jié)點(diǎn)序列為vm到vmk的路徑，該路徑所經(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).第17頁(yè)一個(gè)結(jié)點(diǎn)到它的某個(gè)子孫結(jié)點(diǎn)有且僅有一條路徑.樹(shù)中結(jié)點(diǎn)間的父子關(guān)系具有如下特征：樹(shù)中任一結(jié)點(diǎn)都可有零個(gè)或多個(gè)直接后繼(即子結(jié)點(diǎn)),但至多只能有一個(gè)直接前驅(qū)(即父結(jié)點(diǎn)).樹(shù)中只有根結(jié)點(diǎn)無(wú)前驅(qū),它是始結(jié)點(diǎn);葉結(jié)點(diǎn)無(wú)后繼,它們是終結(jié)點(diǎn).樹(shù)中某些結(jié)點(diǎn)之間具有父子關(guān)系或者祖先、子孫關(guān)系，祖先、子孫關(guān)系是父子關(guān)系的擴(kuò)展,一些結(jié)點(diǎn)間,如兄弟結(jié)點(diǎn)(同一父親的諸子結(jié)點(diǎn)被稱(chēng)為兄弟結(jié)點(diǎn))之間就沒(méi)有這種關(guān)系。第18頁(yè)6．樹(shù)的高度樹(shù)的高度為maxi

1nNL(i),其中n為樹(shù)中結(jié)點(diǎn)總數(shù),i指樹(shù)中第i個(gè)結(jié)點(diǎn),NL(i)之值為結(jié)點(diǎn)i的層數(shù).換言之,樹(shù)的高度指樹(shù)中結(jié)點(diǎn)的最大層數(shù).第19頁(yè)A(B,C(D,E))3樹(shù)的表示:

1.集合嵌套表示法2.凹入表示法3.廣義表表示法4.樹(shù)形表示法BDE1ACABDE2CABCDE4第20頁(yè)樹(shù)的基本操作1、判樹(shù)空：TREEEMPTY(T)2、求根：ROOT(T)3、求樹(shù)的深度：TREEDEPTH(T)4、求結(jié)點(diǎn)的brothers:同一雙親的孩子互稱(chēng)5、求結(jié)點(diǎn)的雙親：PARENT(T,e)6、求結(jié)點(diǎn)的孩子：CHILD(T,e,i)7、建樹(shù):CREATE_TREE(T,T1,T2,…,Tm)8、遍歷樹(shù)：TRAVERSAL(T)第21頁(yè)4.2二叉樹(shù)(BinaryTree)4.2.1二叉樹(shù)的定義和主要性質(zhì)定義4.2.1二叉樹(shù)(形)是結(jié)點(diǎn)的有限集合，它或者是空集，或者由一個(gè)根及兩個(gè)不相交的稱(chēng)為這個(gè)根的左、右子樹(shù)形的二叉樹(shù)組成。第22頁(yè)二叉樹(shù)的五種不同形態(tài)LRRL(a)(b)(c)(d)(e)第23頁(yè)樹(shù)與二叉樹(shù)的主要區(qū)別：⑴二叉樹(shù)每個(gè)結(jié)點(diǎn)最多有2個(gè)子結(jié)點(diǎn)，樹(shù)則無(wú)此限制；⑵二叉樹(shù)中結(jié)點(diǎn)的子樹(shù)分成左子樹(shù)和右子樹(shù)，即使某結(jié)點(diǎn)只有一棵子樹(shù)，也要指明該子樹(shù)是左子樹(shù)，還是右子樹(shù)，就是說(shuō)二叉樹(shù)是有序的；⑶樹(shù)決不能為空(即樹(shù)不能為空集),它至少有一個(gè)結(jié)點(diǎn),而一棵二叉樹(shù)可以是空的(即可以為空集).第24頁(yè)A(a)(b)(c)(d)(e)ACBACBCBACBACB圖4.2.2含3個(gè)結(jié)點(diǎn)的所有二叉樹(shù)第25頁(yè)引理4.1二叉樹(shù)中層數(shù)為

i的結(jié)點(diǎn)至多有

2i個(gè),i0.證明：用數(shù)學(xué)歸納法。當(dāng)i0時(shí),至多有一個(gè)根結(jié)點(diǎn),其層數(shù)為0,因此當(dāng)

i0時(shí)引理成立.假定當(dāng)ik(k0)時(shí)引理成立，即第k層上至多有2k

個(gè)結(jié)點(diǎn)。對(duì)二叉樹(shù)的任意結(jié)點(diǎn)，其子結(jié)點(diǎn)個(gè)數(shù)最多為2,故第k1層上至多有22k2k+1

個(gè)結(jié)點(diǎn)，因此當(dāng)ik1時(shí)，引理成立。證畢?二叉樹(shù)的性質(zhì)第26頁(yè)高度為k(k1)的二叉樹(shù)中至少有k1個(gè)結(jié)點(diǎn).有k1個(gè)結(jié)點(diǎn)的二叉樹(shù)高度至多為k1.圖4.2.3

是高度為3,結(jié)點(diǎn)最少(4個(gè))的二叉樹(shù)之一.ABCD圖4.2.3有4個(gè)結(jié)點(diǎn)的二叉樹(shù)高度為3第27頁(yè)引理4.2

高度為k0的二叉樹(shù)至多有2k+11個(gè)結(jié)點(diǎn).根據(jù)引理4.2.1第0層上至多有20個(gè)結(jié)點(diǎn)，第1層上至多有21個(gè)結(jié)點(diǎn),……,第k層上至多有2k個(gè)結(jié)點(diǎn),因此，高度為k的二叉樹(shù)中至多有20＋21＋……+2k

2k+1－1個(gè)結(jié)點(diǎn)。證畢?第28頁(yè)證明：設(shè)T中,度為1的結(jié)點(diǎn)為n1個(gè),總邊數(shù)為e,則nn0+n1+n2

⑴非根結(jié)點(diǎn)有1條邊與父結(jié)點(diǎn)相連,有en–1⑵顯然又有，e2n2+n1⑶由上諸式有2n2+n1=n0+n1+n21

n2=n01n0=n2+1證畢?引理4.3任一有n個(gè)結(jié)點(diǎn)的二叉樹(shù),其中葉結(jié)點(diǎn)數(shù)為n0,度為2的結(jié)點(diǎn)數(shù)為n2,則有n0n21第29頁(yè)滿二叉樹(shù)定義4.4一棵非空高為k（k

0）,具有2k+11個(gè)結(jié)點(diǎn)的二叉樹(shù)，被稱(chēng)為滿二叉樹(shù)。第30頁(yè)712345689101112131415非空高為k二叉樹(shù)至多有2k+11個(gè)結(jié)點(diǎn).滿二叉樹(shù)的特點(diǎn)是：葉結(jié)點(diǎn)都在第k層上；每個(gè)分支結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)；葉結(jié)點(diǎn)的個(gè)數(shù)等于非葉結(jié)點(diǎn)個(gè)數(shù)加1(對(duì)滿二叉樹(shù)而言，除葉結(jié)點(diǎn)外，其它結(jié)點(diǎn)的度均為2.見(jiàn)引理4.3).第31頁(yè)層次順序:按從上至下,即從第0至第k層，每層由左到右的次序.定義4.5

一棵有n個(gè)結(jié)點(diǎn)、高為k的二叉樹(shù)T,一棵高為k的滿二叉樹(shù)T*,用正整數(shù)按層次順序分別編號(hào)T和T*的所有結(jié)點(diǎn),如果T之所有結(jié)點(diǎn)恰好對(duì)應(yīng)于T*的前n個(gè)結(jié)點(diǎn)，則稱(chēng)T為完全二叉樹(shù).完全二叉樹(shù)顯然,滿二叉樹(shù)一定是完全二叉樹(shù).第32頁(yè)第33頁(yè)71234568910111213141512345678910完全二叉樹(shù)滿二叉樹(shù)包含n個(gè)結(jié)點(diǎn)、高為k的完全二叉樹(shù)的特點(diǎn)：樹(shù)中只有最下面兩層結(jié)點(diǎn)的度可小于2；樹(shù)中最下面一層的結(jié)點(diǎn)都集中在該層最左邊

的若干位置上；樹(shù)中葉結(jié)點(diǎn)只能出現(xiàn)在層數(shù)最大、次大的兩層上，即存在一個(gè)整數(shù)m0使得樹(shù)中每個(gè)葉結(jié)點(diǎn)在第m或第m1層上；對(duì)樹(shù)中所有結(jié)點(diǎn),按層次順序,用正整數(shù)從1開(kāi)始編號(hào),僅僅編號(hào)最大的非葉結(jié)點(diǎn)可無(wú)右孩子,其余非葉結(jié)點(diǎn)都有兩個(gè)孩子結(jié)點(diǎn)；在層次順序意義下,樹(shù)中所有結(jié)點(diǎn)對(duì)應(yīng)于高為k的滿二叉樹(shù)中編號(hào)由1至n的那些結(jié)點(diǎn)。第34頁(yè)引理4.4將一棵有n

個(gè)結(jié)點(diǎn)的完全二叉樹(shù),按層次順序用自然數(shù)從1開(kāi)始編號(hào)，則有：若1i

n,則編號(hào)為i之結(jié)點(diǎn)的父結(jié)點(diǎn)編號(hào)

為

i/

2

.若2i

n,且編號(hào)為i

的結(jié)點(diǎn)有左孩子,則其

左孩子的編號(hào)為2i．若2i1

n,且編號(hào)為

i

的結(jié)點(diǎn)有右孩子,則其右孩子的編號(hào)為2i+1．僅編號(hào)最大的非葉結(jié)點(diǎn)可無(wú)右孩子,但必須有

左孩子,其余非葉結(jié)點(diǎn)都有兩個(gè)孩子結(jié)點(diǎn).第35頁(yè)用歸納法證明引理4.4:若i

1，n2，則其左孩子的編號(hào)顯然為2.假定對(duì)所有

j(1

ji,2i

n),其左孩子編號(hào)為2j.如果

2(i1)n

,那么對(duì)結(jié)點(diǎn)

ji1,往證其左孩子的編號(hào)為2(i1).由層次順序知,i1的左孩子之前的兩個(gè)結(jié)點(diǎn)就是i的左孩子和右孩子,由歸納假設(shè)知i

的左孩子編號(hào)為2i,故i

的右孩子編號(hào)為2i1,從而i1的左孩子編號(hào)為2i22(i1).其它條款可仿證.證畢?第36頁(yè)引理4.5具有n

個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的高度是log2n.證明：設(shè)二叉樹(shù)高度為k

,

由定義4.5知,

完全二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)介于高度為k1和k

的滿二叉樹(shù)的結(jié)點(diǎn)數(shù)之間，即有：

2k

1

n

2k+1

1從而有2k

n

2k+1，即k

log2n

k+1，因?yàn)?/p>

k

為整數(shù)，故有k

log2n

.證畢?第37頁(yè)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)要存儲(chǔ)一棵二叉樹(shù)，需存儲(chǔ)其所有結(jié)點(diǎn)的數(shù)據(jù)信息，以及其左、右孩子的地址。通常有兩種存儲(chǔ)方式：順序存儲(chǔ)鏈接存儲(chǔ)第38頁(yè)4.2.2二叉樹(shù)的順序存儲(chǔ)二叉樹(shù)的順序存儲(chǔ)(或曰順序存儲(chǔ)方式，順序存儲(chǔ)方法)：

系指將二叉樹(shù)的所有結(jié)點(diǎn)按層次順序存放在一塊地址連續(xù)的存儲(chǔ)空間中，同時(shí)要反映出二叉樹(shù)中結(jié)點(diǎn)間的邏輯關(guān)系。第39頁(yè)對(duì)于任一完全二叉樹(shù)T,結(jié)點(diǎn)的層次順序反映了

其結(jié)構(gòu),可按層次順序給出其結(jié)點(diǎn)編號(hào):這就是

T的順序存儲(chǔ)方式,結(jié)點(diǎn)編號(hào)恰好反映了

T

結(jié)

點(diǎn)間的邏輯關(guān)系。若對(duì)完全二叉樹(shù)T之結(jié)點(diǎn)按層次順序編號(hào),則

可用一維數(shù)組A對(duì)其進(jìn)行存儲(chǔ),A[i]存儲(chǔ)T中

編號(hào)為i的結(jié)點(diǎn)，其中A[1]存儲(chǔ)T的根結(jié)點(diǎn)；

若結(jié)點(diǎn)A[i]有左孩子，則其存放在A[2i]處；若結(jié)點(diǎn)A[i]有右孩子,則其存放在A[2i1]處.第40頁(yè)圖4.2.5完全二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)(b)圖(a)的順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)ABECDA[1]A[2]A[3]A[4]A[5]1(a)5個(gè)結(jié)點(diǎn)的完全二叉樹(shù)EBACD2345第41頁(yè)結(jié)點(diǎn)值3123126694175706249結(jié)點(diǎn)編號(hào)12345678910106649311294175706212345672389哪個(gè)是編號(hào)最大的非葉結(jié)點(diǎn)？第42頁(yè)若將上述方法用于非完全二叉樹(shù),卻有很多缺點(diǎn).如果采用上述順序存儲(chǔ)方式，按層次順序，對(duì)非完全二叉樹(shù)之結(jié)點(diǎn)進(jìn)行編號(hào)，則編號(hào)不能表達(dá)結(jié)點(diǎn)間的邏輯關(guān)系.為此先通過(guò)添加虛結(jié)點(diǎn)將其轉(zhuǎn)換成一棵“完全二叉樹(shù)”,然后再對(duì)原來(lái)的結(jié)點(diǎn)和虛結(jié)點(diǎn)統(tǒng)一編號(hào),最后完成順序存儲(chǔ)。但這無(wú)疑增加了用于存儲(chǔ)虛結(jié)點(diǎn)的空間。第43頁(yè)(a)

非完全二叉樹(shù)ABCDA[1]A[3]A[7]A[15](c)非完全二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)轉(zhuǎn)換(b)完全二叉樹(shù)ABCDABCD第44頁(yè)二叉樹(shù)鏈接存儲(chǔ)系指二叉樹(shù)的諸結(jié)點(diǎn)被隨機(jī)存放在內(nèi)存空間中,用指針指明結(jié)點(diǎn)間的邏輯關(guān)系.二叉樹(shù)的結(jié)點(diǎn)結(jié)構(gòu)

在二叉樹(shù)的鏈接存儲(chǔ)中，結(jié)點(diǎn)包含三個(gè)域，數(shù)據(jù)域data、左指針域left和右指針域right，其中左、右指針?lè)謩e指向該結(jié)點(diǎn)的左、右子樹(shù)的根結(jié)點(diǎn)；結(jié)點(diǎn)結(jié)構(gòu)圖示如下：4.2.3二叉樹(shù)鏈接存儲(chǔ)第45頁(yè)leftdataright常用data字段值表示結(jié)點(diǎn)的名字.如在右圖第2層最左邊的結(jié)點(diǎn)C中,left域中的表示C的左子樹(shù)為空,right域的表示C的右子樹(shù)為空.ABCDEFG第46頁(yè)CABDEFG二叉樹(shù)鏈接存儲(chǔ)結(jié)構(gòu)Leftdataparentright另一種結(jié)點(diǎn)結(jié)構(gòu)：結(jié)點(diǎn)包括三個(gè)指針域,parent域中指針指向其父結(jié)點(diǎn)第47頁(yè)算法Father(t,p.q)/*指針t指向二叉樹(shù)T之根;Father使用遞歸在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)p

THEN

(q

t.

RETURN.).Father3.[遞歸]Father(Left

(

t

)

,p

.qL).IFqL

THEN(q

qL

.RETURN.).Father(Right

(

t

),p

.qR).q

qR

.?①在二叉樹(shù)中搜索給定結(jié)點(diǎn)的父結(jié)點(diǎn)第48頁(yè)問(wèn)題：為什么需要淺綠色語(yǔ)句?②搜索二叉樹(shù)中符合數(shù)據(jù)域條件的結(jié)點(diǎn)算法Find(t,item

.q

)/*指針t指向二叉樹(shù)T之根,Find在T中搜索Data

域之值為item的結(jié)點(diǎn),指針q指向該結(jié)點(diǎn)*/Find1.[t

?]IFt

THEN(q

.RETURN.

).IFData(

t

)

itemTHEN(q

t

.RETURN.

).Find2.[遞歸]Find

(

Left(t),item

.p

).IFp

THEN

(q

p

.RETURN.

).Find

(Right(t),item

.q

).?第49頁(yè)③從二叉樹(shù)中刪除給定結(jié)點(diǎn)及其左右子樹(shù)算法DST(t)/*root指向二叉樹(shù)T之根，DST從T中

刪除給定結(jié)點(diǎn)t及其左右子樹(shù)*/DST1.[t

?]IFt

THENRETURN.DST2.[t

root?]IFt

rootTHEN(Del(t).root

.RETURN.)DST3.[找t的父親q]p

t.Father(root,p.q).DST4.[修改q的指針域]IFLeft(q)

pTHENLeft(q)

.IFRight(q)

pTHENRight(q)

.DST5.[刪除p及其子樹(shù)]Del(p).?第50頁(yè)算法Del(p)//刪除結(jié)點(diǎn)p及其左右子樹(shù)Del1.[p

?]IFp

THENRETURN.Del2.[遞歸刪除]Del(Left(p)).Del(Right(p)).AVAIL

p.?假定，當(dāng)前p指向結(jié)點(diǎn)C第51頁(yè)AGBCDEF二叉樹(shù)的遍歷：按照一定次序訪問(wèn)樹(shù)中所有結(jié)點(diǎn)，且使每個(gè)結(jié)點(diǎn)恰好被訪問(wèn)一次。以先根(中根、后根)次序遍歷二叉樹(shù)T,得到T之

結(jié)點(diǎn)的一個(gè)序列,稱(chēng)為T(mén)的先根(中根、后根)序列.遍歷方式先根遍歷：

DLR中根遍歷：

LDR后根遍歷：

LRD4.2.4二叉樹(shù)的遍歷D二叉樹(shù)RL第52頁(yè)當(dāng)二叉樹(shù)為空則什么都不做,否則遍歷分三步進(jìn)行：二叉樹(shù)之先根,中根和后根遍歷定義先根序中根序后根序步驟一訪問(wèn)根以中根序遍歷左子樹(shù)以后根序遍歷左子樹(shù)步驟二以先根序遍歷左子樹(shù)訪問(wèn)根以后根序遍歷右子樹(shù)步驟三以先根遍歷右子樹(shù)以中根序遍歷右子樹(shù)訪問(wèn)根第53頁(yè)+ABEFDC圖4.11

表達(dá)式(A+B)((CD)E+F)對(duì)應(yīng)的二叉樹(shù)第54頁(yè)例：先根序遍歷得到的結(jié)點(diǎn)序列：ABCDEF中根序遍歷得到的結(jié)點(diǎn)序列：A+BCDE+F后根序遍歷得到的結(jié)點(diǎn)序列：AB+CDEF+中根遍歷二叉樹(shù)算法框架:若二叉樹(shù)為空,則空操作;否則：中根遍歷左子樹(shù);訪問(wèn)根結(jié)點(diǎn);中根遍歷右子樹(shù).表達(dá)式語(yǔ)法樹(shù)的中根遍歷

結(jié)果：abcde/f中根遍歷(InorderTraversal,中序遍歷)表達(dá)式語(yǔ)法樹(shù)afbcde第55頁(yè)二叉樹(shù)結(jié)點(diǎn)在水平線上的投影即中序遍歷結(jié)果GKHAFEDCBCBDFE

AH

G

K第56頁(yè)這三種結(jié)點(diǎn)序列都非常重要，它們分別與表達(dá)式的前綴、中綴和后綴表示相對(duì)應(yīng)(其中,中綴表示還需要括號(hào)和優(yōu)先級(jí),稍有差別).

第57頁(yè)二叉樹(shù)遞歸的中根遍歷算法算法Inorder（t）/*;步驟中簡(jiǎn)記Inorder為INO

*/INO1.[遞歸出口]

//若二叉樹(shù)為空,則終止算法IFtNULLTHENRETURN.INO2.[遞歸遍歷]Inorder(left(t)).PRINT(data(t)).Inorder(right(t)).?第58頁(yè)二叉樹(shù)遞歸的先根遍歷算法算法Preorder（t）/*;步驟中簡(jiǎn)記Preorder

為PRO*/PRO1.[遞歸出口]//若二叉樹(shù)為空,終止算法IFtNULLTHENRETURN.PRO2.[遞歸遍歷]PRINT(data(t)).Preorder(left(t)).Preorder(right(t)).)?

第59頁(yè)二叉樹(shù)遞歸的后根遍歷算法算法Postorder（t）/*;步驟中簡(jiǎn)記Postorder

為POO*/POO1.[樹(shù)為空?]IFtNULLTHENRETURN.POO2.[后根遍歷子樹(shù)]Postorder(left(t)). Postorder(right(t)).POO4.[訪問(wèn)根]PRINT(data(t)).?

第60頁(yè)算法NIO(t)/*設(shè)t是指向一棵鏈接表示的二叉樹(shù)T

之根的指針,NIO利用一個(gè)輔助堆棧S以中根序訪問(wèn)

T

的所有結(jié)點(diǎn)*/NIO1.[初始化]CREATE

(

S

).p

t

.

//創(chuàng)建空棧S

NIO2.[入棧]

WHILE

p

DO(S

p.p

Left(p).

)//*一直往左下方NIO3.[棧為空?]

IF

S為空THEN

RETURN

ELSE

p

S.NIO4.

[訪問(wèn)p,更新p]PRINT(Data(

p

)).p

Right(

p

).NIO5.[返回]GOTONIO2.?非遞歸中根遍歷算法第61頁(yè)圖4.12非遞歸中根遍歷二叉樹(shù)(b)中根遍歷(a)中二叉樹(shù),堆棧內(nèi)容變化過(guò)程圖(b)中略去了進(jìn)棧過(guò)程的描述NIO2.[入棧]WHILEp

DO

(S

p.p

Left

(p).)NIO3.[棧為空?]若S為空,則RETURN.否則

p

S.NIO4.[訪問(wèn),更新p]打印

Data(p).

pRight(p).

返回NIO2.第62頁(yè)

(a)二叉樹(shù)ABCEFD

AB

A

AD

C

CE

A

F訪問(wèn)D訪問(wèn)A訪問(wèn)C訪問(wèn)F

A

ABA進(jìn)棧B進(jìn)棧訪問(wèn)B

ADD進(jìn)棧

CC進(jìn)棧E進(jìn)棧

CE訪問(wèn)EF進(jìn)棧

F

定理4.1設(shè)算法NIO從步驟NIO2開(kāi)始，p指向一棵有n個(gè)結(jié)點(diǎn)之二叉樹(shù)T*的根，此時(shí)棧S中有S[1],S[2],┅,S[m],m0.則步驟NIO2至NIO5將以中根序遍歷T*，并最后達(dá)到步驟NIO3，同時(shí)棧S也恢復(fù)到原來(lái)值S[1],S[2],┅,S[m].算法NIO正確性證明作業(yè)：讀書(shū)上之證明第63頁(yè)②非遞歸后根遍歷算法非遞歸后根遍歷算法需要一個(gè)輔助堆棧來(lái)記憶訪問(wèn)路徑，算法中棧元素結(jié)構(gòu)如下：樹(shù)中任一結(jié)點(diǎn)p都要進(jìn)棧三次，出棧三次.

第一次出棧是為遍歷p的左子樹(shù)；第二次出棧是為遍歷p的右子樹(shù)；第三次出棧是為訪問(wèn)p.其中i在集合{0,1,2}中取值,用來(lái)標(biāo)識(shí)p

的

出棧次數(shù).具體說(shuō)明如下：

結(jié)點(diǎn)

退棧次數(shù)

i第64頁(yè)初始化時(shí),將(根結(jié)點(diǎn),0)進(jìn)棧.

出棧,判斷出棧元素(p,i)中的標(biāo)號(hào)i：若i0,則(p,1)

進(jìn)棧;若p的左指針?lè)强?則

(Left(p),

0)

進(jìn)棧,準(zhǔn)備遍歷

p

的左子樹(shù)./*

若p有左子樹(shù),則其左子樹(shù)所有結(jié)點(diǎn)的二元組皆在p的二元組之上

*/

若i1,則(p,2)進(jìn)棧;若

p

的右指針?lè)强?則(Right(p),0)

進(jìn)棧,準(zhǔn)備遍歷

p

的右子樹(shù)./*

此時(shí)

p

的左子樹(shù)已被遍歷;若p有右子樹(shù),則其右子樹(shù)所有結(jié)點(diǎn)的二元組皆在p的二元組之上*/

若i

2,訪問(wèn)結(jié)點(diǎn)p.

//此時(shí)p

的左、右子樹(shù)都已被遍歷,自然應(yīng)訪問(wèn)根結(jié)點(diǎn)第65頁(yè)算法NPO(t)/*設(shè)二叉樹(shù)T以鏈接方式存儲(chǔ),指針t

指向T之根,算法NOP利用堆棧S以后根序遍歷T*/NPO1.[初始化]IFt

THENRETURN.CREATS(S).S

(t,0).NPO2.[后根遍歷]WHILE棧S非空DO((p,i)S.IFi0THEN(

S

(p

,

1).若left(p)則

S(left(p),0).).IFi1THEN//此時(shí)p

的左子樹(shù)已被遍歷(

S

(

p

,

2).若

right(

p)

則

S

(

right(

p),

0).).IFi2THEN//此時(shí)p

的右子樹(shù)已被遍歷PRINT(data(p)).).?WHILE的每次迭代中3個(gè)IF語(yǔ)句僅執(zhí)行一個(gè)第66頁(yè)

C,1A,2E,1

C,1A,2E,2訪E訪F訪C訪A

C,1A,2

C,2A,2F,0

C,2A,2F,1

C,2A,2F,2

C,2A,2

A,2

對(duì)左圖之二叉樹(shù)進(jìn)行后序遍歷,棧S之變化

A,0

B,0A,1

B,1A,1

B,2A,1D,0

B,2A,1D,1

B,2A,1D,2

B,2A,1

A,1

C,0A,2

C,1A,2E,0訪D訪BWHILE棧S非空DO//分別簡(jiǎn)記left、right為L(zhǎng)t和Rt(

(p,i)S.IFi0THEN

[S(p,1).

若

Lt

(p),則

S

(Lt(p),0).].IFi1THEN

[S(p,2).

若

Rt

(p),則

S

(Rt(p),0).].IFi2THEN

PRINT(data(p)).)?ABCDEF第67頁(yè)先根序列和中根序列可唯一確定一棵二叉樹(shù)ABDCEFKH[例]上圖二叉樹(shù)T的先序、中序遍歷結(jié)果:①先根序列A00BALCBRKCLDAREDLHELFDR②中根序列BALKCLCBRA00HELEDLDARFDR由①、②兩個(gè)序列可確定二叉樹(shù)的結(jié)構(gòu)。

由①知T之根為A,由②知A之左子樹(shù)包括B,K,C三個(gè)結(jié)點(diǎn)

其右子樹(shù)包含H,E,D,F四個(gè)結(jié)點(diǎn),再由①知A之左子樹(shù)的根為B，知A之右子樹(shù)的根為D，照此可確定出整個(gè)T之結(jié)構(gòu).譬如，F(xiàn)DR系指F是D的右孩子。A00系指T之根。第68頁(yè)后根序列和中根序列可唯一確定一棵二叉樹(shù)[例]

后根序列CEFDBHGA

中根序列CBEDFAGH第69頁(yè)后根序列CBLEDLFDRDBRBALHGRGARA00

中根序列CBLBALEDLDBRFDR

A00GARHGRAC

B

E

DFGHDEFABCGHABCGDEHF第70頁(yè)第71頁(yè)練習(xí)：已知某二叉樹(shù)的先序遍歷序列是ABDGCEFH，中序遍歷序列是DGBAECHF，它的后序遍歷序列是什么？給定一棵二叉樹(shù)T的先根序列和后根序列，那么能否由此確定出T之結(jié)構(gòu)？第72頁(yè)層次遍歷:按層數(shù)由小到大,即從第0層開(kāi)始逐層向下,同層中由左到右的次序訪問(wèn)二叉樹(shù)的所有結(jié)點(diǎn).遍歷結(jié)果:

ABECFDABECFD第73頁(yè)在第

i

層上若結(jié)點(diǎn)x

在結(jié)點(diǎn)y

的左邊，則x

一定在y

之前被訪問(wèn).同理,在第i1層上，x的孩子結(jié)點(diǎn)一定在y

的孩子結(jié)點(diǎn)之前被訪問(wèn).若訪問(wèn)i

層上的所有結(jié)點(diǎn)，必須知道i

層上所有結(jié)點(diǎn)的地址，地址保存在其父結(jié)點(diǎn)的left或right指針中。由①，算法可用先進(jìn)先出的隊(duì)列來(lái)實(shí)現(xiàn)；由②，除待遍歷二叉樹(shù)T的根結(jié)點(diǎn)之外，其余結(jié)點(diǎn)的地址均是其父結(jié)點(diǎn)的left或right.層次遍歷問(wèn)題的分析第74頁(yè)使用一個(gè)先進(jìn)先出結(jié)構(gòu)的隊(duì)列Q，具體如下：將根結(jié)點(diǎn)插入Q.重復(fù)執(zhí)行本步驟直至Q為空:若Q非空,取Q的頭結(jié)點(diǎn)n

并訪問(wèn);若n的左指針不空,將其左孩子插入Q;若n的右指針不空,將其右孩子插入Q.二叉樹(shù)層次遍歷算法的主要思想第75頁(yè)/*

算法LevelOrder按層次順序?qū)︽溄哟鎯?chǔ)的二叉樹(shù)T進(jìn)行遍歷，t

指向T

之根，Q

為隊(duì)列

*/LO1.[建空隊(duì)]CREATE(Q).LO2.[入隊(duì)]p

t.IF

p

THEN

Q

p.//T

之根入隊(duì)LO3.[層次遍歷]

WHILE

Q

非空DO(p

Q.PRINT(Data(p)).//取對(duì)頭并訪問(wèn)

IF

Left(p)

THEN

Q

Left(p).

IF

Right(p)

THEN

Q

Right(p).)?算法LevelOrder(t)第76頁(yè)由二叉樹(shù)的遍歷算法，很容易想到用遍歷方法去創(chuàng)建二叉樹(shù)。如，從先根遍歷思想出發(fā)構(gòu)造二叉樹(shù)。但先根序列不能唯一確定二叉樹(shù)的結(jié)構(gòu)，兩棵不同的二叉樹(shù)卻可能有相同的先根序列。

原因是：二叉樹(shù)中，可能有其左指針和/或右指針為空的結(jié)點(diǎn)，先根序列不包含這方面的信息。

由此：需在先根序列中加入特殊符號(hào)以示空指針位置，這里不妨用“#”號(hào)表示空指針位置。4.2.5創(chuàng)建二叉樹(shù)第77頁(yè)遞歸算法CreateBinTree（簡(jiǎn)記為CBT）以根指針t為輸入?yún)?shù)，以包含空指針信息的先根序列為輸入序列.當(dāng)讀入"#"字符時(shí)，將其初始化為一個(gè)空指針；否則生成一個(gè)新結(jié)點(diǎn)并初始化其父結(jié)點(diǎn)之左、右指針.由于序列中用"#"表示空指針，故在算法中設(shè)置tostop"#"，以便判斷序列中的"#"號(hào).當(dāng)輸入序列為ABD#E###C##時(shí),可創(chuàng)建下頁(yè)所示的二叉樹(shù).第78頁(yè)算法CBT(tostop.t)//構(gòu)造以結(jié)點(diǎn)t為根的二叉樹(shù)；tostop

‘#’CBT1.[讀數(shù)據(jù)]READ(ch).//順序讀入序列中的一個(gè)符號(hào)CBT2.[ch

tostop?]IFch

tostopTHEN(t

.RETURN.)ELSE(t

AVAIL.Data(t)

ch.)CBT3.[構(gòu)造左子樹(shù)]CBT(tostop.Left(t)).CBT4.[構(gòu)造右子樹(shù)]CBT(tostop.Right(t)).?

ABD#E###C##CBT(.t)

Data(t)A

CBT(.L(t))

Data(L(t))B

CBT(.L(L(t)))

Data(L(L(t)))D

CBT(.L(L(L(t)))).L(L(L(t))).

CBT(.R(L(L(t))))

Data(R(L(L(t))))E

CBT(L(R(L(L(t))))).L(R(L(L(t)))).

CBT(R(R(L(L(t))))).R(R(L(L(t)))).

CBT(.R(L(t))).

R(L(t)).

CBT(.R(t))

Data(R(t))C

CBT(.L(R(t))).

L(R(t)).

CBT(.R(R(t))).R(R(t)).?第79頁(yè)DBE####CA##ABD#E###C##簡(jiǎn)記Left,Right為L(zhǎng)和R;省略參數(shù)tostop,以及t

AVAIL等操作t第80頁(yè)設(shè)指針t指向一棵鏈接表示的二叉樹(shù)T，欲得到T的一個(gè)“備份”，則容易想到用先根、中根或后根遍歷二叉樹(shù)的解決方案。考慮到在創(chuàng)建二叉樹(shù)的算法中使用了先根遍歷的思想，這里最好嘗試其它遍歷方式，譬如說(shuō)“后根遍歷”。若采用后根遍歷方式，則復(fù)制過(guò)程如下：

①?gòu)?fù)制左子樹(shù)；

②復(fù)制右子樹(shù)；

③生成父結(jié)點(diǎn)，連接父結(jié)點(diǎn)和左右子樹(shù)之根結(jié)點(diǎn).4.2.6二叉樹(shù)遍歷的應(yīng)用：復(fù)制二叉樹(shù)第81頁(yè)

算法

CT(t.p)

/*t指向鏈接表示的二叉樹(shù)T之根，二叉樹(shù)T為T(mén)的復(fù)制品，

p指向T之根;在CT中，復(fù)制采用后根遍歷方式*/

CT1.[遞歸出口]IFt

THENRETURN.CT2.[復(fù)制左子樹(shù)]IFLeft(t)

THENCT(Left(t).lptr)ELSElptr

.CT3.[復(fù)制右子樹(shù)]IFRight(t)

THENCT(Right(t).rptr)ELSErptr

.CT4.[生成根結(jié)點(diǎn)]p

AVAIL.Data(p)

Data(t).Left(p)lptr.Right(p)rptr.RETURNp.?CT(t.p)//t

指向結(jié)點(diǎn)A

CT(L(t).lptr)

//步CTP2.L(t)B

具體見(jiàn)85頁(yè)

CT(R(t).rptr)

//步CTP3.R(t)D具體見(jiàn)86頁(yè)

pAVAIL.Data(p)

Data(t).

L(p)lptr.//此時(shí)L(p)指向結(jié)點(diǎn)B，見(jiàn)85頁(yè)R(p)rptr.

//此時(shí)R(p)指向結(jié)點(diǎn)D，見(jiàn)86頁(yè)

RETURNp.?//此時(shí)p指向結(jié)點(diǎn)ABACDE簡(jiǎn)記Left、Right為:L(t)和R(t)第82頁(yè)CT(L(t).lptr)

//L(t)B

lptr

//步CT2，L(L(t))

CT(R(L(t)).rptr)

lptr

//L(R(L(t)))

rptr

//R(R(L(t)))

pAVAIL.Data(p)Data(R(L(t))).//Data(p)C

L(p)lptr.R(p)rptr.

RETURNp.

//rptr

p

pAVAIL.Data(p)

Data(L(t)).//Data(p)B

L(L(t))

lptr.//L(L(t))

R(L(t))

rptr.

//R(L(t))指向結(jié)點(diǎn)C

RETURNp.//lptr

p，即

lptr

指向結(jié)點(diǎn)B第83頁(yè)簡(jiǎn)記Left、Right為:L(t)和R(t)BADECCT(R(t).rptr)

CT(L(R(t)).lptr)//L(R(t))E

lptr

.

//CT2.L(L(R(t))))

rptr

.

//CT3.R(L(R(t))))

pAVAIL.Data(p)Data(L(R(t))).//Data(p)E

L(p)

lptr.//lptr

R(p)

rptr.//rptr

RETURNp.

//lptrp，此時(shí)lptr指向結(jié)點(diǎn)ECT(R(R(t)).rptr)RETURN.//rptr

pAVAIL.Data(p)

Data(R(t)).//Data(p)D

L(p)

lptr.//此時(shí)L(p)

指向結(jié)點(diǎn)E

R(p)

rptr.

//R(p)RETURNp.//rptr

p，此時(shí)rptr指向結(jié)點(diǎn)D

BADCE第84頁(yè)第85頁(yè)用后序遍歷計(jì)算二叉樹(shù)結(jié)點(diǎn)個(gè)數(shù)算法Count(t.n)/**/IFtNULLTHEN(n0.RETURN.)Count(left(t).nl).Count(right(t).nr).n

nlnr1.▌編寫(xiě)計(jì)算二叉樹(shù)高度的算法[解題思路]二叉樹(shù)之深度可由如下公式求得：由此可見(jiàn)，該題可用遞歸算法求解。第86頁(yè)算法depth(t.d)/**/IFtTHEN(d1.RETURN.)ELSE(depth(left(t).d1).depth(right(t).d2).IF(d1>d2)THEN(dd11.RETURN.) ELSE(dd2+1.RETURN.)

)?

第87頁(yè)以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)。這種結(jié)構(gòu)的不足有二：

其一是，從一個(gè)結(jié)點(diǎn)出發(fā)只能訪問(wèn)它的孩子結(jié)點(diǎn)，而不能訪問(wèn)它的父結(jié)點(diǎn)；

其二是，這種結(jié)構(gòu)通常包含很多未被有效利用的指針字段，譬如包含i個(gè)結(jié)點(diǎn)的二叉樹(shù)，在其2i個(gè)指針字段中僅有i1個(gè)被使用.4.3線索二叉樹(shù)第88頁(yè)為使二叉樹(shù)之訪問(wèn)更方便,其空間利用率更高.1960年,珀利斯(A.J.Perlis)和桑頓(C.Thornton)提出了巧妙的線索二叉樹(shù)表示，并給出了以各種順序遍歷線索二叉樹(shù)的重要思想.但是珀利斯和桑頓提出的只是單向的線索二叉樹(shù).1963年，霍特(A.W.Holt)又提出了雙向線索二叉樹(shù)。第89頁(yè)第90頁(yè)象雙向鏈表一樣,二叉樹(shù)也可采用雙向鏈接.如下圖所示,針對(duì)某種遍歷順序,可為二叉樹(shù)的每個(gè)結(jié)點(diǎn)增加兩個(gè)指針域，分別存放指向其前驅(qū)和后繼結(jié)點(diǎn)的指針Pred和Succ，并稱(chēng)Pred和Succ為"線索".在這樣的二叉樹(shù)中,搜索一結(jié)點(diǎn)在某遍歷順序下的前驅(qū)或后繼將變得更加容易，但將增加一些存儲(chǔ)空間的開(kāi)銷(xiāo).LeftRight

DataPredSucc線索二叉樹(shù)定義4.6設(shè)T*是一棵二叉樹(shù)，其結(jié)點(diǎn)增加了針對(duì)某種遍歷順序的線索域，在T*中可直接查找任一結(jié)點(diǎn)在該遍歷順序下的前驅(qū)和后繼結(jié)點(diǎn)，稱(chēng)T*為線索二叉樹(shù)

(Threaded

BinaryTree).第91頁(yè)在一棵線索二叉樹(shù)中，若指針Pred和Succ分別指向結(jié)點(diǎn)的先根（中根、后根）前驅(qū)和先根（中根、后根）后繼，則稱(chēng)其為先序（中序、后序）線索二叉樹(shù).書(shū)上：圖4.21(a)所示二叉樹(shù)T之中根遍歷序列為BCAED，它的中序線索二叉樹(shù)的鏈接表示如圖4.21(b)所示；T的后根序列為CBEDA，它的后序線索二叉樹(shù)的鏈接表示如圖4.21(c)所示.

第92頁(yè)(a)

二叉樹(shù)ABDCEPredSuccPredrootSuccPred(b)中序線索二叉樹(shù)的鏈接表示中序序列：BCAEDDEACBSuccPredSucc圖4.21線索二叉樹(shù)的鏈接表示圖中虛線箭頭表示線索第93頁(yè)后序線索二叉樹(shù)的鏈接表示后序序列：

CBEDASuccPredSuccSuccPredSuccrootADBCEPredPred第94頁(yè)線索二叉樹(shù)的問(wèn)題與分析問(wèn)題：由圖4.21可見(jiàn)，線索二叉樹(shù)的結(jié)點(diǎn)中仍有很多空指針，就是說(shuō)存儲(chǔ)空間的浪費(fèi)問(wèn)題還未得到有效解決。分析：指針域需占用較多的存儲(chǔ)空間，如一個(gè)空間容量為4GB的內(nèi)存儲(chǔ)器需要32個(gè)二進(jìn)制位來(lái)表示地址，若將指針域中的Pred和Succ換成1個(gè)二進(jìn)制位則會(huì)節(jié)省許多空間。

第95頁(yè)10月22日講到這里線索二叉樹(shù)的改進(jìn)方案：將原指針域Pred和Succ分別改成存儲(chǔ)一個(gè)二進(jìn)制位的域LThread和RThread.若結(jié)點(diǎn)t有左孩子，則Left指向t的左孩子，且LThread值為0;若t沒(méi)有左孩子,

則Left指向t的前驅(qū)結(jié)點(diǎn),且LThread值為1，此時(shí)稱(chēng)Left為線索.若結(jié)點(diǎn)t有右孩子，則Right指向t的右孩子，且RThread值為0；若t沒(méi)有右孩子，則Right指向t的后繼結(jié)點(diǎn)，且RThread值為1，此時(shí)稱(chēng)Right為線索.第96頁(yè)圖4.22改進(jìn)后的線索二叉樹(shù)(b)改進(jìn)的中序線索二叉樹(shù)A00B10C11D01E11ABDCE(a)

二叉樹(shù)結(jié)點(diǎn)中為何出現(xiàn)?SuccPredPredSucc第97頁(yè)P(yáng)redSuccroot

(c)改進(jìn)后的后序線索二叉樹(shù)0A0D10B10E11C11SuccSuccPredABDCE(a)二叉樹(shù)為何Left域中放?第98頁(yè)在中序線索二叉樹(shù)中,不需要對(duì)二叉樹(shù)進(jìn)行遍歷就可方便地找到給定結(jié)點(diǎn)的中序前趨和中序后繼結(jié)點(diǎn)，且不需要太多的額外空間。在改進(jìn)的線索二叉樹(shù)中，一個(gè)結(jié)點(diǎn)是葉結(jié)點(diǎn)的充要條件是，其左、右標(biāo)志（LThread、RThread）均為1.第99頁(yè)[1]-1在以t

為根的中序線索二叉樹(shù)中，搜索中根順序的第一個(gè)結(jié)點(diǎn)算法思想：若t

有左子樹(shù)，則中根遍歷順序的第一個(gè)結(jié)點(diǎn)就是左子樹(shù)中最左邊的結(jié)點(diǎn)；若t

無(wú)左子樹(shù)，中根遍歷順序的第一個(gè)結(jié)點(diǎn)就是t.

4.3.3線索二叉樹(shù)基本算法第100頁(yè)算法FIO(t.q)/*t指向改進(jìn)的中序線索二叉樹(shù)T*之根，本算法返回T*的中根序列的首結(jié)點(diǎn)，并用q指向它*/FIO1.[初始化]q

t.FIO2.

[找中根序首結(jié)點(diǎn)]WHILELThread(q)0DOq

Left(q).RETURNq.?

第101頁(yè)WhileLThread(q)=0DOq

Left(q);A00B10C11D01E11t第102頁(yè)[1]-2搜索線索二叉樹(shù)T*之中根順序的最后一個(gè)結(jié)點(diǎn),設(shè)t

指向T*之根.算法思想：若t

有右子樹(shù)，則中根序末結(jié)點(diǎn)就是右子樹(shù)中最右邊的結(jié)點(diǎn)；若t無(wú)右子樹(shù)，中根序的末結(jié)點(diǎn)就是t.

第103頁(yè)算法LIO(t.q)/*給定改進(jìn)的中序線索二叉樹(shù)T*，t指向T*之根，LIO返回T*之中根序之末結(jié)點(diǎn)，并用q指向它*/LIO1.[初始化]q

t.LIO2.[找中根序末結(jié)點(diǎn)]WHILERThread(q)0DOq

Right(q).RETURNq.?第104頁(yè)解決該問(wèn)題的主要思路：若p是中根序首結(jié)點(diǎn)，則p無(wú)中序前驅(qū)結(jié)點(diǎn)；

//情況1若p非中根序首結(jié)點(diǎn)：若LThread(p)1，則Left(p)為左線索，直接指向p的中序前驅(qū)結(jié)點(diǎn)；//情況2若LThread(p)0，p的中序前驅(qū)結(jié)點(diǎn)是p之左子樹(shù)的中根序末結(jié)點(diǎn).//情況3[2]-1T是一棵改進(jìn)的中序線索二叉樹(shù)，如何找出

T中結(jié)點(diǎn)p的中序前驅(qū)結(jié)點(diǎn)？第105頁(yè)算法PIO(t,p.q)/*給定改進(jìn)的中序線索二叉樹(shù)（這里亦簡(jiǎn)稱(chēng)二叉樹(shù)）T*，t指向T*之根，算法PIO搜索T*中結(jié)點(diǎn)p的中序前驅(qū)結(jié)點(diǎn)，PIO運(yùn)行結(jié)束時(shí)q指向它*/PIO1.[求中序首結(jié)點(diǎn)]FIO(t.first).IFp

firstTHEN(q

.RETURNq.)//p無(wú)前驅(qū)PIO2.[取p之左指針]lp

Left(p).IFLThread(p)1THEN(qlp.RETURNq.)

//情況2，lp指向p的中序前驅(qū)結(jié)點(diǎn)PIO3.[求中序末結(jié)點(diǎn)]LIO(lp.q).//求以lp

為根之二叉樹(shù)的中序末結(jié)點(diǎn)RETURNq.?第106頁(yè)主要思想：若p是中序末結(jié)點(diǎn)，則其無(wú)后繼結(jié)點(diǎn)；

//情況1若p非中序末結(jié)點(diǎn)：

//由中序定義知：p之后繼在p

的右子樹(shù)中若RThread(p)1，則Right(p)指向p之中序后繼//情況2，Right(p)為右線索若RThread(p)0，則p的中序后繼為p之右子樹(shù)的中序首結(jié)點(diǎn)。//情況3[2]-2T是一棵改進(jìn)的中序線索二叉樹(shù)，如何找出T中

結(jié)點(diǎn)p之中序后繼結(jié)點(diǎn)？第107頁(yè)算法NIO*(t,p.q)/*給定改進(jìn)的中序線索二叉樹(shù)（這里亦簡(jiǎn)稱(chēng)二叉樹(shù)）T*，t指向T*之根，NIO*搜索T*中結(jié)點(diǎn)p的中序后繼，當(dāng)NIO*運(yùn)行結(jié)束q指向它*/NIO*1.[求中序末結(jié)點(diǎn)]

LIO(t.last).IFp

lastTHEN(q

.RETURNq.)//情況1NIO*2.[取p之右指針]rp

Right(p).IFRThread(p)1THEN(qrp.RETURNq.)

//情況2，Right(p)為指向p之中序后繼的右線索NIO*3.[RThread(p)0]

FIO(rp.q).RETURNq.?

/*情況3，

rp為p之右子樹(shù)的根，q指向以rp為根之

二叉樹(shù)的中序首結(jié)點(diǎn)*/第108頁(yè)主要思想：若結(jié)點(diǎn)p是改進(jìn)的后序線索二叉樹(shù)T*之后序首結(jié)點(diǎn)，則p無(wú)后序前驅(qū)；//情況1若結(jié)點(diǎn)p非T*之后序首結(jié)點(diǎn)：若LThread(p)1，則Left(p)指向p的后序前驅(qū)；

//情況2，Left(p)為左線索若LThread(p)0，則：

//情況3，此時(shí)p有左子樹(shù)若p無(wú)右子樹(shù)，則p之左孩子是其后序前驅(qū)；若p有右子樹(shù)，則p之右孩子是其后序前驅(qū).[3]-1改進(jìn)的后序線索二叉樹(shù)中結(jié)點(diǎn)p之后序前驅(qū)第109頁(yè)算法PPO(t,p.q)/*給定后序線索二叉樹(shù)T*，t指向T*之根，PPO搜索T*之結(jié)點(diǎn)p的后序前驅(qū)，并令q指向它*/PPO1.[求T*之后序首結(jié)點(diǎn)]FPO(t.first).//FPO求T*之后序首結(jié)點(diǎn)IFpfirst