




版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、樹的應(yīng)用樹的應(yīng)用w 某些數(shù)據(jù)庫(kù)管理系統(tǒng)含有分層結(jié)構(gòu)的數(shù)據(jù)庫(kù);復(fù)雜的程序,采用的基本數(shù)某些數(shù)據(jù)庫(kù)管理系統(tǒng)含有分層結(jié)構(gòu)的數(shù)據(jù)庫(kù);復(fù)雜的程序,采用的基本數(shù)據(jù)結(jié)構(gòu)是樹;據(jù)結(jié)構(gòu)是樹;w 在編譯系統(tǒng)中,編譯程序把高級(jí)語(yǔ)言的語(yǔ)句或表達(dá)式分解為樹結(jié)構(gòu)加以分在編譯系統(tǒng)中,編譯程序把高級(jí)語(yǔ)言的語(yǔ)句或表達(dá)式分解為樹結(jié)構(gòu)加以分析和處理,然后生成機(jī)器代碼的目的碼指令;析和處理,然后生成機(jī)器代碼的目的碼指令;w 操作系統(tǒng)的文件處理采用分級(jí)管理的辦法,采用樹結(jié)構(gòu),以提高文件的存操作系統(tǒng)的文件處理采用分級(jí)管理的辦法,采用樹結(jié)構(gòu),以提高文件的存取速度;取速度;w 某些操作系統(tǒng)把主存也按樹結(jié)構(gòu)劃分,樹中的每個(gè)結(jié)點(diǎn)包含數(shù)據(jù)或代碼段
2、;某些操作系統(tǒng)把主存也按樹結(jié)構(gòu)劃分,樹中的每個(gè)結(jié)點(diǎn)包含數(shù)據(jù)或代碼段;w 某些程序模塊本身近似于樹型結(jié)構(gòu);某些程序模塊本身近似于樹型結(jié)構(gòu);w 二叉排序樹:特點(diǎn)是用非線性結(jié)構(gòu)表示一個(gè)線性有序表;二叉排序樹:特點(diǎn)是用非線性結(jié)構(gòu)表示一個(gè)線性有序表;w 決策樹:在企業(yè)的數(shù)據(jù)處理和系統(tǒng)分析等領(lǐng)域中出現(xiàn)的決策問題:即要求決策樹:在企業(yè)的數(shù)據(jù)處理和系統(tǒng)分析等領(lǐng)域中出現(xiàn)的決策問題:即要求根據(jù)一些給定條件來(lái)確定應(yīng)采取什么行動(dòng),如保險(xiǎn)公司的業(yè)務(wù)決策;根據(jù)一些給定條件來(lái)確定應(yīng)采取什么行動(dòng),如保險(xiǎn)公司的業(yè)務(wù)決策;w 博弈樹(博弈樹(Game Tree):人):人機(jī)博弈;機(jī)博弈;w 堆(堆(heap)排序:實(shí)際上是一棵完
3、全二叉樹結(jié)點(diǎn)的層次序列;)排序:實(shí)際上是一棵完全二叉樹結(jié)點(diǎn)的層次序列;w Ldap: 輕量目錄訪問協(xié)議;輕量目錄訪問協(xié)議;w Huffman樹:信息檢索;樹:信息檢索;w 樹例與特征樹例與特征n社會(huì)的組織結(jié)構(gòu)社會(huì)的組織結(jié)構(gòu)n家族的族譜家族的族譜n計(jì)算機(jī)中的目錄組織計(jì)算機(jī)中的目錄組織w 描述層次結(jié)構(gòu),是一種描述層次結(jié)構(gòu),是一種一對(duì)多一對(duì)多的邏輯關(guān)系的邏輯關(guān)系是一種非線性結(jié)構(gòu)是一種非線性結(jié)構(gòu)樹的形式化定義樹的形式化定義 樹:樹:T=D,R。D是包含是包含n個(gè)節(jié)點(diǎn)的有窮集合(個(gè)節(jié)點(diǎn)的有窮集合(n0)。)。當(dāng)當(dāng)n=0時(shí)為空樹,否則關(guān)系時(shí)為空樹,否則關(guān)系R滿足以下條件滿足以下條件: l 有且僅有一個(gè)節(jié)點(diǎn)
4、有且僅有一個(gè)節(jié)點(diǎn)d0D,它對(duì)于關(guān)系,它對(duì)于關(guān)系R來(lái)說(shuō)沒來(lái)說(shuō)沒有前驅(qū)節(jié)點(diǎn),節(jié)點(diǎn)有前驅(qū)節(jié)點(diǎn),節(jié)點(diǎn)d0稱作樹的稱作樹的根節(jié)點(diǎn)根節(jié)點(diǎn)。l 除節(jié)點(diǎn)除節(jié)點(diǎn)d0外,外,D中的每個(gè)節(jié)點(diǎn)對(duì)于關(guān)系中的每個(gè)節(jié)點(diǎn)對(duì)于關(guān)系R來(lái)說(shuō)都來(lái)說(shuō)都有且有且僅有一個(gè)前驅(qū)節(jié)點(diǎn)僅有一個(gè)前驅(qū)節(jié)點(diǎn)。l D中每個(gè)節(jié)點(diǎn)對(duì)于關(guān)系中每個(gè)節(jié)點(diǎn)對(duì)于關(guān)系R來(lái)說(shuō)可以有來(lái)說(shuō)可以有零個(gè)或多個(gè)零個(gè)或多個(gè)后繼節(jié)點(diǎn)后繼節(jié)點(diǎn)。7.1 7.1 樹的基本概念及其樹的基本概念及其ADTADT定義定義 7.1.1 樹的定義樹的定義樹的遞歸定義:樹的遞歸定義: 樹樹是由是由n(n0)個(gè)節(jié)點(diǎn)組成的有限集合(記為)個(gè)節(jié)點(diǎn)組成的有限集合(記為T)。其中:)。其中: l 如果如果n=0
5、,它是一棵空樹,這是樹的特例;,它是一棵空樹,這是樹的特例;l 如果如果n0,這,這n個(gè)節(jié)點(diǎn)中存在(且僅存在)一個(gè)節(jié)點(diǎn)個(gè)節(jié)點(diǎn)中存在(且僅存在)一個(gè)節(jié)點(diǎn)作為樹的根節(jié)點(diǎn),簡(jiǎn)稱為根節(jié)點(diǎn)(作為樹的根節(jié)點(diǎn),簡(jiǎn)稱為根節(jié)點(diǎn)(root),其余節(jié)點(diǎn)),其余節(jié)點(diǎn)可分為可分為m (m0)個(gè)互不相交的有限集)個(gè)互不相交的有限集T1,T2,Tm,其其中每一棵子集本身又是一棵符合本定義的中每一棵子集本身又是一棵符合本定義的樹樹,稱為,稱為根根root的子樹。的子樹。rootT1T2Tm樹定義樹定義ACBGFEHIJDMKLAT1T2T3樹的抽象數(shù)據(jù)類型樹的抽象數(shù)據(jù)類型ADT Tree 數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象 D:D是具有相同性
6、質(zhì)的數(shù)據(jù)元素的集合。是具有相同性質(zhì)的數(shù)據(jù)元素的集合。 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系R:若:若D為空集,則稱為空樹;若為空集,則稱為空樹;若D僅含有一個(gè)數(shù)據(jù)元僅含有一個(gè)數(shù)據(jù)元素,則素,則R為空集,否則為空集,否則R=H,H是如下二元關(guān)系:是如下二元關(guān)系: (1 1)在在D中存在唯一的稱為根的數(shù)據(jù)元素中存在唯一的稱為根的數(shù)據(jù)元素root,它在關(guān)系,它在關(guān)系H下下無(wú)前驅(qū);無(wú)前驅(qū); (2)若)若D-root,則存在則存在D-root的一個(gè)劃分的一個(gè)劃分D1,D2Dm(m0),對(duì)任意對(duì)任意 j k(1 j,k m)有有 Dj DK= ,且對(duì)任意的且對(duì)任意的 i(1 i m ),存在唯一的數(shù)據(jù)元素存在唯一的數(shù)據(jù)元素x
7、i Di , H; (3)對(duì)應(yīng)于)對(duì)應(yīng)于D-root的劃分,的劃分,H-,有唯有唯一的一個(gè)劃分一的一個(gè)劃分H1, H2,Hm(m0),對(duì)任意對(duì)任意j k(1 j,k m)有有Hj Hk= ,且對(duì)任意且對(duì)任意i(1 i m ),Hi是是Di上的二元關(guān)系,上的二元關(guān)系, ( (Di,Hi)是一棵符合本定義的樹,稱為根)是一棵符合本定義的樹,稱為根root的子樹。的子樹。 注意:注意:“”是集合的補(bǔ)運(yùn)是集合的補(bǔ)運(yùn)算,算,“ ”是集合的交運(yùn)算是集合的交運(yùn)算基本操作:基本操作: TreeInit(T); TreeChild (T,x,i); Treebuild(T,F); TreeClear(T); T
8、raverse (T); TreeRoot(T); TreeParent(T,x); TreeRightBrother(T,x); TreeLeftBrother(T,x); TreeInsert(T,y,i,x);ADT Tree樹的抽象數(shù)據(jù)類型樹的抽象數(shù)據(jù)類型7.1.2 樹的表示樹的表示 (1)樹形表示法。)樹形表示法。這是樹的最基本的表示,使用一棵倒這是樹的最基本的表示,使用一棵倒置的樹表示樹結(jié)構(gòu),非常直觀和形象。下圖就是采用這種表置的樹表示樹結(jié)構(gòu),非常直觀和形象。下圖就是采用這種表示法。示法。ABCDEFGJHIKLM邏輯結(jié)構(gòu)表示邏輯結(jié)構(gòu)表示1 (2)文氏圖表示法。)文氏圖表示法。使用
9、集合以及集合的包含關(guān)系描述樹結(jié)使用集合以及集合的包含關(guān)系描述樹結(jié)構(gòu)。下圖就是樹的文氏圖表示法。構(gòu)。下圖就是樹的文氏圖表示法。ABCDEFGJHIKLM邏輯結(jié)構(gòu)表示邏輯結(jié)構(gòu)表示2AEFBCGJHDKLMI (3)凹入表示法。)凹入表示法。使用線段的伸縮描述樹結(jié)構(gòu)。下使用線段的伸縮描述樹結(jié)構(gòu)。下圖是樹的凹入表示法。圖是樹的凹入表示法。邏輯結(jié)構(gòu)表示邏輯結(jié)構(gòu)表示3ABCDEFGJHIKLM(4)括號(hào)表示法。)括號(hào)表示法。將樹的根節(jié)點(diǎn)寫在括號(hào)的左邊,除將樹的根節(jié)點(diǎn)寫在括號(hào)的左邊,除根節(jié)點(diǎn)之外的其余節(jié)點(diǎn)寫在括號(hào)中并用逗號(hào)間隔來(lái)描述根節(jié)點(diǎn)之外的其余節(jié)點(diǎn)寫在括號(hào)中并用逗號(hào)間隔來(lái)描述樹結(jié)構(gòu)。下圖是樹的括號(hào)表示法
10、。樹結(jié)構(gòu)。下圖是樹的括號(hào)表示法。 括號(hào)表示法括號(hào)表示法 A(B(E,F),C(G(J),D(H,I(K,L,M) ABCDEFGJHIKLM樹的其它邏輯表示方式樹的其它邏輯表示方式ACBGFEHIJDMKLAJIMHDGCFLKEB凹入表示法凹入表示法ABFEKLGCDHMIJ嵌套集合表示法嵌套集合表示法(A(B(E(K,L),F),C(G),D(H(M),I,J)廣義表表示法廣義表表示法樹型表示法樹型表示法類似于書的編目類似于書的編目 7.1.3 樹的基本術(shù)語(yǔ)樹的基本術(shù)語(yǔ) 1. 節(jié)點(diǎn)的度與樹的度:節(jié)點(diǎn)的度與樹的度:樹中某樹中某個(gè)節(jié)點(diǎn)的子樹的個(gè)數(shù)稱為該節(jié)點(diǎn)的個(gè)節(jié)點(diǎn)的子樹的個(gè)數(shù)稱為該節(jié)點(diǎn)的度。樹
11、中各節(jié)點(diǎn)的度的最大值稱為度。樹中各節(jié)點(diǎn)的度的最大值稱為樹的度,通常將度為樹的度,通常將度為m的樹稱為的樹稱為m次樹次樹。 2. 分支節(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)。度為零的節(jié)點(diǎn)稱為終端節(jié)點(diǎn)或葉節(jié)點(diǎn)。在分又叫分支節(jié)點(diǎn)。度為零的節(jié)點(diǎn)稱為終端節(jié)點(diǎn)或葉節(jié)點(diǎn)。在分支節(jié)點(diǎn)中,每個(gè)節(jié)點(diǎn)的分支數(shù)就是該節(jié)點(diǎn)的度。如對(duì)于度為支節(jié)點(diǎn)中,每個(gè)節(jié)點(diǎn)的分支數(shù)就是該節(jié)點(diǎn)的度。如對(duì)于度為1的節(jié)點(diǎn)的節(jié)點(diǎn),其分支數(shù)為其分支數(shù)為1,被稱為單分支節(jié)點(diǎn);對(duì)于度為,被稱為單分支節(jié)點(diǎn);對(duì)于度為2的節(jié)的節(jié)點(diǎn),其分支數(shù)為點(diǎn),其分支數(shù)為2,被稱為雙分支節(jié)點(diǎn),其余類推。,被稱
12、為雙分支節(jié)點(diǎn),其余類推。ABCDEFGJHIKLM度為度為3度為度為2ABCDEFGJHIKLM度為度為3度為度為2 3. 路徑與路徑長(zhǎng)度:路徑與路徑長(zhǎng)度:對(duì)于任意對(duì)于任意兩個(gè)節(jié)點(diǎn)兩個(gè)節(jié)點(diǎn)di和和dj,若樹中存在一個(gè)節(jié),若樹中存在一個(gè)節(jié)點(diǎn)序列點(diǎn)序列di,di1,di2,din,dj,使得序列中,使得序列中除除di外的任一節(jié)點(diǎn)都是其在序列中的外的任一節(jié)點(diǎn)都是其在序列中的前一個(gè)節(jié)點(diǎn)的后繼,則稱該節(jié)點(diǎn)序前一個(gè)節(jié)點(diǎn)的后繼,則稱該節(jié)點(diǎn)序列為由列為由di到到dj的一條路徑,用路徑所的一條路徑,用路徑所通過的節(jié)點(diǎn)序列通過的節(jié)點(diǎn)序列(di,di1,di2,dj)表示表示這條路徑這條路徑。 路徑長(zhǎng)度路徑長(zhǎng)度等于
13、路徑所通過的節(jié)點(diǎn)等于路徑所通過的節(jié)點(diǎn)數(shù)目減數(shù)目減1(即路徑上分支數(shù)目)。(即路徑上分支數(shù)目)。ABCDEFGJHIKLMA到到K的路徑為(的路徑為(A,D,I,K)其長(zhǎng)度為其長(zhǎng)度為3 4. 孩子節(jié)點(diǎn)、雙親節(jié)點(diǎn)和兄弟節(jié)孩子節(jié)點(diǎn)、雙親節(jié)點(diǎn)和兄弟節(jié)點(diǎn):點(diǎn):在一棵樹中,每個(gè)節(jié)點(diǎn)的后繼,在一棵樹中,每個(gè)節(jié)點(diǎn)的后繼,被稱作該節(jié)點(diǎn)的孩子節(jié)點(diǎn)(或子女節(jié)被稱作該節(jié)點(diǎn)的孩子節(jié)點(diǎn)(或子女節(jié)點(diǎn))。相應(yīng)地,該節(jié)點(diǎn)被稱作孩子節(jié)點(diǎn))。相應(yīng)地,該節(jié)點(diǎn)被稱作孩子節(jié)點(diǎn)的點(diǎn)的雙親節(jié)點(diǎn)雙親節(jié)點(diǎn)(或父母節(jié)點(diǎn))。(或父母節(jié)點(diǎn))。 具有同一雙親的孩子節(jié)點(diǎn)互為兄弟具有同一雙親的孩子節(jié)點(diǎn)互為兄弟節(jié)點(diǎn)。進(jìn)一步推廣這些關(guān)系,可以把節(jié)點(diǎn)。進(jìn)一步推廣
14、這些關(guān)系,可以把每個(gè)節(jié)點(diǎn)的所有子樹中的節(jié)點(diǎn)稱為該每個(gè)節(jié)點(diǎn)的所有子樹中的節(jié)點(diǎn)稱為該節(jié)點(diǎn)的節(jié)點(diǎn)的子孫節(jié)點(diǎn)子孫節(jié)點(diǎn)。從樹根節(jié)點(diǎn)到達(dá)該節(jié)點(diǎn)的路徑上經(jīng)從樹根節(jié)點(diǎn)到達(dá)該節(jié)點(diǎn)的路徑上經(jīng)過的所有節(jié)點(diǎn)被稱作該節(jié)點(diǎn)的過的所有節(jié)點(diǎn)被稱作該節(jié)點(diǎn)的祖先節(jié)祖先節(jié)點(diǎn)點(diǎn)。ABCDEFGJHIKLM 5. 節(jié)點(diǎn)的層次和樹的高度:節(jié)點(diǎn)的層次和樹的高度:樹樹中的每個(gè)節(jié)點(diǎn)都處在一定的層次上。中的每個(gè)節(jié)點(diǎn)都處在一定的層次上。節(jié)點(diǎn)的層次從樹根開始定義,根節(jié)節(jié)點(diǎn)的層次從樹根開始定義,根節(jié)點(diǎn)為第點(diǎn)為第1層,它的孩子節(jié)點(diǎn)為第層,它的孩子節(jié)點(diǎn)為第2層層,以此類推以此類推,一個(gè)節(jié)點(diǎn)所在的層次為一個(gè)節(jié)點(diǎn)所在的層次為其雙親節(jié)點(diǎn)所在的層次加其雙親節(jié)點(diǎn)所
15、在的層次加1。樹中。樹中節(jié)點(diǎn)的最大層次稱為樹的節(jié)點(diǎn)的最大層次稱為樹的高度高度(或(或樹的樹的深度深度)。)。 6. 有序樹和無(wú)序樹:有序樹和無(wú)序樹:若樹中各若樹中各節(jié)點(diǎn)的子樹是按照一定的次序從左節(jié)點(diǎn)的子樹是按照一定的次序從左向右安排的,且相對(duì)次序是不能隨向右安排的,且相對(duì)次序是不能隨意變換的,則稱為意變換的,則稱為有序樹,有序樹,否則稱否則稱為為無(wú)序樹無(wú)序樹。ABCDEFGJHIKLM1234有的教材規(guī)定為第有的教材規(guī)定為第0層層一般討論無(wú)序樹一般討論無(wú)序樹樹和其子樹之間的次序樹和其子樹之間的次序w 有序樹有序樹和和無(wú)序樹無(wú)序樹之間的區(qū)別在于:之間的區(qū)別在于: 子樹之間是否存在次序關(guān)系。子樹之
16、間是否存在次序關(guān)系。ACBGFEHIJDMKL 如果討論的是無(wú)序樹,則這兩棵樹是等同如果討論的是無(wú)序樹,則這兩棵樹是等同的,否則是不等同的。的,否則是不等同的。 此書一般討論無(wú)序樹此書一般討論無(wú)序樹 7. 森林:森林:n(n0)個(gè)互不相交的樹的集合稱為森)個(gè)互不相交的樹的集合稱為森林。森林的概念與樹的概念十分相近,因?yàn)橹灰褬涞牧?。森林的概念與樹的概念十分相近,因?yàn)橹灰褬涞母?jié)點(diǎn)刪去就成了森林。反之,只要給根節(jié)點(diǎn)刪去就成了森林。反之,只要給n棵獨(dú)立的樹加棵獨(dú)立的樹加上一個(gè)節(jié)點(diǎn),并把這上一個(gè)節(jié)點(diǎn),并把這n棵樹作為該節(jié)點(diǎn)的子樹,則森林棵樹作為該節(jié)點(diǎn)的子樹,則森林就變成了樹。就變成了樹。 任何一棵
17、非空樹是一個(gè)二元組任何一棵非空樹是一個(gè)二元組 Tree=(root,F) 其中:其中:root被稱為根結(jié)點(diǎn)被稱為根結(jié)點(diǎn) F被稱為子樹森林被稱為子樹森林注意與自然界中的樹和注意與自然界中的樹和森林的概念不同。森林的概念不同。概念示例w 結(jié)點(diǎn)結(jié)點(diǎn)w 結(jié)點(diǎn)的度結(jié)點(diǎn)的度(Degree)(Degree)w 葉子(葉子(Leaf)Leaf)或終端結(jié)點(diǎn)或終端結(jié)點(diǎn)w 分支結(jié)點(diǎn)或非終端結(jié)點(diǎn)分支結(jié)點(diǎn)或非終端結(jié)點(diǎn)w 樹的度樹的度w 層次層次(Level)(Level)w 樹的深度樹的深度(Depth)(Depth)w 孩子(孩子(child)child)w 雙親(雙親(Parent)Parent)w 兄弟兄弟(Si
18、bling)(Sibling)w 祖先祖先w 子孫子孫ACBGFEHIJDMKL樹的基本操作樹的基本操作w分為分為三大類:三大類: 查找查找 插入插入 刪除刪除查找操作查找操作w 分為特定的查找和按關(guān)系的查找分為特定的查找和按關(guān)系的查找 特定的查找特定的查找 Root(T); Value(T,cur_e); 按關(guān)系的查找按關(guān)系的查找 Parent(T, cur_e); LeftChild(T, cur_e); RightSibling(T, cur_e); 某些特性的判別某些特性的判別 TreeEmpty(T); TreeDepth(T); 特殊的操作特殊的操作 TraverseTree(T,
19、Visit( ); 查找樹中值為查找樹中值為cur_e的某個(gè)結(jié)點(diǎn)的某個(gè)結(jié)點(diǎn) 查找樹中值為查找樹中值為cur_e的的結(jié)點(diǎn)的最左邊的孩子結(jié)點(diǎn)的最左邊的孩子插入操作插入操作w InitTree(&T ); CreatTree(&t,definition); Assign(&T,cur_e,valus); InsertChild(&T,&p,i,c); 根據(jù)定義生成樹,如根據(jù)定義生成樹,如給定樹根和子樹森林給定樹根和子樹森林可以生成樹可以生成樹 改變樹上某改變樹上某個(gè)結(jié)點(diǎn)的值個(gè)結(jié)點(diǎn)的值 插入一棵子樹,如在樹插入一棵子樹,如在樹T中指針中指針p所指的位置插入一棵以
20、所指的位置插入一棵以c為根的子為根的子樹,并且作為第樹,并且作為第i棵子樹棵子樹刪除操作刪除操作w ClearTree(&T) DestroyTree(&T); DeleteChild(&T,&p,i); 刪除樹刪除樹T中某個(gè)中某個(gè)結(jié)點(diǎn)的某個(gè)子樹結(jié)點(diǎn)的某個(gè)子樹w一般討論的是一般討論的是有向樹(箭頭略去不畫):有向樹(箭頭略去不畫): 1) 有確定的根;有確定的根; 2) 樹根和子樹根之間為有向關(guān)系樹根和子樹根之間為有向關(guān)系;樹結(jié)構(gòu)和線性結(jié)構(gòu)的比較樹結(jié)構(gòu)和線性結(jié)構(gòu)的比較 線性結(jié)構(gòu)線性結(jié)構(gòu)樹結(jié)構(gòu)樹結(jié)構(gòu) 第一個(gè)數(shù)據(jù)元素第一個(gè)數(shù)據(jù)元素 (無(wú)前驅(qū))(無(wú)前驅(qū))根結(jié)點(diǎn)根結(jié)點(diǎn)
21、(無(wú)前驅(qū))(無(wú)前驅(qū))最后一個(gè)數(shù)據(jù)元素最后一個(gè)數(shù)據(jù)元素 (無(wú)后繼)(無(wú)后繼)多個(gè)葉子結(jié)點(diǎn)多個(gè)葉子結(jié)點(diǎn) (無(wú)后繼)(無(wú)后繼)其他數(shù)據(jù)元素其他數(shù)據(jù)元素 (一個(gè)前驅(qū),(一個(gè)前驅(qū), 一個(gè)后繼)一個(gè)后繼)樹中其他結(jié)點(diǎn)樹中其他結(jié)點(diǎn) (一個(gè)前驅(qū),(一個(gè)前驅(qū), 多個(gè)后繼)多個(gè)后繼)一對(duì)一一對(duì)一一對(duì)多一對(duì)多7.2 二叉樹二叉樹w7.2.1 二叉樹的概念二叉樹的概念w 二叉樹二叉樹(Binary Tree)(Binary Tree):或者是一棵空樹,或者是一棵空樹,或者是一棵由一個(gè)根結(jié)點(diǎn)和兩棵或者是一棵由一個(gè)根結(jié)點(diǎn)和兩棵互不相交互不相交的的左子樹左子樹和和右子樹右子樹所組成的非空樹,左子所組成的非空樹,左子樹和右子
22、樹又同樣都是二叉樹樹和右子樹又同樣都是二叉樹。w 特征特征:n每個(gè)結(jié)點(diǎn)最多只有兩棵子樹每個(gè)結(jié)點(diǎn)最多只有兩棵子樹n子樹有左右之分,其次序不能任意顛倒子樹有左右之分,其次序不能任意顛倒許多實(shí)際問題抽象出來(lái)的數(shù)據(jù)許多實(shí)際問題抽象出來(lái)的數(shù)據(jù)結(jié)構(gòu)往往是二叉樹的形式結(jié)構(gòu)往往是二叉樹的形式ABECDFGHK 根結(jié)點(diǎn)根結(jié)點(diǎn)A的左子樹的左子樹 根結(jié)點(diǎn)根結(jié)點(diǎn)A的右子樹的右子樹二叉樹的二叉樹的五種形態(tài)五種形態(tài)(a)(a)(b)(b)(c)(c)(d)(d)(e)(e)空樹空樹只有一個(gè)根結(jié)點(diǎn)的樹只有一個(gè)根結(jié)點(diǎn)的樹右子右子樹為空樹為空左子左子樹為空樹為空左右子樹均非空左右子樹均非空w 與有序樹不同,即使只有一棵子樹也要
23、區(qū)與有序樹不同,即使只有一棵子樹也要區(qū)分出是左子樹還是右子樹。分出是左子樹還是右子樹。有序樹有序樹右子樹為空右子樹為空左子樹為空左子樹為空 在一棵二叉樹中在一棵二叉樹中,如果如果所有分支節(jié)點(diǎn)都有左孩子節(jié)點(diǎn)和右孩所有分支節(jié)點(diǎn)都有左孩子節(jié)點(diǎn)和右孩子節(jié)點(diǎn),子節(jié)點(diǎn),并且并且葉節(jié)點(diǎn)都集中在二叉樹的最下一層,這樣的二叉葉節(jié)點(diǎn)都集中在二叉樹的最下一層,這樣的二叉樹稱為樹稱為滿二叉樹。滿二叉樹。下圖所示就是一棵滿二叉樹。可以對(duì)滿二叉樹的節(jié)點(diǎn)進(jìn)行下圖所示就是一棵滿二叉樹??梢詫?duì)滿二叉樹的節(jié)點(diǎn)進(jìn)行連續(xù)編號(hào),約定編號(hào)從樹根為連續(xù)編號(hào),約定編號(hào)從樹根為1開始,按照層數(shù)從小到大、同開始,按照層數(shù)從小到大、同一層從左到右
24、的次序進(jìn)行。圖中每個(gè)節(jié)點(diǎn)外邊的數(shù)字為對(duì)該節(jié)一層從左到右的次序進(jìn)行。圖中每個(gè)節(jié)點(diǎn)外邊的數(shù)字為對(duì)該節(jié)點(diǎn)的編號(hào)。點(diǎn)的編號(hào)。 A B C D E H I J K F G L M N O 1 2 3 4 5 6 7 8 9 10 15 11 12 13 14 滿二叉樹滿二叉樹 若二叉樹中最多若二叉樹中最多只有最下面兩層的節(jié)點(diǎn)的度數(shù)可以小于只有最下面兩層的節(jié)點(diǎn)的度數(shù)可以小于2,并且并且最下面一層的葉節(jié)點(diǎn)都依次排列在該層最左邊的位置上,最下面一層的葉節(jié)點(diǎn)都依次排列在該層最左邊的位置上,則這樣的二叉樹稱為則這樣的二叉樹稱為完全二叉樹。完全二叉樹。 如下圖所示為一棵完全二叉樹。同樣可以對(duì)完全二叉樹中如下圖所示為
25、一棵完全二叉樹。同樣可以對(duì)完全二叉樹中每個(gè)節(jié)點(diǎn)進(jìn)行連續(xù)編號(hào),編號(hào)的方法同滿二叉樹相同。圖中每每個(gè)節(jié)點(diǎn)進(jìn)行連續(xù)編號(hào),編號(hào)的方法同滿二叉樹相同。圖中每個(gè)節(jié)點(diǎn)外邊的數(shù)字為對(duì)該節(jié)點(diǎn)的編號(hào)。個(gè)節(jié)點(diǎn)外邊的數(shù)字為對(duì)該節(jié)點(diǎn)的編號(hào)。 A B C D E H I J K F G 1 2 3 4 5 6 7 8 9 10 11 完全二叉樹完全二叉樹 189101112452673完全二完全二叉樹叉樹二叉樹的抽象數(shù)據(jù)類型二叉樹的抽象數(shù)據(jù)類型ADT BinTree 數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象D:D是具有相同特性的數(shù)據(jù)元素的集合。是具有相同特性的數(shù)據(jù)元素的集合。 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系R: 若若D= ,則,則R= ,稱二叉樹為空二叉樹;
26、,稱二叉樹為空二叉樹; 若若D,則,則R=H,H是如下二元關(guān)系:是如下二元關(guān)系: (1)在)在D中存在唯一的稱為根的數(shù)據(jù)元素中存在唯一的稱為根的數(shù)據(jù)元素root,它在關(guān)系,它在關(guān)系H下無(wú)前驅(qū);下無(wú)前驅(qū); (2)若)若D-root,則存在則存在D-root=D1,Dr,且且D1 Dr; (3)若)若D1,則,則D1中存在唯一的元素中存在唯一的元素x1, H,且存在且存在D1上的關(guān)系上的關(guān)系 H1 H;若;若Dr,則則Dr中存在唯一的元素中存在唯一的元素xr, H, 且存在且存在Dr上上的關(guān)系的關(guān)系Hr H;H=, H1, Hr; (4)()(D1,H1)是一棵符合本定義的二叉樹,稱為根的左子樹,
27、)是一棵符合本定義的二叉樹,稱為根的左子樹, (Dr,Hr)是一棵符合本定義的二叉樹,稱為根的右子樹。)是一棵符合本定義的二叉樹,稱為根的右子樹。 二叉樹的抽象數(shù)據(jù)類型二叉樹的抽象數(shù)據(jù)類型 基本操作:基本操作: BinTreeInit (BT); BinTreeRoot(BT); BinTreeParent(BT,x); BinTreeLeftChild (BT,x); BinTreeRightChild (BT,x); BinTreeBulid(BT,LBT,RBT); BinTreeInsertLeft(BT,y,x); BinTreeInsertRight(BT,y,x); BinTre
28、eDeleteLeft(BT,x); BinTreeDeleteRight(BT,x); BinTreeClear(BT); BinTraverse(BT);ADT BinTree 主要操作也是主要操作也是三類:三類:查找查找插入插入刪除刪除7.2.2 二叉樹的性質(zhì)二叉樹的性質(zhì)1.1.一個(gè)非空二叉樹的第一個(gè)非空二叉樹的第i i層上至多有層上至多有2 2i-1i-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)(i i 1 1) 證明證明(用數(shù)學(xué)歸納法用數(shù)學(xué)歸納法): i = 1, 只有根結(jié)點(diǎn),只有根結(jié)點(diǎn), 2i-1 201,顯然成立,顯然成立 設(shè)設(shè)i = k時(shí)成立,最多有時(shí)成立,最多有2k-1 當(dāng)當(dāng)i= k+1時(shí),最多的結(jié)點(diǎn)個(gè)
29、數(shù):時(shí),最多的結(jié)點(diǎn)個(gè)數(shù): 2k-1 * 2 = 2k-1+1 = 2k = 2( k+1)-1因?yàn)槊總€(gè)結(jié)點(diǎn)的度最多因?yàn)槊總€(gè)結(jié)點(diǎn)的度最多為為2,所以乘以,所以乘以27.2.2 二叉樹的性質(zhì)二叉樹的性質(zhì)2.2.深度為深度為k k的二叉樹至多有的二叉樹至多有2 2k k-1-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)(k(k 1)1) 證明:由性質(zhì)證明:由性質(zhì)1 可知,只有每層的結(jié)點(diǎn)數(shù)達(dá)到可知,只有每層的結(jié)點(diǎn)數(shù)達(dá)到最大時(shí),其樹的結(jié)點(diǎn)數(shù)為最多。最大時(shí),其樹的結(jié)點(diǎn)數(shù)為最多。 二叉樹的結(jié)點(diǎn)個(gè)數(shù)最多為:二叉樹的結(jié)點(diǎn)個(gè)數(shù)最多為: 20 +21 +22 +2k-1 =1 + 2 + + 2k-1= 2k-1等比級(jí)數(shù)前等比級(jí)數(shù)前n項(xiàng)的求和公
30、式項(xiàng)的求和公式二叉樹的性質(zhì)二叉樹的性質(zhì)3.3.對(duì)任意一棵非空二叉樹對(duì)任意一棵非空二叉樹BTBT,如果其終端結(jié)點(diǎn)數(shù)為,如果其終端結(jié)點(diǎn)數(shù)為n n0 0,度,度為為2 2的結(jié)點(diǎn)數(shù)的結(jié)點(diǎn)數(shù)為為n n2 2,則,則n n0 0 = n = n2 2 +1; +1; 證明:證明: 設(shè)設(shè)n1為為BT中度為中度為1的結(jié)點(diǎn)數(shù),則總結(jié)點(diǎn)數(shù):的結(jié)點(diǎn)數(shù),則總結(jié)點(diǎn)數(shù):n = n0 + n1 + n2 另:除根結(jié)點(diǎn)外,所有結(jié)點(diǎn)都有且僅有一個(gè)雙親結(jié)點(diǎn),另:除根結(jié)點(diǎn)外,所有結(jié)點(diǎn)都有且僅有一個(gè)雙親結(jié)點(diǎn),也就是僅有一個(gè)分支進(jìn)入,若也就是僅有一個(gè)分支進(jìn)入,若B為分支數(shù),則為分支數(shù),則 n=B+1 由于這些分支是由度為由于這些分支是
31、由度為1或或2的結(jié)點(diǎn)射出的,所以又有:的結(jié)點(diǎn)射出的,所以又有: B=n1+2*n2 即:即: B=n1+2*n2 n-1; n= n1+2*n2 +1; 由式子由式子 和和 得到:得到: n0 + n1 + n2 n1+2*n2 +1; n n0 0 = n = n2 2 +1 +1填空題填空題w 如某二叉樹有如某二叉樹有20個(gè)葉子結(jié)點(diǎn),有個(gè)葉子結(jié)點(diǎn),有30個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)僅有一個(gè)孩子,則該二叉樹的總結(jié)點(diǎn)數(shù)為僅有一個(gè)孩子,則該二叉樹的總結(jié)點(diǎn)數(shù)為_。w 【南京理工大學(xué)【南京理工大學(xué) 2001 二、二、3(2分)分)】w答案為:答案為: 69 根據(jù)二叉樹性質(zhì)根據(jù)二叉樹性質(zhì)3滿二叉樹(特殊形態(tài)的二叉樹)
32、滿二叉樹(特殊形態(tài)的二叉樹)w 滿二叉樹(滿二叉樹(Full Binary Tree):深深度為度為k且有且有2k-1個(gè)結(jié)個(gè)結(jié)點(diǎn)的二叉樹。點(diǎn)的二叉樹。w 考慮到有序性,任一考慮到有序性,任一結(jié)點(diǎn)在樹中都有確切結(jié)點(diǎn)在樹中都有確切的位置,因此可以對(duì)的位置,因此可以對(duì)滿二叉樹進(jìn)行編號(hào)。滿二叉樹進(jìn)行編號(hào)。編號(hào)方式為:從上到編號(hào)方式為:從上到下,從左到右下,從左到右。189101112131415452673滿二叉樹滿二叉樹其特點(diǎn)是每一層上的結(jié)其特點(diǎn)是每一層上的結(jié)點(diǎn)樹都是最大結(jié)點(diǎn)數(shù)。點(diǎn)樹都是最大結(jié)點(diǎn)數(shù)。不存在度為不存在度為1的結(jié)點(diǎn)的結(jié)點(diǎn)完全二叉樹(特殊形態(tài)的二叉樹)完全二叉樹(特殊形態(tài)的二叉樹)w 完全
33、二叉樹完全二叉樹(Completed Binary Tree):深度為深度為k,有有n個(gè)結(jié)點(diǎn)的二叉樹,當(dāng)個(gè)結(jié)點(diǎn)的二叉樹,當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為深度為k的滿二叉樹編號(hào)的滿二叉樹編號(hào)從從1到到n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí),的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí),稱為完全二叉樹。稱為完全二叉樹。w 特征:特征:n葉子結(jié)點(diǎn)只可能在層次葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)最大的兩層上出現(xiàn)n任一結(jié)點(diǎn),若其右分支任一結(jié)點(diǎn),若其右分支下的子孫的最大層次為下的子孫的最大層次為l,則其左分支下的最大層則其左分支下的最大層次為次為l或或l+1.189101112452673完全二完全二叉樹叉樹滿二叉樹是完全二叉滿二叉
34、樹是完全二叉樹的樹的 一種特殊情況一種特殊情況完全二叉樹的性質(zhì)完全二叉樹的性質(zhì)1.1.具有具有n n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為:個(gè)結(jié)點(diǎn)的完全二叉樹的深度為: k = k = loglog2 2(n+1)(n+1) ( x 表示不小于表示不小于x的最小整數(shù),如的最小整數(shù),如 6.1 =7,即向上取,即向上取整整 ) 證明:設(shè)樹的深度為證明:設(shè)樹的深度為k,則由完全二叉樹的定義和性質(zhì),則由完全二叉樹的定義和性質(zhì) 2 可知:可知: 2k-1 1 n 2k 1 或:或: 2k-1 n+1 2k 取對(duì)數(shù)后:取對(duì)數(shù)后: k-1 log2(n+1) k 由于由于k是整數(shù),是整數(shù), k = log2(n+1)
35、 完全二叉樹的性質(zhì)完全二叉樹的性質(zhì)或有的教材:或有的教材:1.1.具有具有n n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為:個(gè)結(jié)點(diǎn)的完全二叉樹的深度為: k = k = loglog2 2n n +1 +1( x 表示不大于表示不大于x的最大整數(shù),如的最大整數(shù),如 6.9 =6,即向下取整,即向下取整 ) 證明:設(shè)樹的深度為證明:設(shè)樹的深度為k,則由完全二叉樹的定義和性質(zhì),則由完全二叉樹的定義和性質(zhì) 2 可知:可知: 2k-1 1 n 2k 1 或:或: 2k-1 n 2k 取對(duì)數(shù)后:取對(duì)數(shù)后: k-1 log2n 0時(shí)與上頁(yè)的描述等效,當(dāng)時(shí)與上頁(yè)的描述等效,當(dāng)n=0時(shí)此定義就沒有意義了。)時(shí)此定義就沒有意義
36、了。)填空題填空題w 一個(gè)有一個(gè)有2001個(gè)結(jié)點(diǎn)的完全二叉樹的高度為個(gè)結(jié)點(diǎn)的完全二叉樹的高度為_。w 【南京理工大學(xué)【南京理工大學(xué) 1997 三、三、2(1分)分)】 答案為:答案為:11k = log2(n+1) log22002 11 或:或: k = log2n + 1= log22001 + 1=10+1=11完全二叉樹的性質(zhì)完全二叉樹的性質(zhì)2.2.如果將一棵有如果將一棵有n n個(gè)結(jié)點(diǎn)的完全二叉樹自頂向下,個(gè)結(jié)點(diǎn)的完全二叉樹自頂向下,同一層自左向右連續(xù)給結(jié)點(diǎn)編號(hào)同一層自左向右連續(xù)給結(jié)點(diǎn)編號(hào)1 1、2 2、3 3n,n,則對(duì)任一結(jié)點(diǎn)則對(duì)任一結(jié)點(diǎn)i i(1 1 i i n n)有:)有:
37、(a)如果)如果i=1,此結(jié)點(diǎn)為根結(jié)點(diǎn),無(wú)雙親;若此結(jié)點(diǎn)為根結(jié)點(diǎn),無(wú)雙親;若i1,則則其雙親結(jié)點(diǎn)是其雙親結(jié)點(diǎn)是 i/2 。 (b)如果)如果2in,則結(jié)點(diǎn)則結(jié)點(diǎn)i無(wú)左孩子,無(wú)左孩子,i為葉子結(jié)為葉子結(jié)點(diǎn)點(diǎn),否則否則其左孩子是結(jié)點(diǎn)其左孩子是結(jié)點(diǎn)2i。 (c)如果)如果2i+1n,則結(jié)點(diǎn),則結(jié)點(diǎn)i無(wú)右孩子,否則無(wú)右孩子,否則其其右孩子是結(jié)點(diǎn)右孩子是結(jié)點(diǎn)2i+1。 完全二叉樹示意圖完全二叉樹示意圖2i2i2i+12i+1i i2i+22i+22i+32i+3i+1i+1 i/2i/2 j 層層j+1層層結(jié)點(diǎn)結(jié)點(diǎn)i i和和i i1 1在同一層上在同一層上完全二叉樹示意圖完全二叉樹示意圖2i+22i+2
38、2i+32i+3i+1i+12i2i2i+12i+1i i.2i2i2i+12i+1i i2i+22i+22i+32i+3i+1i+1LCHILD(i)LCHILD(i+1)RCHILD(i)RCHILD(i+1) i/2i/2 結(jié)點(diǎn)結(jié)點(diǎn)i i和和i+1i+1不在同一層上不在同一層上滿二叉樹是完全二叉樹的一滿二叉樹是完全二叉樹的一種特殊形式種特殊形式 性質(zhì)性質(zhì)4 對(duì)完全二叉樹中編號(hào)為對(duì)完全二叉樹中編號(hào)為i的節(jié)點(diǎn)(的節(jié)點(diǎn)(1in,n1,n為節(jié)點(diǎn)數(shù))有:為節(jié)點(diǎn)數(shù))有: (1)若)若i n/2 ,即即2in,則編號(hào)為,則編號(hào)為i的節(jié)點(diǎn)為分支節(jié)點(diǎn),的節(jié)點(diǎn)為分支節(jié)點(diǎn),否則為葉子節(jié)點(diǎn)。否則為葉子節(jié)點(diǎn)。 (
39、2)若)若n為奇數(shù),則每個(gè)分支節(jié)點(diǎn)都既有左孩子節(jié)點(diǎn),為奇數(shù),則每個(gè)分支節(jié)點(diǎn)都既有左孩子節(jié)點(diǎn),也有右孩子節(jié)點(diǎn);若也有右孩子節(jié)點(diǎn);若n為偶數(shù),則編號(hào)最大的分支節(jié)點(diǎn)只有為偶數(shù),則編號(hào)最大的分支節(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)。i/2i2i2i+1教材教材P.163.與上述完全二叉樹性質(zhì)與上述完全二叉樹性質(zhì)2的的不同表述不同表述 (3)若編號(hào)為)若編號(hào)為i的節(jié)點(diǎn)有左孩子節(jié)點(diǎn),則左孩子節(jié)點(diǎn)的編的節(jié)點(diǎn)有左孩子節(jié)點(diǎn),則左孩子節(jié)點(diǎn)的編號(hào)為號(hào)為2i;若編號(hào)為;若編號(hào)為i的節(jié)點(diǎn)有右孩子節(jié)點(diǎn),則右孩子節(jié)點(diǎn)的編的節(jié)點(diǎn)有右孩子
40、節(jié)點(diǎn),則右孩子節(jié)點(diǎn)的編號(hào)為號(hào)為(2i+1)。 (4)除樹根節(jié)點(diǎn)外)除樹根節(jié)點(diǎn)外,若一個(gè)節(jié)點(diǎn)的編號(hào)為若一個(gè)節(jié)點(diǎn)的編號(hào)為i,則它的雙親,則它的雙親節(jié)點(diǎn)的編號(hào)為節(jié)點(diǎn)的編號(hào)為 i/2 ,也就是說(shuō),當(dāng),也就是說(shuō),當(dāng)i為偶數(shù)時(shí),其雙親節(jié)點(diǎn)的為偶數(shù)時(shí),其雙親節(jié)點(diǎn)的編號(hào)為編號(hào)為i/2,它是雙親節(jié)點(diǎn)的左孩子節(jié)點(diǎn),當(dāng)它是雙親節(jié)點(diǎn)的左孩子節(jié)點(diǎn),當(dāng)i為奇數(shù)時(shí),其雙為奇數(shù)時(shí),其雙親節(jié)點(diǎn)的編號(hào)為親節(jié)點(diǎn)的編號(hào)為(i-1)/2,它是雙親節(jié)點(diǎn)的右孩子節(jié)點(diǎn)。,它是雙親節(jié)點(diǎn)的右孩子節(jié)點(diǎn)。練習(xí)題練習(xí)題w 在下述結(jié)論中,正確的是(在下述結(jié)論中,正確的是( )w 【南京理工大學(xué)【南京理工大學(xué) 1999 1999 一、一、4 4 (1 1
41、分)分)】w 只有一個(gè)結(jié)點(diǎn)的二叉樹的度為只有一個(gè)結(jié)點(diǎn)的二叉樹的度為0; 0; w 二叉樹的度為二叉樹的度為2 2; w 二叉樹的左右子樹可任意交換二叉樹的左右子樹可任意交換; ;w 深度為深度為K K的完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)小于或等于深度相的完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)小于或等于深度相同的滿二叉樹。同的滿二叉樹。 w A A w B B w C C w D Dw 答案為:答案為:w D練習(xí)題練習(xí)題w 若一棵二叉樹具有若一棵二叉樹具有1010個(gè)度為個(gè)度為2 2的結(jié)點(diǎn),的結(jié)點(diǎn),5 5個(gè)個(gè)度為度為1 1的結(jié)點(diǎn),則度為的結(jié)點(diǎn),則度為0 0的結(jié)點(diǎn)個(gè)數(shù)是(的結(jié)點(diǎn)個(gè)數(shù)是( )w A A9 9 w B B11 11 w
42、 C C15 15 w D D不確定不確定 w 【北京工商大學(xué)【北京工商大學(xué)20012001一一.7(3.7(3分分) )】w 答案為:答案為: B 二叉樹性質(zhì)二叉樹性質(zhì) 3練習(xí)題練習(xí)題w 具有具有1010個(gè)葉結(jié)點(diǎn)的二叉樹中有(個(gè)葉結(jié)點(diǎn)的二叉樹中有( )個(gè)度)個(gè)度為為2 2的結(jié)點(diǎn),的結(jié)點(diǎn),w 【北京航空航天大學(xué)【北京航空航天大學(xué)2000 2000 一、一、5 5(2 2分分) )】w A A8 8 w B B9 9 w C C10 10 w D Dllllw 答案為:答案為: B二叉樹性質(zhì)二叉樹性質(zhì) 3練習(xí)題練習(xí)題w 有關(guān)二叉樹下列說(shuō)法正確的是(有關(guān)二叉樹下列說(shuō)法正確的是( )w 【南京理工大
43、學(xué)【南京理工大學(xué) 2000 2000 一、一、11 11 (1.51.5分)分)】w A A二叉樹的度為二叉樹的度為2 2 w B B一棵二叉樹的度可以小于一棵二叉樹的度可以小于2 2 w C C二叉樹中至少有一個(gè)結(jié)點(diǎn)的度為二叉樹中至少有一個(gè)結(jié)點(diǎn)的度為2 2w D D二叉樹中任何一個(gè)結(jié)點(diǎn)的度都為二叉樹中任何一個(gè)結(jié)點(diǎn)的度都為2 2w答案為:答案為: B練習(xí)題練習(xí)題w 二叉樹的第二叉樹的第I層上最多含有結(jié)點(diǎn)數(shù)為(層上最多含有結(jié)點(diǎn)數(shù)為( )w 【中山大學(xué)【中山大學(xué)1998二、二、7 (2分)分)】w 【北京理工大學(xué)【北京理工大學(xué) 2001 六、六、5(2分)分)】w A 2I w B 2I-1-1
44、w C 2I-1 w D 2I -1w 答案為:答案為: C 二叉樹性質(zhì)二叉樹性質(zhì)1練習(xí)題練習(xí)題w 一個(gè)具有一個(gè)具有1025個(gè)結(jié)點(diǎn)的二叉樹的高個(gè)結(jié)點(diǎn)的二叉樹的高h(yuǎn)為(為( )w 【南京理工大學(xué)【南京理工大學(xué) 1999 一、一、19 (2分)分)】w A11 w B10 w C11至至1025之間之間 w D10至至1024之間之間w答案為:答案為: C 注意可能是單支樹注意可能是單支樹練習(xí)題練習(xí)題w 將有關(guān)二叉樹的概念推廣到三叉樹,則一棵有將有關(guān)二叉樹的概念推廣到三叉樹,則一棵有244個(gè)結(jié)點(diǎn)的完全三叉樹的高度()個(gè)結(jié)點(diǎn)的完全三叉樹的高度()w A4 w B5 w C6 w D7 w 答案為:答
45、案為:w C w 根據(jù)完全二叉樹性質(zhì)根據(jù)完全二叉樹性質(zhì)1: k = log3245 6w 或或根據(jù)完全二叉樹性質(zhì)根據(jù)完全二叉樹性質(zhì)1: k = log3244 +1=5+1=6【南京理工大學(xué)【南京理工大學(xué)2000一、一、5 1.5分)分)】判斷題判斷題w 完全二叉樹一定存在度為完全二叉樹一定存在度為1的結(jié)點(diǎn)。的結(jié)點(diǎn)。w 【青島大學(xué)【青島大學(xué) 2002 一、一、4 (1分)分)】 w答案為:答案為: 錯(cuò)錯(cuò)判斷題判斷題w 深度為深度為K的二叉樹中結(jié)點(diǎn)總數(shù)的二叉樹中結(jié)點(diǎn)總數(shù)2k-1。w 【南京航空航天大學(xué)【南京航空航天大學(xué) 1995 五、五、1 (1分)分)】 w答案為:答案為: 對(duì)對(duì)判斷題判斷題w
46、 完全二叉樹中,若一個(gè)結(jié)點(diǎn)沒有左孩子,完全二叉樹中,若一個(gè)結(jié)點(diǎn)沒有左孩子,則它必是樹葉。則它必是樹葉。w 【東南大學(xué)【東南大學(xué) 2001一、一、1-8(1分)分)】w 【中科院軟件所【中科院軟件所1997一、一、2(1分)分)】w 【山東大學(xué)【山東大學(xué)2001一、一、4 (1分分)】w答案為:答案為: 對(duì)對(duì)判斷題判斷題w 下面二叉樹的定義只有一個(gè)是正確的,請(qǐng)?jiān)谡_的地方畫下面二叉樹的定義只有一個(gè)是正確的,請(qǐng)?jiān)谡_的地方畫“”。w (1)它是由一個(gè)根和兩株互不相交的、稱為左子樹和右子樹的)它是由一個(gè)根和兩株互不相交的、稱為左子樹和右子樹的二叉樹組成。二叉樹組成。w (2)()(a)在一株二叉樹的
47、級(jí))在一株二叉樹的級(jí)i上,最大結(jié)點(diǎn)數(shù)是上,最大結(jié)點(diǎn)數(shù)是2i-1(i1) (b)在一棵深度為)在一棵深度為k的二叉樹中,最大結(jié)點(diǎn)數(shù)是的二叉樹中,最大結(jié)點(diǎn)數(shù)是2k-1+1 (k1)。)。w (3)二叉樹是結(jié)點(diǎn)的集合,滿足如下條件:)二叉樹是結(jié)點(diǎn)的集合,滿足如下條件: (a)它或者是空集;)它或者是空集; (b)或者是由一個(gè)根和兩個(gè)互不相交的、稱為左子樹和右)或者是由一個(gè)根和兩個(gè)互不相交的、稱為左子樹和右子樹的二叉樹組成。子樹的二叉樹組成。w 【中科院自動(dòng)化所【中科院自動(dòng)化所1995一、一、2(6分)分)】w 答案為:答案為: (3)填空題填空題w 深度為深度為k的完全二叉樹至少有的完全二叉樹至少有
48、_(1)_個(gè)個(gè)結(jié)點(diǎn),至多有結(jié)點(diǎn),至多有_(2)_個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。w 【廈門大學(xué)【廈門大學(xué) 2001 一、一、4 (5分)分)】w 【南京理工大學(xué)【南京理工大學(xué) 1999 二、二、5 (4分)分)】w答案為:答案為: (1) 2k-1 (2) 2k-1填空題填空題w 深度為深度為H 的完全二叉樹至少有的完全二叉樹至少有_(1)_個(gè)結(jié)點(diǎn);個(gè)結(jié)點(diǎn);至多有至多有_(2)_個(gè)結(jié)點(diǎn);個(gè)結(jié)點(diǎn);H和結(jié)點(diǎn)總數(shù)和結(jié)點(diǎn)總數(shù)N之間之間的關(guān)系是的關(guān)系是 (3)_。w 【中科院計(jì)算所【中科院計(jì)算所1998 一、一、3(3分)分)1999 二、二、4(3分)分)】w 【中國(guó)科技大學(xué)【中國(guó)科技大學(xué) 1998 一、一、3(4分
49、)分)】答案為:答案為: (1)2H-1 (2)2H-1 (3) H = log2(N+1) 或或H = log2N +1填空題填空題w 含含4個(gè)度為個(gè)度為2的結(jié)點(diǎn)和的結(jié)點(diǎn)和5個(gè)葉子結(jié)點(diǎn)的二叉?zhèn)€葉子結(jié)點(diǎn)的二叉樹,可有樹,可有_個(gè)度為個(gè)度為1的結(jié)點(diǎn)。的結(jié)點(diǎn)。w 【北京工業(yè)大學(xué)【北京工業(yè)大學(xué) 2001 一、一、6 (2分分)】w答案為:答案為: 0 至多個(gè)。至多個(gè)。 任意二叉樹,度為任意二叉樹,度為1的結(jié)點(diǎn)個(gè)數(shù)的結(jié)點(diǎn)個(gè)數(shù)沒有限制。只有完全二叉樹,度為沒有限制。只有完全二叉樹,度為1的結(jié)點(diǎn)個(gè)數(shù)才至多為的結(jié)點(diǎn)個(gè)數(shù)才至多為1選擇題選擇題w 一棵完全二叉樹上有一棵完全二叉樹上有1001個(gè)結(jié)點(diǎn),其中葉子結(jié)點(diǎn)
50、的個(gè)數(shù)個(gè)結(jié)點(diǎn),其中葉子結(jié)點(diǎn)的個(gè)數(shù)是(是( )w 【西安交通大學(xué)【西安交通大學(xué) 1996 三、三、2 (3分分)】w A 250 w B 500 w C254 w D505 w E以上答案都不對(duì)以上答案都不對(duì)w 答案為:答案為: Ew 由二叉樹的結(jié)點(diǎn)公式:由二叉樹的結(jié)點(diǎn)公式:n=n0+n1+n2=n0+n1+(n0-1)=2n0+n1-1,因?yàn)橐驗(yàn)閚1001,所以,所以10022n0n1,在完全二叉樹中,在完全二叉樹中,n1只能只能取取1或或0,在本題中只能取,在本題中只能取0(否則就是小數(shù)了),所以(否則就是小數(shù)了),所以n0501補(bǔ)充作業(yè)補(bǔ)充作業(yè)w 7.1 設(shè)樹設(shè)樹T的度為的度為4,其中度為
51、,其中度為1,2,3和和4的結(jié)點(diǎn)個(gè)數(shù)的結(jié)點(diǎn)個(gè)數(shù)分別為分別為4,2,1,1,求樹,求樹T中的葉子數(shù)。中的葉子數(shù)。w 7.2 一棵完全二叉樹上有一棵完全二叉樹上有1001個(gè)結(jié)點(diǎn),求葉子結(jié)點(diǎn)的個(gè)結(jié)點(diǎn),求葉子結(jié)點(diǎn)的個(gè)數(shù)個(gè)數(shù) 。w 7.3 一棵一棵124個(gè)葉結(jié)點(diǎn)的完全二叉樹,最多有多少個(gè)個(gè)葉結(jié)點(diǎn)的完全二叉樹,最多有多少個(gè)結(jié)點(diǎn)。結(jié)點(diǎn)。w 7.4 一棵完全二叉樹有一棵完全二叉樹有500個(gè)結(jié)點(diǎn),請(qǐng)問該完全二叉?zhèn)€結(jié)點(diǎn),請(qǐng)問該完全二叉樹有多少個(gè)葉子結(jié)點(diǎn)?有多少個(gè)度為樹有多少個(gè)葉子結(jié)點(diǎn)?有多少個(gè)度為1的結(jié)點(diǎn)?有多的結(jié)點(diǎn)?有多少個(gè)度為少個(gè)度為2的結(jié)點(diǎn)?如果完全二叉樹有的結(jié)點(diǎn)?如果完全二叉樹有501個(gè)結(jié)點(diǎn),個(gè)結(jié)點(diǎn),結(jié)果
52、如何?請(qǐng)寫出推導(dǎo)過程。結(jié)果如何?請(qǐng)寫出推導(dǎo)過程。 補(bǔ)充作業(yè)補(bǔ)充作業(yè)w 7.5 某二叉樹有某二叉樹有20個(gè)葉子結(jié)點(diǎn),有個(gè)葉子結(jié)點(diǎn),有30個(gè)結(jié)點(diǎn)僅個(gè)結(jié)點(diǎn)僅有一個(gè)孩子,則該二叉樹的總結(jié)點(diǎn)數(shù)是多少。有一個(gè)孩子,則該二叉樹的總結(jié)點(diǎn)數(shù)是多少。 w 7.6 一棵二叉樹高度為一棵二叉樹高度為h,所有結(jié)點(diǎn)的度或?yàn)?,所有結(jié)點(diǎn)的度或?yàn)?,或?yàn)榛驗(yàn)?,則這棵二叉樹最少有多少結(jié)點(diǎn)。,則這棵二叉樹最少有多少結(jié)點(diǎn)。 w 7.7 將有關(guān)二叉樹的概念推廣到三叉樹,則一將有關(guān)二叉樹的概念推廣到三叉樹,則一棵有棵有244個(gè)結(jié)點(diǎn)的完全三叉樹的高度是多少。個(gè)結(jié)點(diǎn)的完全三叉樹的高度是多少。 7.2.3 二叉樹的存二叉樹的存儲(chǔ)儲(chǔ)結(jié)構(gòu)結(jié)構(gòu)w
53、順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)w鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)二叉樹的順序存儲(chǔ)結(jié)構(gòu)二叉樹的順序存儲(chǔ)結(jié)構(gòu) 二叉樹的順序存儲(chǔ)結(jié)構(gòu)中節(jié)點(diǎn)的存放次序是:對(duì)該二叉樹的順序存儲(chǔ)結(jié)構(gòu)中節(jié)點(diǎn)的存放次序是:對(duì)該樹中每個(gè)節(jié)點(diǎn)進(jìn)行編號(hào),其編號(hào)從小到大的順序就是節(jié)點(diǎn)樹中每個(gè)節(jié)點(diǎn)進(jìn)行編號(hào),其編號(hào)從小到大的順序就是節(jié)點(diǎn)存放在連續(xù)存儲(chǔ)單元的先后次序。存放在連續(xù)存儲(chǔ)單元的先后次序。 若把二叉樹存儲(chǔ)到一維數(shù)組中若把二叉樹存儲(chǔ)到一維數(shù)組中,則該編號(hào)就是下標(biāo)值則該編號(hào)就是下標(biāo)值加加1(注意(注意C/C+語(yǔ)言中數(shù)組的起始下標(biāo)為語(yǔ)言中數(shù)組的起始下標(biāo)為0)。)。樹中各節(jié)樹中各節(jié)點(diǎn)的編號(hào)與等高度的完全二叉樹中對(duì)應(yīng)位置上節(jié)點(diǎn)的編號(hào)點(diǎn)的編號(hào)與等高度的完全
54、二叉樹中對(duì)應(yīng)位置上節(jié)點(diǎn)的編號(hào)相同。相同。 利用二叉樹的性質(zhì)利用二叉樹的性質(zhì)4。 A B C D E H I J K F G 1 2 3 4 5 6 7 8 9 10 11 完全二叉樹完全二叉樹 ABCDEFGHIJK123456789101112131415順序存儲(chǔ)結(jié)構(gòu)(不用下標(biāo)為順序存儲(chǔ)結(jié)構(gòu)(不用下標(biāo)為0的元素)的元素)ABCDEF A B D # C # E # # # # # # F 1 2 3 4 5 6 7 8 9 10 11 12 13 142511437一般的二叉樹先用空節(jié)點(diǎn)一般的二叉樹先用空節(jié)點(diǎn)補(bǔ)全成為完全二叉樹,然補(bǔ)全成為完全二叉樹,然后對(duì)節(jié)點(diǎn)編號(hào)后對(duì)節(jié)點(diǎn)編號(hào)typedef
55、ElemType SqBTreeMaxSize;SqBTree bt=ABD#C#E#F;順序存儲(chǔ)結(jié)構(gòu)舉例123456789101 18 89 910104 45 52 26 67 73 3完全二完全二叉樹叉樹順序存儲(chǔ)結(jié)構(gòu)舉例ABC非完全二非完全二叉樹叉樹XABCA B C 僅適用于完全二叉樹僅適用于完全二叉樹二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)1. 二叉鏈表二叉鏈表 3. 雙親鏈表雙親鏈表2. 三叉鏈表三叉鏈表 4. 線索鏈表線索鏈表二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)w 二叉鏈表二叉鏈表w 三叉鏈表三叉鏈表lchilddatarchilddatalchild rchildlchil
56、ddatarchildparentdatalchild rchildparent二叉樹及其鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu):二叉鏈表二叉樹及其鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu):二叉鏈表 ABCDEGFABDGCEFb鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)示例ACFEDB二叉鏈表二叉鏈表三叉鏈表三叉鏈表ADBCEFbtABCDEFbtlchilddatarchildlchilddatarchildparent二叉鏈表的二叉鏈表的C表示表示 二叉樹的二叉鏈表存儲(chǔ)表示二叉樹的二叉鏈表存儲(chǔ)表示typedef struct BinNode ElemType data; struct BinNode * *lchild, * *rchild; 左右孩子指針左右孩子指針
57、BinTNode,*BinTree;二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 在二叉樹的鏈接存儲(chǔ)中,節(jié)點(diǎn)的結(jié)構(gòu)如下在二叉樹的鏈接存儲(chǔ)中,節(jié)點(diǎn)的結(jié)構(gòu)如下: typedef struct node ElemType data; struct node *lchild,*rchild; BTNode; 其中其中,data表示值域表示值域,用于存儲(chǔ)對(duì)應(yīng)的數(shù)據(jù)元素,用于存儲(chǔ)對(duì)應(yīng)的數(shù)據(jù)元素,lchild和和rchild分別表示左指針域和右指針域,用于分別存儲(chǔ)左孩子節(jié)分別表示左指針域和右指針域,用于分別存儲(chǔ)左孩子節(jié)點(diǎn)和右孩子節(jié)點(diǎn)(即左、右子樹的根節(jié)點(diǎn))的存儲(chǔ)位置。點(diǎn)和右孩子節(jié)點(diǎn)(即左、右子樹的根節(jié)點(diǎn))的存儲(chǔ)
58、位置。教材教材P.168.三叉鏈表的三叉鏈表的C表示表示 二叉樹的三叉鏈表存儲(chǔ)表示二叉樹的三叉鏈表存儲(chǔ)表示typedef struct TriNode ElemType data; struct TriNode * *lchild, * *rchild; 左右孩子指針左右孩子指針 struct TriNode * *parent;/雙親指針雙親指針 TriTNode,*TriTree;二叉樹的雙親鏈表表示二叉樹的雙親鏈表表示Typedef struct BPTNode TElemType data; int *parent; /指向雙親的指針指向雙親的指針 char LRflag;/左、右孩子
59、標(biāo)志左、右孩子標(biāo)志 BPTNodeTypedef struct BPTree BPTNode nodesMAX_TREE_SIZE; int num_node; /結(jié)點(diǎn)數(shù)目結(jié)點(diǎn)數(shù)目 int root; /根結(jié)點(diǎn)的位置根結(jié)點(diǎn)的位置 BPTree;ABDC A-1L或或R B 0L C 1R D 0R 0 1 2 3root=0num_node=47.2.4 7.2.4 二叉樹的二叉樹的遍歷遍歷 二叉樹的遍歷是指按照一定次序二叉樹的遍歷是指按照一定次序訪問訪問樹中所樹中所有節(jié)點(diǎn),并且每個(gè)節(jié)點(diǎn)僅被訪問一次的過程。有節(jié)點(diǎn),并且每個(gè)節(jié)點(diǎn)僅被訪問一次的過程。它是最基本的運(yùn)算它是最基本的運(yùn)算,是二叉樹中所有
60、其他運(yùn)是二叉樹中所有其他運(yùn)算的基礎(chǔ)。算的基礎(chǔ)。 “訪問訪問”的含義可以很廣,如:輸出結(jié)點(diǎn)的含義可以很廣,如:輸出結(jié)點(diǎn)的信息等。的信息等。 “ “遍歷遍歷”是任何類型都有的操是任何類型都有的操作。對(duì)線性結(jié)構(gòu)而言,只有一條搜作。對(duì)線性結(jié)構(gòu)而言,只有一條搜索路徑(因?yàn)槊總€(gè)結(jié)點(diǎn)均只有一個(gè)索路徑(因?yàn)槊總€(gè)結(jié)點(diǎn)均只有一個(gè)后繼),故不需要另加討論。而二后繼),故不需要另加討論。而二叉樹是非線性結(jié)構(gòu),每個(gè)結(jié)點(diǎn)有兩叉樹是非線性結(jié)構(gòu),每個(gè)結(jié)點(diǎn)有兩個(gè)后繼,則存在如何遍歷即按什么個(gè)后繼,則存在如何遍歷即按什么樣的搜索路徑遍歷的問題。樣的搜索路徑遍歷的問題。對(duì)對(duì)“二叉樹二叉樹”而言,可以有而言,可以有三條三條搜索路搜索路徑:徑:1. 先上后下的按層次遍歷;先上后下的按層次遍歷;2.
溫馨提示
- 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ù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 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ì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 教育類讀書分享
- 2025年計(jì)算機(jī)服務(wù)項(xiàng)目規(guī)劃申請(qǐng)報(bào)告模板
- 2025年蚌埠淮上區(qū)區(qū)屬國(guó)有企業(yè)招聘考試筆試試題(含答案)
- 【錦州】2025年遼寧錦州義縣事業(yè)單位面向社會(huì)公開招聘工作人員15人筆試歷年典型考題及考點(diǎn)剖析附帶答案詳解
- 文庫(kù)發(fā)布:中醫(yī)護(hù)理
- 書包勞動(dòng)與技術(shù)課件
- 整體護(hù)理教程課件教學(xué)
- 【課件】角的平分線+第1課時(shí)+++課件-2025-2026學(xué)年+人教版2024八年級(jí)數(shù)學(xué)上冊(cè)
- 魏姍姍四季之美教學(xué)課件
- 教育課件背景圖
- 與工商部門核對(duì)臺(tái)帳表格模板
- DB11T 593-2016高速公路清掃保潔質(zhì)量與作業(yè)要求
- 嘟嘟少兒英語(yǔ)beep演示簡(jiǎn)化版
- GB/T 699-2015優(yōu)質(zhì)碳素結(jié)構(gòu)鋼
- GB/T 19096-2003技術(shù)制圖圖樣畫法未定義形狀邊的術(shù)語(yǔ)和注法
- GB/T 13808-1992銅及銅合金擠制棒
- 項(xiàng)目安全體系圖
- 中央財(cái)政科技計(jì)劃的項(xiàng)目結(jié)題審計(jì)指引講解文課件
- 職業(yè)暴露(銳器傷)應(yīng)急預(yù)案演練腳本
- 首屆全國(guó)報(bào)刊編校技能大賽決賽試卷(一)及答案
- 材料出入庫(kù)表格范本
評(píng)論
0/150
提交評(píng)論