《數(shù)據(jù)結(jié)構(gòu)、代碼》第4章 樹(shù)和二叉樹(shù)

第4章樹(shù)和二叉樹(shù)張成文北京郵電大學(xué)計(jì)算機(jī)學(xué)院編輯ppt樹(shù)的定義與基本術(shù)語(yǔ)1.定義:樹(shù)是n(n≥0)個(gè)結(jié)點(diǎn)的有限集合T。當(dāng)n=0時(shí),稱(chēng)為空樹(shù);當(dāng)n>0時(shí),該集合滿足如下條件:(1)其中必有一個(gè)稱(chēng)為根(root)的特定結(jié)點(diǎn),它沒(méi)有直接前驅(qū),但有零個(gè)或多個(gè)直接后繼。(2)其余n-1個(gè)結(jié)點(diǎn)可以劃分成m(m≥0)個(gè)互不相交的有限集T1,T2,T3,…,Tm,其中Ti又是一棵樹(shù),稱(chēng)為根root的子樹(shù)。每棵子樹(shù)的根結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū),但有零個(gè)或多個(gè)直接后繼。一、樹(shù)(tree)的基本概念:編輯pptABCDEFGHIJMKLA(B(E,F(K,L)),

C(G),

D(H,I,J(M))

)T1T3T2樹(shù)根例如:編輯ppt(1).樹(shù)型圖示(2).嵌套集合(3).凹入(書(shū)目)(4).廣義表(用根作為表的名字寫(xiě)在表的左邊)ABCDEFGHIJKLMA------------B----------E--------K------L------F--------C----------G--------D----------H--------M

------

I--------J--------2.樹(shù)的表示法:編輯ppt線性結(jié)構(gòu)樹(shù)型結(jié)構(gòu)第一個(gè)數(shù)據(jù)元素(無(wú)前驅(qū))

根結(jié)點(diǎn)(無(wú)前驅(qū))最后一個(gè)數(shù)據(jù)元素(無(wú)后繼)多個(gè)葉子結(jié)點(diǎn)(無(wú)后繼)其它數(shù)據(jù)元素(一個(gè)前驅(qū)、

一個(gè)后繼)其它數(shù)據(jù)元素(一個(gè)前驅(qū)、

多個(gè)后繼)對(duì)比樹(shù)型結(jié)構(gòu)和線性結(jié)構(gòu)的結(jié)構(gòu)特點(diǎn)編輯ppt結(jié)點(diǎn)(node):樹(shù)的度:葉子結(jié)點(diǎn)(leaf):分支結(jié)點(diǎn):數(shù)據(jù)元素+若干指向子樹(shù)的分支樹(shù)各結(jié)點(diǎn)的度的最大值度為零的結(jié)點(diǎn)度大于零的結(jié)點(diǎn)DHIJM3.樹(shù)的相關(guān)術(shù)語(yǔ)結(jié)點(diǎn)的度(degree):結(jié)點(diǎn)擁有的子樹(shù)數(shù)結(jié)點(diǎn)的層次:(level)假設(shè)根結(jié)點(diǎn)的層次為1,第l層的結(jié)點(diǎn)的子樹(shù)根結(jié)點(diǎn)的層次為l+1樹(shù)的深度(depth):葉子結(jié)點(diǎn)所在的最大層次分支(branch):表示數(shù)據(jù)元素與它的子樹(shù)的關(guān)系編輯ppt路徑(path):常用家族樹(shù)的術(shù)語(yǔ)表示結(jié)點(diǎn)關(guān)系孩子(child)結(jié)點(diǎn)雙親(parent)結(jié)點(diǎn)

兄弟結(jié)點(diǎn)由根到該結(jié)點(diǎn)所經(jīng)的分支和結(jié)點(diǎn)構(gòu)成ABCDEFGHIJMKL樹(shù)的結(jié)點(diǎn)數(shù)n和分支數(shù)b的關(guān)系是:

b=n-1編輯ppt任何一棵非空樹(shù)是一個(gè)二元組Tree=(root,F)其中:root被稱(chēng)為根結(jié)點(diǎn)F被稱(chēng)為子樹(shù)森林森林(forest):是m(m≥0)棵互不相交的樹(shù)的集合ArootBCDEFGHIJMKLF編輯ppt二叉樹(shù)1二叉樹(shù)的定義與基本操作定義：滿足以下兩個(gè)條件的樹(shù)稱(chēng)做二叉樹(shù)(BinaryTree):（1）每個(gè)結(jié)點(diǎn)的度都不大于2；（2）每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)次序不能任意顛倒。編輯ppt

