版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
1、1第五章 樹和二叉樹5.1 5.1 樹的有關(guān)概念樹的有關(guān)概念5.2 5.2 二叉樹二叉樹5.35.3 二叉樹的遍歷二叉樹的遍歷5.4 5.4 遍歷的應(yīng)用遍歷的應(yīng)用5.5 5.5 線索二叉樹線索二叉樹5.6 5.6 樹和森林樹和森林5.7 5.7 哈夫曼樹及應(yīng)用哈夫曼樹及應(yīng)用2第六章第六章 樹和二叉樹樹和二叉樹本章學(xué)習(xí)要點(diǎn):本章學(xué)習(xí)要點(diǎn): 熟練掌握熟練掌握二叉樹的結(jié)構(gòu)特點(diǎn),二叉樹的結(jié)構(gòu)特點(diǎn),了解了解相應(yīng)的證明方法;相應(yīng)的證明方法; 熟悉熟悉二叉樹的各種存儲結(jié)構(gòu)的特點(diǎn)及使用范圍;二叉樹的各種存儲結(jié)構(gòu)的特點(diǎn)及使用范圍; 熟練掌握熟練掌握各種序遍歷的遞歸和非遞歸算法,各種序遍歷的遞歸和非遞歸算法,了解
2、了解遍歷過程中遍歷過程中“棧?!?的狀態(tài),并能的狀態(tài),并能靈活運(yùn)用靈活運(yùn)用遍歷算法實(shí)現(xiàn)二叉樹的其它各種運(yùn)算;遍歷算法實(shí)現(xiàn)二叉樹的其它各種運(yùn)算; 了解了解線索化的實(shí)質(zhì)是建立結(jié)點(diǎn)與其在相應(yīng)序列中的前驅(qū)或后繼線索化的實(shí)質(zhì)是建立結(jié)點(diǎn)與其在相應(yīng)序列中的前驅(qū)或后繼之之 間的直接聯(lián)系,間的直接聯(lián)系,熟練掌握熟練掌握在中序線索化樹上找給定結(jié)點(diǎn)的前驅(qū)和在中序線索化樹上找給定結(jié)點(diǎn)的前驅(qū)和 后繼的方法;后繼的方法; 熟悉熟悉樹的各種存儲結(jié)構(gòu)及其特點(diǎn);樹的各種存儲結(jié)構(gòu)及其特點(diǎn); 學(xué)會編寫學(xué)會編寫實(shí)現(xiàn)樹的各種運(yùn)算的算法;實(shí)現(xiàn)樹的各種運(yùn)算的算法; 了解了解最優(yōu)樹的特性,最優(yōu)樹的特性,掌握掌握建立最優(yōu)樹和哈夫曼編碼的方法建
3、立最優(yōu)樹和哈夫曼編碼的方法36.1 樹的有關(guān)概念 5.15.1 樹的有關(guān)概念樹的有關(guān)概念1.1. 樹的概念樹的概念2. 2. 樹的應(yīng)用樹的應(yīng)用3.3. 樹的表示樹的表示樹的有關(guān)術(shù)語樹的有關(guān)術(shù)語5 樹的基本操作樹的基本操作45.1 樹的有關(guān)概念1樹的概念樹的概念 樹(樹(Tree)是)是n(n 0)個結(jié)點(diǎn)的有限集合,在任一棵非空樹)個結(jié)點(diǎn)的有限集合,在任一棵非空樹(n0)中:中:(1)有且僅有一個稱為根的結(jié)點(diǎn)。)有且僅有一個稱為根的結(jié)點(diǎn)。(2)其余結(jié)點(diǎn)可分為)其余結(jié)點(diǎn)可分為m(m 0)個互不相交的集合,而且這些集合)個互不相交的集合,而且這些集合中的每一集合都本身又是一棵樹,稱為根的子樹。中的每
4、一集合都本身又是一棵樹,稱為根的子樹。樹是遞歸結(jié)構(gòu),在樹的定義樹是遞歸結(jié)構(gòu),在樹的定義中又用到了樹的概念中又用到了樹的概念J JI IA AC CB BD DH HG GF FE EK KL LM M從邏輯結(jié)構(gòu)看:從邏輯結(jié)構(gòu)看:1)樹中只有根結(jié)點(diǎn)沒有前趨;)樹中只有根結(jié)點(diǎn)沒有前趨;2)除根外,其余結(jié)點(diǎn)都有且僅一個前趨;)除根外,其余結(jié)點(diǎn)都有且僅一個前趨;3)樹的結(jié)點(diǎn),可以有零個或多個后繼;)樹的結(jié)點(diǎn),可以有零個或多個后繼;4)除根外的其他結(jié)點(diǎn),都存在唯一條從根到該結(jié)點(diǎn))除根外的其他結(jié)點(diǎn),都存在唯一條從根到該結(jié)點(diǎn)的路徑;的路徑;5)樹是一種分枝結(jié)構(gòu))樹是一種分枝結(jié)構(gòu) (除了一個稱為根的結(jié)點(diǎn)外(除
5、了一個稱為根的結(jié)點(diǎn)外)每個元素都有且僅有一個直接前趨,有且僅有零)每個元素都有且僅有一個直接前趨,有且僅有零個或多個直接后繼。個或多個直接后繼。55.1 樹的有關(guān)概念例:下面的圖是一棵樹例:下面的圖是一棵樹T=A, B, C, D, E, F, G, H, I, JT=A, B, C, D, E, F, G, H, I, J,K K,L L,MMA A是根,其余結(jié)點(diǎn)可以劃分為是根,其余結(jié)點(diǎn)可以劃分為3 3個個互不相交的集合:互不相交的集合: T T1 1=B, E, F=B, E, F,K K,L , TL , T2 2=C, G , T=C, G , T3 3=D, H, I, J=D, H
6、, I, J,MM這些集合中的每一集合都本身又是一棵樹,它們是這些集合中的每一集合都本身又是一棵樹,它們是A的子樹。的子樹。 例如例如 對于對于T T1 1,B B是根,其余結(jié)點(diǎn)可以劃分為是根,其余結(jié)點(diǎn)可以劃分為2 2個個互不相交的集合:互不相交的集合: T1111=E,K,L,T1212=F,T1111,T1212 是是B 的子樹。的子樹。J JI IA AC CB BD DH HG GF FE EK KL LM M65.1 5.1 樹的有關(guān)概念樹的有關(guān)概念2樹的應(yīng)用樹的應(yīng)用 1)樹可表示具有分枝結(jié)構(gòu)關(guān)系的對象)樹可表示具有分枝結(jié)構(gòu)關(guān)系的對象例例1家族族譜家族族譜 設(shè)某家庭有設(shè)某家庭有13個
7、成員個成員A、B、C、D、E、F、G、H、I、J,K,L,M他們之間的關(guān)系可下圖所示的樹表示:他們之間的關(guān)系可下圖所示的樹表示:例例2單位行政機(jī)構(gòu)的組織關(guān)系:單位行政機(jī)構(gòu)的組織關(guān)系:J JI IA AC CB BD DH HG GF FE EK KL LM M75.1 樹的有關(guān)概念 2)樹是常用的數(shù)據(jù)組織形式)樹是常用的數(shù)據(jù)組織形式 有些應(yīng)用中數(shù)據(jù)元素之間并不存在分支結(jié)構(gòu)關(guān)系,但是為了便于管理和使用數(shù)有些應(yīng)用中數(shù)據(jù)元素之間并不存在分支結(jié)構(gòu)關(guān)系,但是為了便于管理和使用數(shù)據(jù),將它們用樹的形式來組織。據(jù),將它們用樹的形式來組織。例例3 計(jì)算機(jī)的文件系統(tǒng)計(jì)算機(jī)的文件系統(tǒng) 不論是不論是DOS文件系統(tǒng)還是
8、文件系統(tǒng)還是window文件系統(tǒng),所有的文件是用樹的形式來組織文件系統(tǒng),所有的文件是用樹的形式來組織的。的。文件夾文件夾1 1 文件夾文件夾n n 文件文件1 1 文件文件2 2文件夾文件夾11 11 文件夾文件夾12 12 文件文件11 11 文件文件1212C C85.1 樹的有關(guān)概念3 樹的表示樹的表示 1)圖示表示)圖示表示 2)二元組表示)二元組表示 3)嵌套集合表示)嵌套集合表示 4)凹入表示法(類似書的目錄)凹入表示法(類似書的目錄) 5)廣義表表示)廣義表表示(A A(B B(E E(K,LK,L),F,F),C,C(G G),D,D(H H(M M),I,J,I,J)) ))
9、廣義表表示廣義表表示ABEKLFCGDHMJI凹凹入入表表示示法法AEDHJIKLMFGC嵌套集合表示嵌套集合表示B9 5.1 樹的有關(guān)概念樹的樹的 基本術(shù)語基本術(shù)語 樹的結(jié)點(diǎn):包含一個數(shù)據(jù)元素及若干指樹的結(jié)點(diǎn):包含一個數(shù)據(jù)元素及若干指向子樹的分支;向子樹的分支;孩子結(jié)點(diǎn)孩子結(jié)點(diǎn)(child):結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn):結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn)的孩子;的孩子;雙親結(jié)點(diǎn)雙親結(jié)點(diǎn)(parent):B 結(jié)點(diǎn)是結(jié)點(diǎn)是A 結(jié)點(diǎn)的孩子,結(jié)點(diǎn)的孩子, 則則A結(jié)點(diǎn)是結(jié)點(diǎn)是B 結(jié)點(diǎn)的雙親;結(jié)點(diǎn)的雙親;兄弟結(jié)點(diǎn)兄弟結(jié)點(diǎn)(sibling):同一雙親的孩子結(jié)點(diǎn);:同一雙親的孩子結(jié)點(diǎn);堂兄結(jié)點(diǎn)堂兄結(jié)點(diǎn)(cousin):
10、其雙親在同一層上的結(jié)點(diǎn);:其雙親在同一層上的結(jié)點(diǎn);祖先結(jié)點(diǎn)祖先結(jié)點(diǎn): 從根到該結(jié)點(diǎn)的所經(jīng)分支上的所有結(jié)點(diǎn)從根到該結(jié)點(diǎn)的所經(jīng)分支上的所有結(jié)點(diǎn) 子孫結(jié)點(diǎn):以某結(jié)點(diǎn)為根的子樹中任一結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫子孫結(jié)點(diǎn):以某結(jié)點(diǎn)為根的子樹中任一結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫J JI IA AC CB BD DH HG GF FE EK KL LM M10 5.1 樹的有關(guān)概念樹的樹的 基本術(shù)語基本術(shù)語結(jié)點(diǎn)層結(jié)點(diǎn)層:根結(jié)點(diǎn)的層定義為:根結(jié)點(diǎn)的層定義為1;根的孩子為第二層結(jié)點(diǎn),依此類推;根的孩子為第二層結(jié)點(diǎn),依此類推樹的深度樹的深度:樹中結(jié)點(diǎn)的最大層數(shù),也稱為樹的高度:樹中結(jié)點(diǎn)的最大層數(shù),也稱為樹的高度結(jié)點(diǎn)的度結(jié)點(diǎn)的度
11、:結(jié)點(diǎn)具有的子樹個數(shù):結(jié)點(diǎn)具有的子樹個數(shù)樹的度樹的度: 樹中最大的結(jié)點(diǎn)度樹中最大的結(jié)點(diǎn)度葉子結(jié)點(diǎn)葉子結(jié)點(diǎn):也叫終端結(jié)點(diǎn),是度為:也叫終端結(jié)點(diǎn),是度為 0 的結(jié)點(diǎn)的結(jié)點(diǎn)分枝結(jié)點(diǎn)分枝結(jié)點(diǎn):也叫非終端結(jié)點(diǎn),是度不為:也叫非終端結(jié)點(diǎn),是度不為0的結(jié)點(diǎn)的結(jié)點(diǎn)有序樹有序樹:子樹有序的樹,如:家族樹;:子樹有序的樹,如:家族樹; 最左邊的子樹的根成為第一個孩子最左邊的子樹的根成為第一個孩子,最右邊的稱為最后一個孩子最右邊的稱為最后一個孩子無序樹無序樹:不考慮子樹的順序;:不考慮子樹的順序;森林森林;互不相交的樹的集合;森林和樹之間的聯(lián)系是:一棵樹去;互不相交的樹的集合;森林和樹之間的聯(lián)系是:一棵樹去 掉根,
12、其子樹構(gòu)成一個森林;一個森林增加一個根結(jié)點(diǎn)成為樹。掉根,其子樹構(gòu)成一個森林;一個森林增加一個根結(jié)點(diǎn)成為樹。J JI IA AC CB BD DH HG GF FE EK KL LM M115.1 樹的有關(guān)概念5 樹的基本操作樹的基本操作 樹的應(yīng)用很廣,應(yīng)用不同基本操作也不同。下面列舉了樹的一些基本操作:樹的應(yīng)用很廣,應(yīng)用不同基本操作也不同。下面列舉了樹的一些基本操作:1 1)initate (T): T 樹的初始化,置樹的初始化,置T為空樹為空樹。包括建樹。包括建樹。2) root (T): 求求T 樹的根。樹的根。3)parent (T , x ): 求求T 樹中樹中 x 結(jié)點(diǎn)的雙親結(jié)點(diǎn)。結(jié)
13、點(diǎn)的雙親結(jié)點(diǎn)。4)Child (T, x, i ): 求求 T 樹中樹中 x 結(jié)點(diǎn)的第結(jié)點(diǎn)的第 i 個孩子結(jié)點(diǎn)。個孩子結(jié)點(diǎn)。5)right_Sibling (T, x ): 求求T 樹中樹中 x 結(jié)點(diǎn)的右兄弟結(jié)點(diǎn)的右兄弟6)insert_Child (y, i, x ): 將根為將根為 x 的子樹置為的子樹置為 y 結(jié)點(diǎn)的第結(jié)點(diǎn)的第 i 個孩子個孩子7)del_child (x, i): 刪除刪除 x 結(jié)點(diǎn)的第結(jié)點(diǎn)的第i 個孩子個孩子8)traverse (T): 遍歷遍歷T樹。按某個次序依次訪問樹中每一個結(jié)點(diǎn),并使每個結(jié)樹。按某個次序依次訪問樹中每一個結(jié)點(diǎn),并使每個結(jié) 點(diǎn)都被訪問且只被訪問一
14、次。點(diǎn)都被訪問且只被訪問一次。9)clear (T): 置置T為空樹為空樹 125. 2 二二 叉叉 樹樹 樹是一種分枝結(jié)構(gòu)的對象,在樹的概念中,樹是一種分枝結(jié)構(gòu)的對象,在樹的概念中,對每一個結(jié)點(diǎn)孩子的個數(shù)沒有限制,因此樹的對每一個結(jié)點(diǎn)孩子的個數(shù)沒有限制,因此樹的形態(tài)多種多樣,本章我們主要討論一種最簡單形態(tài)多種多樣,本章我們主要討論一種最簡單的樹的樹二叉樹。二叉樹。135.2 二 叉 樹 5.2 5.2 二叉樹二叉樹一一 二叉樹的概念二叉樹的概念二二 二叉樹的性質(zhì)二叉樹的性質(zhì)三三 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)145.2 二 叉 樹一一 二叉樹的概念二叉樹的概念1 1 二叉樹的定義二叉樹的定
15、義二叉樹:二叉樹: 或?yàn)榭諛?,或由根及兩顆不相交的左子樹、右子樹構(gòu)成,并且或?yàn)榭諛洌蛴筛皟深w不相交的左子樹、右子樹構(gòu)成,并且左、右子樹本身也是二叉樹。左、右子樹本身也是二叉樹。說明說明1 1)二叉樹中每個結(jié)點(diǎn)最多有兩顆子樹;二叉樹每個結(jié)點(diǎn)度小于等于)二叉樹中每個結(jié)點(diǎn)最多有兩顆子樹;二叉樹每個結(jié)點(diǎn)度小于等于2;2;2 2)左、右子樹不能顛倒)左、右子樹不能顛倒有序樹有序樹; ;3 3)二叉樹是遞歸結(jié)構(gòu),在二叉樹的定義中又用到了二叉樹的概念)二叉樹是遞歸結(jié)構(gòu),在二叉樹的定義中又用到了二叉樹的概念; ; A A F F G G E E D D C C B B155.2 二 叉 樹 (a)(a)、
16、(b)(b)是不同的二叉樹,是不同的二叉樹, (a)(a)的左子樹有四個結(jié)點(diǎn)的左子樹有四個結(jié)點(diǎn),(b)(b)的左子樹有兩個結(jié)點(diǎn),的左子樹有兩個結(jié)點(diǎn), A A F F G G E E D D C C B B(a)(a) A A G G E E D D B B C C F F(b)(b)165.2 二 叉 樹 2 二叉樹的基本形態(tài)二叉樹的基本形態(tài)(a)(a)空樹空樹 (b)(b)僅有根僅有根(c) (c) 右子樹空右子樹空(e) (e) 左子樹空左子樹空(d) (d) 左、右子樹均在左、右子樹均在3個結(jié)點(diǎn)的樹具有個結(jié)點(diǎn)的樹具有2種基本形態(tài)種基本形態(tài)3個結(jié)點(diǎn)的二叉樹具有個結(jié)點(diǎn)的二叉樹具有5中基本形態(tài)
17、中基本形態(tài)175.2 二 叉 樹3應(yīng)用舉例 可以用二叉樹表示表達(dá)式 a+b*(c-d)-e/f e e d d c c b b f f a a + + * * / / - - - -185.2 二 叉 樹二二 二叉樹性質(zhì)二叉樹性質(zhì)n性質(zhì)性質(zhì)1 1 二叉樹第二叉樹第i i層上至多層上至多2 2i-1i-1個結(jié)點(diǎn)(個結(jié)點(diǎn)(i=1)i=1) 證明:證明:( (采用數(shù)學(xué)歸納法采用數(shù)學(xué)歸納法) ) 當(dāng)當(dāng)i=1i=1時,只有時,只有1 1個根結(jié)點(diǎn)。顯然個根結(jié)點(diǎn)。顯然 2 21-11-1 =1 =1,命題成立。,命題成立。 假設(shè)對所有的假設(shè)對所有的j(1jj(1ji)i)命題成立,即第命題成立,即第j j層
18、上至多層上至多2 2j-1j-1個結(jié)點(diǎn)個結(jié)點(diǎn); ; 現(xiàn)證明現(xiàn)證明j=ij=i時命題仍然成立。時命題仍然成立。 由歸納假設(shè)知,二叉樹的由歸納假設(shè)知,二叉樹的i-1i-1層至多有層至多有2 2i-2i-2個結(jié)點(diǎn)個結(jié)點(diǎn)又由二叉樹的定義知,二叉樹每個結(jié)點(diǎn)的度至多為又由二叉樹的定義知,二叉樹每個結(jié)點(diǎn)的度至多為2 2 第第i i層上的最大結(jié)點(diǎn)數(shù)目層上的最大結(jié)點(diǎn)數(shù)目=2=2* *第第i-1i-1層上的最大結(jié)點(diǎn)數(shù)目層上的最大結(jié)點(diǎn)數(shù)目=2=2* *2 2i-2i-2 = 2 = 2i-1i-1 故故j=ij=i時命題成立時命題成立 從而該命題成立。從而該命題成立。195.2 二 叉 樹n 性質(zhì)性質(zhì)2 2 深度為
19、深度為k k的二叉樹至多的二叉樹至多2 2k k-1-1個結(jié)點(diǎn)(個結(jié)點(diǎn)(k=1)k=1)證明:深度為證明:深度為k k的二叉樹的結(jié)點(diǎn)的最大數(shù)目的二叉樹的結(jié)點(diǎn)的最大數(shù)目 每層結(jié)點(diǎn)的最大數(shù)目之和每層結(jié)點(diǎn)的最大數(shù)目之和2 20 0+2+21 1+2 2k-1k-12 2k k-1-1206.2 二叉樹n 性質(zhì)性質(zhì)3 對任何一棵二叉樹對任何一棵二叉樹T,若其終端結(jié)點(diǎn)數(shù)目為,若其終端結(jié)點(diǎn)數(shù)目為n0,度為度為2的結(jié)點(diǎn)數(shù)目為的結(jié)點(diǎn)數(shù)目為n2,則,則n0=n2+1。證明:證明:設(shè)二叉樹設(shè)二叉樹T的總結(jié)點(diǎn)數(shù)目為的總結(jié)點(diǎn)數(shù)目為n,度為度為1的結(jié)點(diǎn)數(shù)目為的結(jié)點(diǎn)數(shù)目為n1, 則則 n=n0+ n1+ n2 (1) 又
20、由于二叉樹又由于二叉樹T中,除根結(jié)點(diǎn)以外,每個結(jié)點(diǎn)剛好有一個分支指向,中,除根結(jié)點(diǎn)以外,每個結(jié)點(diǎn)剛好有一個分支指向, 設(shè)設(shè)B為分支總數(shù),則為分支總數(shù),則 n=B+1 (2) 而二叉樹的這些分支是由度為而二叉樹的這些分支是由度為1和度為和度為2的結(jié)點(diǎn)產(chǎn)生,的結(jié)點(diǎn)產(chǎn)生, 則則 B=n1+ 2 n2 (3) 綜上三式,可知綜上三式,可知n0=n2+1成立。成立。思考思考 如果一棵樹有如果一棵樹有n1個度數(shù)為個度數(shù)為1的結(jié)點(diǎn),的結(jié)點(diǎn),n2個度數(shù)為個度數(shù)為2的結(jié)點(diǎn),的結(jié)點(diǎn), ,nm個度數(shù)為個度數(shù)為m的結(jié)點(diǎn),則終端結(jié)點(diǎn)數(shù)的結(jié)點(diǎn),則終端結(jié)點(diǎn)數(shù)n0= ?215.2 二 叉 樹兩種特殊的二叉樹兩種特殊的二叉樹滿
21、二叉樹滿二叉樹:如果深度為:如果深度為k k的二叉樹,有的二叉樹,有2 2k k-1-1個結(jié)點(diǎn)則稱為滿二叉樹;個結(jié)點(diǎn)則稱為滿二叉樹; A A G G F F E E D D C C B B A A C C B BK=3K=3的滿二叉樹的滿二叉樹K=2K=2的滿二叉樹的滿二叉樹225.2 二 叉 樹完全二叉樹完全二叉樹:如果一顆二叉樹只有最下一層結(jié)點(diǎn)數(shù)可能未達(dá)到最大,并如果一顆二叉樹只有最下一層結(jié)點(diǎn)數(shù)可能未達(dá)到最大,并且最下層結(jié)點(diǎn)都集中在該層的最左端,則稱為完全二叉樹;且最下層結(jié)點(diǎn)都集中在該層的最左端,則稱為完全二叉樹; G G A A E E D D C C B B(c)(c) A A E E
22、 D D C C B B(b)(b)、(b)(b)完全二叉樹(c) (c) 不是完全二叉樹 A A(a)(a) G G F F E E D D C C B B235.2 二 叉 樹下面是兩個關(guān)于完全二叉樹的性質(zhì)下面是兩個關(guān)于完全二叉樹的性質(zhì) 性質(zhì)性質(zhì)4 4 具有具有n n個結(jié)點(diǎn)的完全二叉樹的深度為:個結(jié)點(diǎn)的完全二叉樹的深度為:trunc(logtrunc(log2 2 n)+1n)+1, trunc(x)trunc(x)為取整函數(shù)。為取整函數(shù)。證明:假設(shè)完全二叉樹的深度為證明:假設(shè)完全二叉樹的深度為k,k,則由性質(zhì)則由性質(zhì)2 2和完和完全二叉樹的定義知:全二叉樹的定義知:2 2k-1 k-1
23、-1-1 n 2n 2k k -1-1 ,即,即2 2k-1k-1nn 2 2k k對上式取對數(shù)有:對上式取對數(shù)有:k-1logk-1log2 2n nk k由于由于k k是整數(shù),故是整數(shù),故k= trunck= trunc(2 2n n)+1+1245.2 二叉樹對完全二叉樹的結(jié)點(diǎn)編號:對完全二叉樹的結(jié)點(diǎn)編號:從上到下,每一層從左到右從上到下,每一層從左到右 性質(zhì)性質(zhì)5 5:在一棵有在一棵有n n個結(jié)點(diǎn)的完全二叉樹中個結(jié)點(diǎn)的完全二叉樹中, ,對于編號為對于編號為i(i(1 1in)的結(jié)點(diǎn)的結(jié)點(diǎn): :1 1)當(dāng))當(dāng)i=1i=1,結(jié)點(diǎn),結(jié)點(diǎn)i i為根結(jié)點(diǎn)為根結(jié)點(diǎn)1 1)若有左孩子)若有左孩子(
24、(2i2in n) ),則左孩編號為,則左孩編號為2i2i2 2)若有右孩子)若有右孩子( (2i+12i+1n) ),則右孩子結(jié)點(diǎn)編號為,則右孩子結(jié)點(diǎn)編號為2i+12i+13 3)若有雙親,則雙親結(jié)點(diǎn)編號為)若有雙親,則雙親結(jié)點(diǎn)編號為trunc(i/2)trunc(i/2) A A F F E E D D C C B B1 12 23 34 45 56 6255.2二叉樹 1 1 二叉樹的順序結(jié)構(gòu)二叉樹的順序結(jié)構(gòu) /-二叉樹的順序存儲表示二叉樹的順序存儲表示- int MAX_TREE_SIZE 100Object treeMAX_TREE_SIZE存儲方案存儲方案: 用順序存儲結(jié)構(gòu)存儲一棵
25、二叉樹時,必須首先對該樹中每個用順序存儲結(jié)構(gòu)存儲一棵二叉樹時,必須首先對該樹中每個結(jié)點(diǎn)進(jìn)行結(jié)點(diǎn)進(jìn)行編號編號,樹中各結(jié)點(diǎn)的編號應(yīng)與等深度的滿二叉樹中對應(yīng),樹中各結(jié)點(diǎn)的編號應(yīng)與等深度的滿二叉樹中對應(yīng)位置上結(jié)點(diǎn)的編號相同。位置上結(jié)點(diǎn)的編號相同。用一組連續(xù)的內(nèi)存單元,按結(jié)點(diǎn)的用一組連續(xù)的內(nèi)存單元,按結(jié)點(diǎn)的編號編號順序依次存儲二叉樹的元素值。順序依次存儲二叉樹的元素值。 三二叉樹存貯結(jié)構(gòu)三二叉樹存貯結(jié)構(gòu)265.2 二 叉 樹例:例: 用一維數(shù)組用一維數(shù)組bt bt 存放一棵完全二叉樹,將標(biāo)號為存放一棵完全二叉樹,將標(biāo)號為 i i 的結(jié)點(diǎn)的的結(jié)點(diǎn)的數(shù)據(jù)元素存放在分量數(shù)據(jù)元素存放在分量 bti-1bti-1
26、中。存儲位置隱含了樹中的關(guān)系,樹中的中。存儲位置隱含了樹中的關(guān)系,樹中的關(guān)系是通過完全二叉樹的性質(zhì)實(shí)現(xiàn)的。例如,關(guān)系是通過完全二叉樹的性質(zhì)實(shí)現(xiàn)的。例如,bt5bt5(i=6)i=6)的雙親結(jié)點(diǎn)的雙親結(jié)點(diǎn)標(biāo)號是標(biāo)號是k=trunc(i/2)=3,k=trunc(i/2)=3,雙親結(jié)點(diǎn)所對應(yīng)的數(shù)組分量雙親結(jié)點(diǎn)所對應(yīng)的數(shù)組分量btk-1=bt2btk-1=bt2順序結(jié)構(gòu)圖示順序結(jié)構(gòu)圖示 A A F F E E D D C C B B1 12 23 34 45 56 6下標(biāo)下標(biāo) 0 1 2 3 4 5 6 7 m-10 1 2 3 4 5 6 7 m-1 A B C D E FA B C D E F編
27、號編號 1 2 3 4 5 6275.2 二 叉 樹非完全二叉樹的順序結(jié)構(gòu)非完全二叉樹的順序結(jié)構(gòu) 按完全二叉樹的形式補(bǔ)齊二叉樹所缺少的那些結(jié)點(diǎn),對二叉樹結(jié)點(diǎn)編號按完全二叉樹的形式補(bǔ)齊二叉樹所缺少的那些結(jié)點(diǎn),對二叉樹結(jié)點(diǎn)編號, ,將二叉樹原有的結(jié)點(diǎn)按編號存儲到內(nèi)存單元將二叉樹原有的結(jié)點(diǎn)按編號存儲到內(nèi)存單元“相應(yīng)相應(yīng)”的位置上。但這種方式的位置上。但這種方式對于畸形二叉樹,浪費(fèi)較大空間。對于畸形二叉樹,浪費(fèi)較大空間。 A A F F G G E E D D C C B B8 81 16 67 72 24 45 53 31010 A A F F G G E E D D C C B B9 90 1 2
28、 3 4 5 6 7 8 9 10 m-10 1 2 3 4 5 6 7 8 9 10 m-1A B C D E 0 F 0 0 GA B C D E 0 F 0 0 G28討論:討論: 對于對于完全二叉樹完全二叉樹來說,二叉樹中的結(jié)點(diǎn)的編號完全可以反映來說,二叉樹中的結(jié)點(diǎn)的編號完全可以反映出該二叉樹中結(jié)點(diǎn)之間的邏輯關(guān)系,可將此類二叉樹中結(jié)點(diǎn)的編出該二叉樹中結(jié)點(diǎn)之間的邏輯關(guān)系,可將此類二叉樹中結(jié)點(diǎn)的編號與數(shù)組下標(biāo)建立一一對應(yīng)關(guān)系,所以采用順序存儲結(jié)構(gòu)較好。號與數(shù)組下標(biāo)建立一一對應(yīng)關(guān)系,所以采用順序存儲結(jié)構(gòu)較好。 對于對于一般的二叉樹一般的二叉樹,則添加一些不存在的,則添加一些不存在的“空空”結(jié)
29、點(diǎn),使之結(jié)點(diǎn),使之成為一棵完全二叉樹。將其每個結(jié)點(diǎn)與完全二叉樹上的結(jié)點(diǎn)完全成為一棵完全二叉樹。將其每個結(jié)點(diǎn)與完全二叉樹上的結(jié)點(diǎn)完全對應(yīng),此時仍可用順序存儲結(jié)構(gòu)表示這棵二叉樹。可能造成空間對應(yīng),此時仍可用順序存儲結(jié)構(gòu)表示這棵二叉樹??赡茉斐煽臻g浪費(fèi),最壞的情況是:深度為浪費(fèi),最壞的情況是:深度為k且只有且只有k個結(jié)點(diǎn)的單支樹,需要長個結(jié)點(diǎn)的單支樹,需要長為為2 2k k-1-1的數(shù)組空間。的數(shù)組空間。295.2 二 叉 樹2 2 二叉鏈表二叉鏈表 二叉鏈表中每個結(jié)點(diǎn)包含三個域:數(shù)據(jù)域、左指針域、右指針域二叉鏈表中每個結(jié)點(diǎn)包含三個域:數(shù)據(jù)域、左指針域、右指針域 A A F F E E D D C
30、C B Bclass Bnodeptint data; Bnodept lchild, rchlid;二叉鏈表圖示 D D A A B B C C E E F F rchilddatalchild二叉鏈表結(jié)點(diǎn)二叉鏈表結(jié)點(diǎn)306.2 二 叉 樹 A A F F E E D D C C B B3 3 三叉鏈表(便于找到結(jié)點(diǎn)的雙親)三叉鏈表(便于找到結(jié)點(diǎn)的雙親) 三叉鏈表中每個結(jié)點(diǎn)包含四個域:數(shù)據(jù)域、雙親指針域、左指針域、三叉鏈表中每個結(jié)點(diǎn)包含四個域:數(shù)據(jù)域、雙親指針域、左指針域、右指針域右指針域class Bnodept int data; Bnodept lchild, rchild, pare
31、nt;ABDFECparentrchilddatalchild三叉鏈表結(jié)點(diǎn)31 5.3 5.3 二叉樹的遍歷二叉樹的遍歷 一一. . 二叉樹的遍歷方法二叉樹的遍歷方法 二二. . 遍歷的遞歸算法遍歷的遞歸算法 三三. . 遍歷的非遞歸算法遍歷的非遞歸算法325.3 二叉樹的遍歷遍歷:遍歷:按某種搜索路徑訪問二叉樹的每個結(jié)點(diǎn),而且每個結(jié)點(diǎn)僅被訪按某種搜索路徑訪問二叉樹的每個結(jié)點(diǎn),而且每個結(jié)點(diǎn)僅被訪問一次。問一次。訪問訪問:含義很廣,可以是對結(jié)點(diǎn)的各種處理:含義很廣,可以是對結(jié)點(diǎn)的各種處理,如修改結(jié)點(diǎn)數(shù)據(jù)、輸出,如修改結(jié)點(diǎn)數(shù)據(jù)、輸出結(jié)點(diǎn)數(shù)據(jù)。結(jié)點(diǎn)數(shù)據(jù)。 遍歷是各種數(shù)據(jù)結(jié)構(gòu)最基本的操作,許多其他的操
32、作可以在遍歷遍歷是各種數(shù)據(jù)結(jié)構(gòu)最基本的操作,許多其他的操作可以在遍歷基礎(chǔ)上實(shí)現(xiàn)?;A(chǔ)上實(shí)現(xiàn)。 如何訪問二叉樹的每個結(jié)點(diǎn),如何訪問二叉樹的每個結(jié)點(diǎn), 而且每個結(jié)點(diǎn)僅被訪問一次?而且每個結(jié)點(diǎn)僅被訪問一次?335.3 二叉樹的遍歷二叉樹的遍歷方法二叉樹的遍歷方法 二叉樹由二叉樹由根根、左子樹、左子樹、右子樹右子樹三部分組成三部分組成 二叉樹的遍歷二叉樹的遍歷可以分解為:訪問可以分解為:訪問根根,遍歷,遍歷左子樹左子樹和和遍歷遍歷右子樹右子樹令:令:L L:遍歷左子樹:遍歷左子樹 T T:訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn) R R:遍歷右子樹遍歷右子樹 約定先左后右約定先左后右, ,有三種遍歷方法:有三種遍歷方法:
33、 T T L L R R、L L T T R R、L L R R T T ,分別稱為分別稱為: : 先序遍歷、中序遍歷、后序遍歷先序遍歷、中序遍歷、后序遍歷 A A F F G G E E D D C C B B345.3 二叉樹的遍歷 先序遍歷(先序遍歷(T T L L R R) 若二叉樹非空若二叉樹非空 (1 1)訪問根結(jié)點(diǎn);)訪問根結(jié)點(diǎn); (2 2)先序遍歷左子樹;)先序遍歷左子樹; (3 3)先序遍歷右子樹)先序遍歷右子樹; 先序遍歷序列:先序遍歷序列:A,A,B,D,B,D,E E,G,G,C,FC,F A A F F G G E E D D C C B B例:先先序遍歷右圖所示的二
34、叉樹序遍歷右圖所示的二叉樹 (1 1)訪問根結(jié)點(diǎn))訪問根結(jié)點(diǎn)A A (2 2)先序遍歷左子樹:)先序遍歷左子樹:即按即按 T T L L R R 的順序遍歷的順序遍歷左子樹左子樹 (3 3)先序遍歷右子樹:)先序遍歷右子樹:即按即按 T T L L R R 的順序遍歷的順序遍歷右子樹右子樹355.3 二叉樹的遍歷中序遍歷(中序遍歷(L L T T R R)若二叉樹非空若二叉樹非空(1 1)中序遍歷左子樹)中序遍歷左子樹(2 2)訪問根結(jié)點(diǎn))訪問根結(jié)點(diǎn)(3 3)中序遍歷右子樹)中序遍歷右子樹 中序遍歷序列:中序遍歷序列: D,B,G,D,B,G,E E, ,A,A,C,FC,F A A F F
35、G G E E D D C C B B例:例:中序遍歷右圖所示的二叉樹中序遍歷右圖所示的二叉樹 (1 1)中序遍歷左子樹:即按)中序遍歷左子樹:即按 L L T T R R 的順序遍歷的順序遍歷左子樹左子樹 (2 2)訪問根結(jié)點(diǎn))訪問根結(jié)點(diǎn)A A (3 3)中序遍歷右子樹:即按)中序遍歷右子樹:即按 L L T T R R 的順序遍歷的順序遍歷右子樹右子樹365.3 二叉樹的遍歷后序遍歷(后序遍歷(L L R R T T)若二叉樹非空若二叉樹非空(1 1)后序遍歷左子樹)后序遍歷左子樹(2 2)后序遍歷右子樹)后序遍歷右子樹(3 3)訪問根結(jié)點(diǎn))訪問根結(jié)點(diǎn) 后序遍歷序列:后序遍歷序列: D,G
36、,D,G,E E,B,B,F,CF,C, ,A A例:后例:后序遍歷右圖所示的二叉樹序遍歷右圖所示的二叉樹 (1 1)后序遍歷左子樹:即按)后序遍歷左子樹:即按 L L R R T T 的順序遍歷的順序遍歷左子樹左子樹 (2 2)后序遍歷右子樹:即按)后序遍歷右子樹:即按 L L R R T T 的順序遍歷的順序遍歷右子樹右子樹 (3 3)訪問根結(jié)點(diǎn))訪問根結(jié)點(diǎn)A A A A F F G G E E D D C C B B375.3 二叉樹的遍歷 - - e e d d c c b b f f a a + + * * / / - - 后序遍歷序列:后序遍歷序列:a,b,c,d,-,a,b,c,
37、d,-,* *,+,+,e,f,/,e,f,/,- - 中序遍歷序列:中序遍歷序列:a,+,b,a,+,b,* *,c,-,d,c,-,d,- -,e,/,f,e,/,f 先序遍歷序列:先序遍歷序列:- -, ,+,a,+,a,* *,b,-,c,d,b,-,c,d,/,e,f/,e,f例:先例:先序遍歷、中序遍歷、序遍歷、中序遍歷、后后序遍歷下圖所示的二叉樹序遍歷下圖所示的二叉樹385.3 二叉樹的遍歷 若二叉樹非空若二叉樹非空 (1 1)訪問根結(jié)點(diǎn);)訪問根結(jié)點(diǎn); (2 2)先序遍歷左子樹)先序遍歷左子樹 (3 3)先序遍歷右子樹;)先序遍歷右子樹;二二. . 遍歷的遞歸算法遍歷的遞歸算法
38、先序遍歷(T T L L R R)的定義:上面先序遍歷的定義等價于:上面先序遍歷的定義等價于:若二叉樹為空,結(jié)束若二叉樹為空,結(jié)束 基本項(xiàng)基本項(xiàng)(也叫終止項(xiàng))(也叫終止項(xiàng))若二叉樹非空若二叉樹非空 遞歸項(xiàng)遞歸項(xiàng) (1 1)訪問根結(jié)點(diǎn);)訪問根結(jié)點(diǎn); (2 2)先序遍歷左子樹)先序遍歷左子樹 (3 3)先序遍歷右子樹;)先序遍歷右子樹;395.3 二叉樹的遍歷先序遍歷遞歸算法先序遍歷遞歸算法 void preorder (Bnodept root) if (root!=null) System.out.print(root.data); preorder(root.lchild); preord
39、er(root.rchild); 先序序列為先序序列為 + * a b c / d e稱為前綴表達(dá)式稱為前綴表達(dá)式 a a + + * * / / / d d / - -rootroot e e b b c c a a* *(b-c)+d/e(b-c)+d/e405.3 二叉樹的遍歷2 中序遍歷遞歸算法中序遍歷遞歸算法 void inorder (Bnodept root) if (root!=null)inorder(root.lchild); System.out.printf( root.data); inorder(root.rchild); 中序序列為中序序列為 a * b c+ d
40、 / e稱為中綴表達(dá)式稱為中綴表達(dá)式你能寫出后序遍歷遞歸算法了吧 a a + + * * / / / d d / - -rootroot e e b b c c a*(b-c)+d/e415.3 二叉樹的遍歷3 后序遍歷遞歸算法后序遍歷遞歸算法 void postorder (Bnodept root) if (root!=null)postorder(root.lchild); postorder(root.rchild); System.out.printf(root.data); 后序序列為后序序列為 a b c * d e / + 稱為后綴表達(dá)式稱為后綴表達(dá)式 a a + + * *
41、/ / / d d / - -rootroot e e b b c c a a* *(b-c)+d/e(b-c)+d/e42二叉樹的層次遍歷 二叉樹層次遍歷:先訪問根節(jié)點(diǎn),再依次訪問下層結(jié)點(diǎn),二叉樹層次遍歷:先訪問根節(jié)點(diǎn),再依次訪問下層結(jié)點(diǎn),每層結(jié)點(diǎn)按從左至右的順序訪問,直至全部結(jié)點(diǎn)訪問完每層結(jié)點(diǎn)按從左至右的順序訪問,直至全部結(jié)點(diǎn)訪問完畢。畢。 其實(shí)現(xiàn)可以其實(shí)現(xiàn)可以借助隊(duì)列借助隊(duì)列來完成,算法如下:來完成,算法如下: 1.把根節(jié)點(diǎn)壓入隊(duì)列;把根節(jié)點(diǎn)壓入隊(duì)列; 2.如果隊(duì)列非空,循環(huán)執(zhí)行以下操作:如果隊(duì)列非空,循環(huán)執(zhí)行以下操作: 1.從隊(duì)列中取出隊(duì)頭結(jié)點(diǎn),訪問該結(jié)點(diǎn);從隊(duì)列中取出隊(duì)頭結(jié)點(diǎn),訪問該
42、結(jié)點(diǎn); 2.若該結(jié)點(diǎn)的左孩子結(jié)點(diǎn)非空,則將該結(jié)點(diǎn)的左孩子結(jié)點(diǎn)入隊(duì)列;若該結(jié)點(diǎn)的左孩子結(jié)點(diǎn)非空,則將該結(jié)點(diǎn)的左孩子結(jié)點(diǎn)入隊(duì)列; 3.若該結(jié)點(diǎn)的右孩子結(jié)點(diǎn)非空,則將該結(jié)點(diǎn)的右孩子結(jié)點(diǎn)入隊(duì)列;若該結(jié)點(diǎn)的右孩子結(jié)點(diǎn)非空,則將該結(jié)點(diǎn)的右孩子結(jié)點(diǎn)入隊(duì)列; 3.結(jié)束結(jié)束435.3 二叉樹的遍歷對二叉樹的先序遍歷對二叉樹的先序遍歷:先訪問根結(jié)點(diǎn),然后沿其左鏈一:先訪問根結(jié)點(diǎn),然后沿其左鏈一直訪問下來,直到左鏈為空,最后再從左子樹返回到根直訪問下來,直到左鏈為空,最后再從左子樹返回到根結(jié)點(diǎn),最后訪問其右子樹。結(jié)點(diǎn),最后訪問其右子樹。故需要借助于棧,將根結(jié)點(diǎn)進(jìn)棧保存起來,將遍歷其左故需要借助于棧,將根結(jié)點(diǎn)進(jìn)棧保存
43、起來,將遍歷其左子樹的根結(jié)點(diǎn)進(jìn)棧,。當(dāng)左子樹遍歷完畢后,再子樹的根結(jié)點(diǎn)進(jìn)棧,。當(dāng)左子樹遍歷完畢后,再從棧中取回根結(jié)點(diǎn),再對其右子樹進(jìn)行遍歷進(jìn)棧操作。從棧中取回根結(jié)點(diǎn),再對其右子樹進(jìn)行遍歷進(jìn)棧操作。三三. . 二叉樹遍歷的非遞歸算法二叉樹遍歷的非遞歸算法遞歸算法邏輯清晰、易懂,但在實(shí)現(xiàn)時,由于函數(shù)調(diào)用棧層層疊加,遞歸算法邏輯清晰、易懂,但在實(shí)現(xiàn)時,由于函數(shù)調(diào)用棧層層疊加,效率不高,故有時考慮非遞歸算法。效率不高,故有時考慮非遞歸算法。 1 1 先序遍歷(先序遍歷(T L RT L R)的非遞歸算法。)的非遞歸算法。44先序遍歷非遞歸算法步驟先序遍歷非遞歸算法步驟: (1)初始化一個空棧)初始化一
44、個空棧 (2)當(dāng)前指針指向根結(jié)點(diǎn)。將根結(jié)點(diǎn)指針進(jìn)棧)當(dāng)前指針指向根結(jié)點(diǎn)。將根結(jié)點(diǎn)指針進(jìn)棧 (3)打印當(dāng)前結(jié)點(diǎn),當(dāng)前指針指向其左孩子并進(jìn))打印當(dāng)前結(jié)點(diǎn),當(dāng)前指針指向其左孩子并進(jìn)棧,重復(fù)(棧,重復(fù)(3),直到左孩子為),直到左孩子為null (4)依次退棧,將當(dāng)前指針指向其右孩子)依次退棧,將當(dāng)前指針指向其右孩子 (5)若棧非空或當(dāng)前指針非)若棧非空或當(dāng)前指針非null,執(zhí)行(,執(zhí)行(3) (6)結(jié)束。)結(jié)束。455.3二叉樹的遍歷 d d b b a a * * - - / / c c + + e erootrootp pnode node 6 65 54 43 32 21 10 0toptop
45、System.out.print( root.data);+ +nodetop=p;top+;toptopp=p.lchild;p pSystem.out.print( root.data);* *nodetop=p;top+;toptopp=p.lchild;p pSystem.out.print( root.data) ;a anodetop=p;top+;toptopp=p.lchild;p pif (top0)top - -;toptopp=nodetop;p pp=p.rch;p ptoptopp pp pSystem.out.print( root.data) ;- -nodeto
46、p=p;top+;toptopp=p.lchild;p pb btoptopp ptop - -; p=nodetop; p=p.rch;toptopp ptoptopp pp pp pc cSystem.out.print( root.data)nodetop=p;top+;toptopp=p.lchild;p ptop - -;toptopp=nodetop;p pp=p.rchtoptopp pp p/ /toptopd dSystem.out. print(root.data);nodetop=p;top+; p=p.lchild;465.3 二叉樹的遍歷先序遍歷的非遞歸算法先序遍歷的
47、非遞歸算法void preorder2 (Bnodept root) Bnodept p, nodeMAX; int top=0; p=root; do while( p!=null) System.out.printf(p.data) ; nodetop=p;top+; p=p.lchild; if (top0) top - -; p=nodetop; p=p.rchild; while(top0|p!=null); d d b b e e a a * * - - / / c c + +475.4 遍歷的應(yīng)用 遍歷是二叉樹的基本操作:二叉樹許多操作遍歷是二叉樹的基本操作:二叉樹許多操作可在遍
48、歷過程中完成,本節(jié)再例子舉幾個二叉可在遍歷過程中完成,本節(jié)再例子舉幾個二叉樹遍歷應(yīng)用實(shí)例。樹遍歷應(yīng)用實(shí)例。485.4 遍歷的應(yīng)用例例1 編寫編寫 求二叉樹的葉子結(jié)點(diǎn)個數(shù)的算法求二叉樹的葉子結(jié)點(diǎn)個數(shù)的算法輸入:輸入:二叉樹的二叉鏈表二叉樹的二叉鏈表結(jié)果:結(jié)果:二叉樹的葉子結(jié)點(diǎn)個數(shù)二叉樹的葉子結(jié)點(diǎn)個數(shù) F F D D A A B B C C E E rootrootint leaf(Bnodept root) /采用二叉鏈表存貯二叉樹,采用二叉鏈表存貯二叉樹,n為全局變量,用于累加二叉樹的葉子結(jié)點(diǎn)為全局變量,用于累加二叉樹的葉子結(jié)點(diǎn) /的個數(shù)。的個數(shù)。本算法在先序遍歷二叉樹的過程中,統(tǒng)計(jì)葉子結(jié)點(diǎn)的
49、個數(shù)本算法在先序遍歷二叉樹的過程中,統(tǒng)計(jì)葉子結(jié)點(diǎn)的個數(shù) if(root=null) return 0;/空樹時,空樹時,n=0 else if(root.lchild= =null&root.rch= =null) return 1; /若若root所指點(diǎn)為葉子所指點(diǎn)為葉子, 則返回則返回1 return(leaf(root.lchild)+leaf(root.rchild); 與與先序遍歷算法先序遍歷算法比較一下比較一下!495.4 遍歷的應(yīng)用 例例2 建立二叉鏈表建立二叉鏈表 輸入:輸入:二叉樹的先序序列二叉樹的先序序列 結(jié)果:結(jié)果:二叉樹的二叉鏈表二叉樹的二叉鏈表 遍歷操作訪問二叉樹的每
50、個結(jié)點(diǎn),而且每個結(jié)點(diǎn)僅被訪問一次。是遍歷操作訪問二叉樹的每個結(jié)點(diǎn),而且每個結(jié)點(diǎn)僅被訪問一次。是否可在利用否可在利用遍歷,建立遍歷,建立二叉鏈表的所有結(jié)點(diǎn)并完成相應(yīng)結(jié)點(diǎn)的鏈接?二叉鏈表的所有結(jié)點(diǎn)并完成相應(yīng)結(jié)點(diǎn)的鏈接?基本思想:基本思想:輸入(輸入(在空子樹處添加字符在空子樹處添加字符* *的二叉樹的)先序序列(設(shè)每個的二叉樹的)先序序列(設(shè)每個元素是元素是一個字符)按先序遍歷的順序,建立二叉鏈表的所有結(jié)點(diǎn)并完成一個字符)按先序遍歷的順序,建立二叉鏈表的所有結(jié)點(diǎn)并完成相應(yīng)結(jié)點(diǎn)的鏈接相應(yīng)結(jié)點(diǎn)的鏈接 A A F F E E D D C C B B*A B D A B D * * F F * * * *
51、 * * C E C E * * * * * *505.4 遍歷的應(yīng)用 輸入輸入(在空子樹處添加空格字符的二叉樹的)在空子樹處添加空格字符的二叉樹的)先序序列先序序列(設(shè)每個元素是(設(shè)每個元素是一個字一個字 符)符)按先序遍歷的順序,建立二叉鏈表按先序遍歷的順序,建立二叉鏈表,并將該二叉鏈表根結(jié),并將該二叉鏈表根結(jié)點(diǎn)指針賦給點(diǎn)指針賦給root Bnodept create_tree(Bnodept root) char ch; Scanner sc=new Scanner(System.in); ch=(sc.nextLine().charAt(0); if (ch= = *) root=nu
52、ll; / 若若ch= = * 則則root=null返回返回 else / 若若ch! = * root=new Bnodept() root.date = ch; / 建立(根)結(jié)點(diǎn)建立(根)結(jié)點(diǎn) root.lchild=create_tree(root.lchild); /構(gòu)造左子樹鏈表,并將左子樹根結(jié)點(diǎn)指針構(gòu)造左子樹鏈表,并將左子樹根結(jié)點(diǎn)指針 賦給(根)結(jié)點(diǎn)賦給(根)結(jié)點(diǎn) 的左孩子域的左孩子域 root.rchild=create_tree(root.rchild); /構(gòu)造右子樹鏈表,并將右子樹根結(jié)點(diǎn)指針構(gòu)造右子樹鏈表,并將右子樹根結(jié)點(diǎn)指針 賦給(根)結(jié)點(diǎn)賦給(根)結(jié)點(diǎn) 的右孩子域的
53、右孩子域 return (root); 515.4 遍歷的應(yīng)用 D D A A B B C C E E F F T T 先序序列:先序序列:A B D F C EA B D F C E(在空子樹處添加(在空子樹處添加* *的二叉樹的)先序序列:的二叉樹的)先序序列: A B D F C E A B D F C E A A F F E E D D C C B B A A F F E E D D C C B B52 兩點(diǎn)說明兩點(diǎn)說明:1. 按先序次序輸入二叉樹中結(jié)點(diǎn)的值,用按先序次序輸入二叉樹中結(jié)點(diǎn)的值,用*表示空樹,對每一表示空樹,對每一個結(jié)點(diǎn)應(yīng)當(dāng)確定其左右子樹的值(為空時必須用特定的空字符占個
54、結(jié)點(diǎn)應(yīng)當(dāng)確定其左右子樹的值(為空時必須用特定的空字符占位),故執(zhí)行此程序時,最好先在紙上畫出你想建立的二叉樹,每位),故執(zhí)行此程序時,最好先在紙上畫出你想建立的二叉樹,每個結(jié)點(diǎn)的左右子樹必須確定,若為空,則用特定字符標(biāo)出,然后再個結(jié)點(diǎn)的左右子樹必須確定,若為空,則用特定字符標(biāo)出,然后再按先序輸入這棵二叉樹的字符序列;按先序輸入這棵二叉樹的字符序列;2. 為了簡化程序的書寫量,以及程序的清晰性,對結(jié)點(diǎn)的訪問為了簡化程序的書寫量,以及程序的清晰性,對結(jié)點(diǎn)的訪問以一條輸出語句表示,若有更復(fù)雜的或多種訪問,可以將結(jié)點(diǎn)的訪以一條輸出語句表示,若有更復(fù)雜的或多種訪問,可以將結(jié)點(diǎn)的訪問編寫成函數(shù),然后通過函
55、數(shù)的調(diào)用。讀者若有興趣,可自行編寫。問編寫成函數(shù),然后通過函數(shù)的調(diào)用。讀者若有興趣,可自行編寫。5.4 遍歷的應(yīng)用53 二叉排序樹二叉排序樹 或者為一棵空樹,或?yàn)闈M足如下條件的二叉樹或者為一棵空樹,或?yàn)闈M足如下條件的二叉樹 (1)若左子樹非空,則左子樹上所有結(jié)點(diǎn)的值均小于它)若左子樹非空,則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值;的根結(jié)點(diǎn)的值; (2)若右子樹非空,則右子樹上所有結(jié)點(diǎn)的值均大于它)若右子樹非空,則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值;的根結(jié)點(diǎn)的值; (3)它的左右子樹也分別為二叉排序樹。)它的左右子樹也分別為二叉排序樹。 建立過程示例建立過程示例v二叉樹的建立二叉樹的建立
56、2(建立二叉排序樹(建立二叉排序樹,P206)5.4 遍歷的應(yīng)用54輸入序列輸入序列45,12,37,3,53,100,24451253337100245.4 遍歷的應(yīng)用算法思想:算法思想: 設(shè)二叉排序樹為設(shè)二叉排序樹為b,新申請的結(jié)點(diǎn)為,新申請的結(jié)點(diǎn)為s。則則(1)若)若b是空樹,將是空樹,將s結(jié)點(diǎn)作為根結(jié)點(diǎn);結(jié)點(diǎn)作為根結(jié)點(diǎn);(2)若)若s.data等于等于b的根結(jié)點(diǎn)的數(shù)據(jù)域,的根結(jié)點(diǎn)的數(shù)據(jù)域,不作任何操作;不作任何操作;(3)若)若s.data小于小于b的根結(jié)點(diǎn)的數(shù)據(jù)域,的根結(jié)點(diǎn)的數(shù)據(jù)域,則將則將s插入到左子樹中;插入到左子樹中;(4)若)若s.data大于大于b的根結(jié)點(diǎn)的數(shù)據(jù)域,的根結(jié)點(diǎn)
57、的數(shù)據(jù)域,則將則將s插入到右子樹中。插入到右子樹中。55 void insert(Bnodept T,int x) if (T=null|T.data=x) return; /如果結(jié)點(diǎn)不存在或數(shù)據(jù)已存在如果結(jié)點(diǎn)不存在或數(shù)據(jù)已存在,返回返回 else if(xT.data) /將數(shù)據(jù)結(jié)點(diǎn)添加到左子樹將數(shù)據(jù)結(jié)點(diǎn)添加到左子樹 if (T.lchild=null) /左子樹為空則創(chuàng)建左子樹為空則創(chuàng)建Bnodept temp=new Bnodept();temp.data=x;temp.lchild=temp.rchild=null;T.lchild=temp;else insert(T.lchild,
58、x); /否則遞歸調(diào)用否則遞歸調(diào)用 else /數(shù)據(jù)結(jié)點(diǎn)添加到右子樹數(shù)據(jù)結(jié)點(diǎn)添加到右子樹 if (T.rchild=null) /右子樹為空則創(chuàng)建右子樹為空則創(chuàng)建 Bnodept temp=new Bnodept();temp.data=x;temp.lchild=temp.rchild=null;T.rchild=temp;else insert(T.rchild,x); /否則遞歸調(diào)用否則遞歸調(diào)用 建立一棵二叉排序樹建立一棵二叉排序樹5.4 遍歷的應(yīng)用56 void CreateBiTree(Bnodept root) int x;Scanner sc=new Scanner(System
59、.in)x=sc.nextInt(); while (x!=-1)if(root=null) /如果根節(jié)點(diǎn)為空則創(chuàng)建根節(jié)點(diǎn)如果根節(jié)點(diǎn)為空則創(chuàng)建根節(jié)點(diǎn) root =new Bnodept(); root.data=x; root.lchild=root.rchild=null;else insert(root,x); /否則插入排序數(shù)中否則插入排序數(shù)中 x=sc.nextInt(); 5.4 遍歷的應(yīng)用57小 結(jié) 1 1 二叉樹:二叉樹: 或?yàn)榭諛?,或由根及兩顆不相交的左子或?yàn)榭諛?,或由根及兩顆不相交的左子樹、右子樹構(gòu)成,并且左、右子樹本身也是二叉樹;樹、右子樹構(gòu)成,并且左、右子樹本身也是二叉樹
60、; 2 2 二叉樹即可以用順序結(jié)構(gòu)存儲,也可用鏈?zhǔn)浇Y(jié)構(gòu)二叉樹即可以用順序結(jié)構(gòu)存儲,也可用鏈?zhǔn)浇Y(jié)構(gòu)存儲;存儲;3 3 遍歷:按某種搜索路徑訪問二叉樹的每個結(jié)點(diǎn),每遍歷:按某種搜索路徑訪問二叉樹的每個結(jié)點(diǎn),每個結(jié)點(diǎn)僅被訪問一次。個結(jié)點(diǎn)僅被訪問一次。 二叉樹的遍歷可以分解為:訪二叉樹的遍歷可以分解為:訪問根,遍歷問根,遍歷左子樹和左子樹和遍歷遍歷右子樹,本課程介紹了三種右子樹,本課程介紹了三種遍歷算法:遍歷算法:先序遍歷、中序遍歷、后序遍歷;先序遍歷、中序遍歷、后序遍歷;58第五章 樹和二叉樹 5.5 5.5 線索二叉樹線索二叉樹 一.分析與設(shè)計(jì)分析與設(shè)計(jì) 二、線索二叉樹上如何尋找結(jié)點(diǎn)的前驅(qū)和后繼二
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 實(shí)務(wù)課程設(shè)計(jì)部門職責(zé)
- 畜牧飼料企業(yè)社會責(zé)任與可持續(xù)發(fā)展考核試卷
- 電子制造中的自動化光學(xué)檢測考核試卷
- 2024展覽搭建與展會效果評估服務(wù)合同3篇
- 2024年解除婚姻關(guān)系后商業(yè)利益分割協(xié)議3篇
- 電機(jī)制造中的供應(yīng)鏈管理與合作模式考核試卷
- 煉鐵高爐爐頂煤氣的排放與控制考核試卷
- 期貨市場信息服務(wù)考核試卷
- 煉鐵過程中的金屬熔凝與析出過程的結(jié)構(gòu)動力學(xué)考核試卷
- 2024年網(wǎng)絡(luò)游戲運(yùn)營合同標(biāo)的為網(wǎng)絡(luò)游戲產(chǎn)品
- 如何防止個人信息被盜用
- 電氣領(lǐng)域知識培訓(xùn)課件
- 金融產(chǎn)品分類介紹
- 2024-2025學(xué)年上學(xué)期深圳初中語文七年級期末模擬卷2
- 期末檢測試卷(含答案)2024-2025學(xué)年數(shù)學(xué)五年級上冊人教版
- 2023年上海商學(xué)院招聘筆試真題
- 標(biāo)準(zhǔn)2024項(xiàng)目投資協(xié)議書
- 中建幕墻高處防墜落專項(xiàng)方案方案
- 鎂合金回收與再利用
- 2024年貴州省農(nóng)業(yè)農(nóng)村廳所屬事業(yè)單位招聘人員管理單位遴選500模擬題附帶答案詳解
- 頭皮腫物患者的護(hù)理
評論
0/150
提交評論