數(shù)據(jù)結(jié)構(gòu)-第四章樹微軟2010版2013ldy_第1頁(yè)
數(shù)據(jù)結(jié)構(gòu)-第四章樹微軟2010版2013ldy_第2頁(yè)
數(shù)據(jù)結(jié)構(gòu)-第四章樹微軟2010版2013ldy_第3頁(yè)
數(shù)據(jù)結(jié)構(gòu)-第四章樹微軟2010版2013ldy_第4頁(yè)
數(shù)據(jù)結(jié)構(gòu)-第四章樹微軟2010版2013ldy_第5頁(yè)
已閱讀5頁(yè),還剩220頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

第1頁(yè)4.1樹的基本概念4.2二叉樹(BinaryTree)4.3線索二叉樹(ThreadedBinaryTree)4.4樹與森林(Tree&Forest)4.5壓縮與哈夫曼樹(HuffmanTree)4.6應(yīng)用第四章樹第2頁(yè)在現(xiàn)實(shí)世界中,樹(或曰樹結(jié)構(gòu))大量存在,例如用樹可形象地表示家譜、行政組織機(jī)構(gòu)、著作目錄等。樹在計(jì)算機(jī)領(lǐng)域中也有著廣泛的應(yīng)用,例如在編譯程序中,用樹來(lái)表示源程序的語(yǔ)法結(jié)構(gòu);在數(shù)據(jù)庫(kù)系統(tǒng)中,可用樹來(lái)組織信息;在分析算法的行為時(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è)總裁銷售副總裁市場(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)圖.頂層元素(亦稱機(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樹的基本概念4.2二叉樹4.3線索二叉樹4.4樹和森林4.5壓縮與哈夫曼樹4.6

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

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

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

v1

vk,其中vi是vi1(1

i

k)

的子結(jié)點(diǎn)。樹的非遞歸定義線性結(jié)構(gòu)樹結(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è)后繼)樹中其它結(jié)點(diǎn)(一個(gè)前驅(qū),多個(gè)后繼)樹與線性結(jié)構(gòu)的比較第12頁(yè)1、結(jié)點(diǎn)的度與樹的度一個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)的數(shù)目,被稱為該結(jié)點(diǎn)的度或曰次數(shù).一棵樹的度為maxi

1nD(i),其中n為樹中結(jié)點(diǎn)總數(shù),i指樹中的第i個(gè)結(jié)點(diǎn),D(i)表結(jié)點(diǎn)i的度.2、葉結(jié)點(diǎn)與分支結(jié)點(diǎn)度為零的結(jié)點(diǎn)被稱為葉結(jié)點(diǎn);度大于零的結(jié)點(diǎn)被稱為分支結(jié)點(diǎn).4.1.2樹的相關(guān)術(shù)語(yǔ)第13頁(yè)3.結(jié)點(diǎn)的層數(shù)樹形T中結(jié)點(diǎn)的層數(shù)遞歸定義如下:⑴root(T)層數(shù)為零;⑵其余結(jié)點(diǎn)的層數(shù)為其前驅(qū)結(jié)點(diǎn)的層數(shù)加1.第14頁(yè)在圖4.1所示的樹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ù)最多,故這棵樹的度為3.T

中F,G,H,I

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

為樹T

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

vm1…

vmk,1

k

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

i

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

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

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

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

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

高度為k0的二叉樹至多有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的二叉樹中至多有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)的二叉樹,其中葉結(jié)點(diǎn)數(shù)為n0,度為2的結(jié)點(diǎn)數(shù)為n2,則有n0n21第29頁(yè)滿二叉樹定義4.4一棵非空高為k(k

0),具有2k+11個(gè)結(jié)點(diǎn)的二叉樹,被稱為滿二叉樹。第30頁(yè)712345689101112131415非空高為k二叉樹至多有2k+11個(gè)結(jié)點(diǎn).滿二叉樹的特點(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ì)滿二叉樹而言,除葉結(jié)點(diǎn)外,其它結(jié)點(diǎn)的度均為2.見(jiàn)引理4.3).第31頁(yè)層次順序:按從上至下,即從第0至第k層,每層由左到右的次序.定義4.5

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

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