二叉樹(shù)或?yàn)榭諛?shù),或是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱(chēng)為左子樹(shù)和右子樹(shù)的、互不交的二叉樹(shù)組成。注意:二叉樹(shù)是有序樹(shù),它的子樹(shù)有左右之分。二叉樹(shù)的度數(shù)不超過(guò)二,但度數(shù)不超過(guò)二的樹(shù)未必是二叉樹(shù)。ABCDEFGHK根結(jié)點(diǎn)左子樹(shù)右子樹(shù)編輯ppt二叉樹(shù)的五種基本形態(tài):N空樹(shù)只含根結(jié)點(diǎn)NNNLRR右子樹(shù)為空樹(shù)L左子樹(shù)為空樹(shù)左右子樹(shù)均非空樹(shù)編輯ppt用歸納法證明:

歸納基:

歸納假設(shè):

歸納證明:i=1層時(shí),只有一個(gè)根結(jié)點(diǎn):

2i-1=20=1命題成立;假設(shè)

i-1命題成立,即:第i-1層至多有結(jié)點(diǎn)=2i-1-1=2i-2個(gè);二叉樹(shù)每個(gè)結(jié)點(diǎn)至多有兩棵子樹(shù),則第i層至多有結(jié)點(diǎn)=2i-22=2i-1個(gè)。2二叉樹(shù)的重要特性性質(zhì)1:二叉樹(shù)第i層上至多有2i-1個(gè)結(jié)點(diǎn)。編輯ppt證明:

基于性質(zhì)1,深度為k的二叉樹(shù)上的結(jié)點(diǎn)總數(shù)的最大值是將二叉樹(shù)每層上結(jié)點(diǎn)的最大值相加，所以深度為k的二叉樹(shù)上含結(jié)點(diǎn)數(shù)至多為：

20+21++2k-1=2k-1

性質(zhì)2:

深度為k的二叉樹(shù)上至多含2k-1個(gè)結(jié)點(diǎn)(k≥1)。編輯ppt證明:設(shè)二叉樹(shù)上結(jié)點(diǎn)總數(shù)：n=n0+n1+n2再根據(jù)樹(shù)的性質(zhì)：b=n-1

=n0+n1+n2-1由有二叉樹(shù)分支總數(shù)：b=n1+2n2兩式右邊相等得:n0=n2+1。性質(zhì)3:

對(duì)任何一棵二叉樹(shù),若它含有n0個(gè)葉子結(jié)點(diǎn)、n2個(gè)度為2的結(jié)點(diǎn),則必存在關(guān)系式:n0=n2+1。也可以用歸納法證明編輯ppt滿二叉樹(shù)在一個(gè)二叉樹(shù)中，若第i層的結(jié)點(diǎn)數(shù)為2i-1，則稱(chēng)此層的結(jié)點(diǎn)數(shù)是滿的，當(dāng)樹(shù)中的每一層都是滿的，則稱(chēng)此二叉樹(shù)為滿二叉樹(shù)。即如果一個(gè)二叉樹(shù)中，除最下一層的各結(jié)點(diǎn)度數(shù)為0以外，其它各層結(jié)點(diǎn)的度數(shù)均等于2，則此二叉樹(shù)為滿二叉樹(shù)。編輯ppt完全二叉樹(shù) 如果一個(gè)二叉樹(shù)各層都是“滿”的，只是最下面一層從右邊起連續(xù)缺n個(gè)結(jié)點(diǎn)，這種二叉樹(shù)叫做完全二叉樹(shù)。編輯ppt完全二叉樹(shù):樹(shù)中所含的n個(gè)結(jié)點(diǎn)和滿二叉樹(shù)中編號(hào)為1至n的結(jié)點(diǎn)一一對(duì)應(yīng)。abcdefghij編輯ppt可用一維數(shù)組存儲(chǔ):bt[n]順序:完全二叉樹(shù)中將編號(hào)i的結(jié)點(diǎn)存在bt[i]中。一、二叉樹(shù)的順序存儲(chǔ)3二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)是非線性結(jié)構(gòu)，結(jié)點(diǎn)最多有兩個(gè)后繼。存儲(chǔ)結(jié)構(gòu)有兩種：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。ABCDEFGHIJKLABCDEFGHIJKL編輯ppt例如:

ABDCEF1

23

456

789

1011