個(gè)結(jié)點(diǎn)的完全二叉樹,按層次順序用自然數(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)的完全二叉樹的高度是log2n.證明:設(shè)二叉樹高度為k

,

由定義4.5知,

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

的滿二叉樹的結(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è)二叉樹的存儲(chǔ)結(jié)構(gòu)要存儲(chǔ)一棵二叉樹,需存儲(chǔ)其所有結(jié)點(diǎn)的數(shù)據(jù)信息,以及其左、右孩子的地址。通常有兩種存儲(chǔ)方式:順序存儲(chǔ)鏈接存儲(chǔ)第38頁(yè)4.2.2二叉樹的順序存儲(chǔ)二叉樹的順序存儲(chǔ)(或曰順序存儲(chǔ)方式,順序存儲(chǔ)方法):

系指將二叉樹的所有結(jié)點(diǎn)按層次順序存放在一塊地址連續(xù)的存儲(chǔ)空間中,同時(shí)要反映出二叉樹中結(jié)點(diǎn)間的邏輯關(guān)系。第39頁(yè)對(duì)于任一完全二叉樹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ì)完全二叉樹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完全二叉樹的順序存儲(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)的完全二叉樹EBACD2345第41頁(yè)結(jié)點(diǎn)值3123126694175706249結(jié)點(diǎn)編號(hào)12345678910106649311294175706212345672389哪個(gè)是編號(hào)最大的非葉結(jié)點(diǎn)?第42頁(yè)若將上述方法用于非完全二叉樹,卻有很多缺點(diǎn).如果采用上述順序存儲(chǔ)方式,按層次順序,對(duì)非完全二叉樹之結(jié)點(diǎn)進(jìn)行編號(hào),則編號(hào)不能表達(dá)結(jié)點(diǎn)間的邏輯關(guān)系.為此先通過(guò)添加虛結(jié)點(diǎn)將其轉(zhuǎn)換成一棵“完全二叉樹”,然后再對(duì)原來(lái)的結(jié)點(diǎn)和虛結(jié)點(diǎn)統(tǒng)一編號(hào),最后完成順序存儲(chǔ)。但這無(wú)疑增加了用于存儲(chǔ)虛結(jié)點(diǎn)的空間。第43頁(yè)(a)

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

在二叉樹的鏈接存儲(chǔ)中,結(jié)點(diǎn)包含三個(gè)域,數(shù)據(jù)域data、左指針域left和右指針域right,其中左、右指針?lè)謩e指向該結(jié)點(diǎn)的左、右子樹的根結(jié)點(diǎn);結(jié)點(diǎn)結(jié)構(gòu)圖示如下:4.2.3二叉樹鏈接存儲(chǔ)第45頁(yè)leftdataright常用data字段值表示結(jié)點(diǎn)的名字.如在右圖第2層最左邊的結(jié)點(diǎn)C中,left域中的表示C的左子樹為空,right域的表示C的右子樹為空.ABCDEFG第46頁(yè)CABDEFG二叉樹鏈接存儲(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指向二叉樹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

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

.q

)/*指針t指向二叉樹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è)③從二叉樹中刪除給定結(jié)點(diǎn)及其左右子樹算法DST(t)/*root指向二叉樹T之根,DST從T中

刪除給定結(jié)點(diǎn)t及其左右子樹*/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及其子樹]Del(p).?第50頁(yè)算法Del(p)//刪除結(jié)點(diǎn)p及其左右子樹Del1.[p

?]IFp

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

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

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

DLR中根遍歷:

LDR后根遍歷:

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

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

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

AH

G

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

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

*/INO1.[遞歸出口]

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

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

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

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

第60頁(yè)算法NIO(t)/*設(shè)t是指向一棵鏈接表示的二叉樹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非遞歸中根遍歷二叉樹(b)中根遍歷(a)中二叉樹,堆棧內(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)二叉樹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)之二叉樹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è):讀書上之證明第63頁(yè)②非遞歸后根遍歷算法非遞歸后根遍歷算法需要一個(gè)輔助堆棧來(lái)記憶訪問(wèn)路徑,算法中棧元素結(jié)構(gòu)如下:樹中任一結(jié)點(diǎn)p都要進(jìn)棧三次,出棧三次.

第一次出棧是為遍歷p的左子樹;第二次出棧是為遍歷p的右子樹;第三次出棧是為訪問(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

的左子樹./*

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

*/

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

p

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

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

p

的右子樹./*

此時(shí)

p

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

若i

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

//此時(shí)p

的左、右子樹都已被遍歷,自然應(yīng)訪問(wèn)根結(jié)點(diǎn)第65頁(yè)算法NPO(t)/*設(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

的左子樹已被遍歷(

S

(

p

,

2).若

right(

p)

S

(

right(

p),

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

的右子樹已被遍歷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ì)左圖之二叉樹進(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è)先根序列和中根序列可唯一確定一棵二叉樹ABDCEFKH[例]上圖二叉樹T的先序、中序遍歷結(jié)果:①先根序列A00BALCBRKCLDAREDLHELFDR②中根序列BALKCLCBRA00HELEDLDARFDR由①、②兩個(gè)序列可確定二叉樹的結(jié)構(gòu)。

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

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

后根序列CEFDBHGA

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

中根序列CBLBALEDLDBRFDR

A00GARHGRAC

B

E

DFGHDEFABCGHABCGDEHF第70頁(yè)第71頁(yè)練習(xí):已知某二叉樹的先序遍歷序列是ABDGCEFH,中序遍歷序列是DGBAECHF,它的后序遍歷序列是什么?給定一棵二叉樹T的先根序列和后根序列,那么能否由此確定出T之結(jié)構(gòu)?第72頁(yè)層次遍歷:按層數(shù)由小到大,即從第0層開(kāi)始逐層向下,同層中由左到右的次序訪問(wèn)二叉樹的所有結(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);由②,除待遍歷二叉樹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.二叉樹層次遍歷算法的主要思想第75頁(yè)/*

算法LevelOrder按層次順序?qū)︽溄哟鎯?chǔ)的二叉樹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è)由二叉樹的遍歷算法,很容易想到用遍歷方法去創(chuàng)建二叉樹。如,從先根遍歷思想出發(fā)構(gòu)造二叉樹。但先根序列不能唯一確定二叉樹的結(jié)構(gòu),兩棵不同的二叉樹卻可能有相同的先根序列。

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

由此:需在先根序列中加入特殊符號(hào)以示空指針位置,這里不妨用“#”號(hào)表示空指針位置。4.2.5創(chuàng)建二叉樹第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è)所示的二叉樹.第78頁(yè)算法CBT(tostop.t)//構(gòu)造以結(jié)點(diǎn)t為根的二叉樹;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)造左子樹]CBT(tostop.Left(t)).CBT4.[構(gòu)造右子樹]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指向一棵鏈接表示的二叉樹T,欲得到T的一個(gè)“備份”,則容易想到用先根、中根或后根遍歷二叉樹的解決方案??紤]到在創(chuàng)建二叉樹的算法中使用了先根遍歷的思想,這里最好嘗試其它遍歷方式,譬如說(shuō)“后根遍歷”。若采用后根遍歷方式,則復(fù)制過(guò)程如下:

①?gòu)?fù)制左子樹;

②復(fù)制右子樹;

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

算法

CT(t.p)

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

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

CT1.[遞歸出口]IFt

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

THENCT(Left(t).lptr)ELSElptr

.CT3.[復(fù)制右子樹]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ì)算二叉樹結(jié)點(diǎn)個(gè)數(shù)算法Count(t.n)/**/IFtNULLTHEN(n0.RETURN.)Count(left(t).nl).Count(right(t).nr).n