121314ABCDEF2511437一般二叉樹(shù)，按完全二叉樹(shù)結(jié)點(diǎn)的編號(hào)存放,無(wú)結(jié)點(diǎn)的單元存放空元素。會(huì)造成空間浪費(fèi)編輯ppt二、二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)表示二叉鏈表每個(gè)結(jié)點(diǎn)包括兩個(gè)指針域：指向左孩子和右孩子LChildDataRChildDABCEFGABCDEFG二叉樹(shù)T二叉鏈表結(jié)點(diǎn)結(jié)構(gòu):編輯pptlchilddatarchild結(jié)點(diǎn)結(jié)構(gòu):二叉鏈表結(jié)點(diǎn)的結(jié)構(gòu)用C語(yǔ)言描述為：typedefstructNode{DataTypedata;strctNode*LChild;structNode*RChild;}BiTNode,*BiTree;

編輯ppt一、問(wèn)題的提出二、先左后右的遍歷算法三、算法描述二叉樹(shù)的遍歷編輯ppt

“遍歷”:

沿某條搜索路徑巡訪二叉樹(shù)的結(jié)點(diǎn),

使每個(gè)結(jié)點(diǎn)均被訪問(wèn)一次,且僅被訪問(wèn)一次。一、問(wèn)題的提出“訪問(wèn)”:

的含義很廣,如:輸出結(jié)點(diǎn)信息等。

“遍歷”是任何類(lèi)型均有的操作,對(duì)線性結(jié)構(gòu)而言,只有一條搜索路徑(因?yàn)槊總€(gè)結(jié)點(diǎn)只有一個(gè)后繼),故不需要另加討論.編輯ppt二叉樹(shù)是非線性結(jié)構(gòu),每個(gè)結(jié)點(diǎn)有兩個(gè)后繼,

則存在按什么樣的搜索路徑遍歷的問(wèn)題。 “二叉樹(shù)”由三部分組成：根結(jié)點(diǎn)、左子樹(shù)和右子樹(shù)。若能依次遍歷這三部分，就遍歷了整個(gè)二叉樹(shù)。

用L、D、R表示遍歷左子樹(shù)、訪問(wèn)根結(jié)點(diǎn)、遍歷右子樹(shù)，則有8種遍歷二叉樹(shù)方案：先左后右：DLR、LDR、LRD、按層次先右后左：DRL、RDL、RLD、按層次編輯ppt二、先左后右的遍歷算法先序的遍歷算法DLR中序的遍歷算法LDR后序的遍歷算法LRDDLR編輯ppt

若二叉樹(shù)為空樹(shù),則空操作;否則,(1)訪問(wèn)根結(jié)點(diǎn);(2)先序遍歷左子樹(shù);(3)先序遍歷右子樹(shù)。先序的遍歷算法:DLR編輯ppt

若二叉樹(shù)為空樹(shù),則空操作;否則,(1)中序遍歷左子樹(shù);(2)訪問(wèn)根結(jié)點(diǎn);(3)中序遍歷右子樹(shù)。中序的遍歷算法:DLR編輯ppt

若二叉樹(shù)為空樹(shù),則空操作;否則,(1)后序遍歷左子樹(shù);(2)后序遍歷右子樹(shù);(3)訪問(wèn)根結(jié)點(diǎn)。后序的遍歷算法:DLR編輯pptabcdefghij例如:先序序列:

abdhiejcfg中序序列:

hdibjeafcg后序序列:

hidjebfgca編輯ppt三、算法描述1)先序遍歷voidPreOrder(BiTreebt)/*先序遍歷,根指針為bt的二叉樹(shù)*/{if(bt!=NULL){Visit(bt->data);//訪問(wèn)根結(jié)點(diǎn)

PreOrder(bt->LChild);//遍歷左子樹(shù)

PreOrder(bt->RChild);//遍歷右子樹(shù)}}編輯ppt2)中序遍歷voidInOrder(BiTreebt)/*中序遍歷根指針為bt的二叉樹(shù)*/{if(bt!=NULL){

InOrder(bt->LChild);//遍歷左子樹(shù) Visit(bt->data);//訪問(wèn)根結(jié)點(diǎn)

InOrder(bt->RChild);//遍歷右子樹(shù)}}

編輯ppt3)后序遍歷voidPostOrder(BiTreebt)/*后序遍歷根指針為bt的二叉樹(shù)*/{if(bt!=NULL){

PostOrder(bt->LChild);//遍歷左子樹(shù)

PostOrder(bt->RChild);//遍歷右子樹(shù) Visit(bt->data);//訪問(wèn)根結(jié)點(diǎn)}}

編輯ppt利用遍歷結(jié)果確定二叉樹(shù)問(wèn)題先序序列+中序序列中序序列+后序序列先序序列+后序序列(x)

先序序列:ABCDEFGH中序序列:BDCEAFHGABFCGDEH利用遍歷結(jié)果確定二叉