nlnr1.▌編寫計(jì)算二叉樹高度的算法[解題思路]二叉樹之深度可由如下公式求得:由此可見(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鏈接表示的二叉樹結(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)的二叉樹,在其2i個(gè)指針字段中僅有i1個(gè)被使用.4.3線索二叉樹第88頁(yè)為使二叉樹之訪問(wèn)更方便,其空間利用率更高.1960年,珀利斯(A.J.Perlis)和桑頓(C.Thornton)提出了巧妙的線索二叉樹表示,并給出了以各種順序遍歷線索二叉樹的重要思想.但是珀利斯和桑頓提出的只是單向的線索二叉樹.1963年,霍特(A.W.Holt)又提出了雙向線索二叉樹。第89頁(yè)第90頁(yè)象雙向鏈表一樣,二叉樹也可采用雙向鏈接.如下圖所示,針對(duì)某種遍歷順序,可為二叉樹的每個(gè)結(jié)點(diǎn)增加兩個(gè)指針域,分別存放指向其前驅(qū)和后繼結(jié)點(diǎn)的指針Pred和Succ,并稱Pred和Succ為"線索".在這樣的二叉樹中,搜索一結(jié)點(diǎn)在某遍歷順序下的前驅(qū)或后繼將變得更加容易,但將增加一些存儲(chǔ)空間的開(kāi)銷.LeftRight

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

(Threaded

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

第92頁(yè)(a)

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

CBEDASuccPredSuccSuccPredSuccrootADBCEPredPred第94頁(yè)線索二叉樹的問(wèn)題與分析問(wèn)題:由圖4.21可見(jiàn),線索二叉樹的結(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日講到這里線索二叉樹的改進(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í)稱Left為線索.若結(jié)點(diǎn)t有右孩子,則Right指向t的右孩子,且RThread值為0;若t沒(méi)有右孩子,則Right指向t的后繼結(jié)點(diǎn),且RThread值為1,此時(shí)稱Right為線索.第96頁(yè)圖4.22改進(jìn)后的線索二叉樹(b)改進(jìn)的中序線索二叉樹A00B10C11D01E11ABDCE(a)

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

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

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

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

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

4.3.3線索二叉樹基本算法第100頁(yè)算法FIO(t.q)/*t指向改進(jìn)的中序線索二叉樹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搜索線索二叉樹T*之中根順序的最后一個(gè)結(jié)點(diǎn),設(shè)t

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

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

第103頁(yè)算法LIO(t.q)/*給定改進(jìn)的中序線索二叉樹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之左子樹的中根序末結(jié)點(diǎn).//情況3[2]-1T是一棵改進(jìn)的中序線索二叉樹,如何找出

T中結(jié)點(diǎn)p的中序前驅(qū)結(jié)點(diǎn)?第105頁(yè)算法PIO(t,p.q)/*給定改進(jìn)的中序線索二叉樹(這里亦簡(jiǎn)稱二叉樹)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

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

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

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

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

結(jié)點(diǎn)p之中序后繼結(jié)點(diǎn)?第107頁(yè)算法NIO*(t,p.q)/*給定改進(jìn)的中序線索二叉樹(這里亦簡(jiǎn)稱二叉樹)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之右子樹的根,q指向以rp為根之

二叉樹的中序首結(jié)點(diǎn)*/第108頁(yè)主要思想:若結(jié)點(diǎn)p是改進(jìn)的后序線索二叉樹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有左子樹若p無(wú)右子樹,則p之左孩子是其后序前驅(qū);若p有右子樹,則p之右孩子是其后序前驅(qū).[3]-1改進(jìn)的后序線索二叉樹中結(jié)點(diǎn)p之后序前驅(qū)第109頁(yè)算法PPO(t,p.q)/*給定后序線索二叉樹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

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論