第7章 樹(shù)形結(jié)構(gòu)_第1頁(yè)
第7章 樹(shù)形結(jié)構(gòu)_第2頁(yè)
第7章 樹(shù)形結(jié)構(gòu)_第3頁(yè)
第7章 樹(shù)形結(jié)構(gòu)_第4頁(yè)
第7章 樹(shù)形結(jié)構(gòu)_第5頁(yè)
已閱讀5頁(yè),還剩89頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

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

文檔簡(jiǎn)介

第七章樹(shù)和二叉樹(shù)7.1-2 樹(shù)和二叉樹(shù)的概念與性質(zhì)7.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)7.4 二叉樹(shù)的操作算法7.6-7 線(xiàn)索二叉樹(shù)的操作算法樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換7.8 樹(shù)的應(yīng)用---Huffman編碼決策分析小王是一家著名高爾夫俱樂(lè)部的經(jīng)理。但是他被雇員數(shù)量問(wèn)題搞得心情十分不好。某些天好像所有人都來(lái)玩高爾夫,以至于所有員工都忙的團(tuán)團(tuán)轉(zhuǎn)還是應(yīng)付不過(guò)來(lái),而有些天不知道什么原因卻一個(gè)人也不來(lái),俱樂(lè)部為雇員數(shù)量浪費(fèi)了不少資金。小王的目的是通過(guò)下周天氣預(yù)報(bào)尋找什么時(shí)候人們會(huì)打高爾夫,以適時(shí)調(diào)整雇員數(shù)量。因此首先他必須了解人們決定是否打球的原因。在2周時(shí)間內(nèi)我們得到以下記錄:

天氣狀況(sun)有晴,云和雨;氣溫用華氏溫度表示;相對(duì)濕度用百分比;還有有無(wú)風(fēng)。當(dāng)然還有顧客是不是在這些日子光顧俱樂(lè)部。最終他得到了14行5列的數(shù)據(jù)表格:樹(shù)結(jié)構(gòu)和線(xiàn)性結(jié)構(gòu)的比較線(xiàn)性結(jié)構(gòu)樹(shù)結(jié)構(gòu)第一個(gè)數(shù)據(jù)元素根結(jié)點(diǎn)(只有一個(gè))無(wú)前驅(qū)無(wú)雙親最后一個(gè)數(shù)據(jù)元素葉子結(jié)點(diǎn)(可以有多個(gè))無(wú)后繼無(wú)孩子其它數(shù)據(jù)元素其它結(jié)點(diǎn)一個(gè)前驅(qū),一個(gè)后繼一個(gè)雙親,多個(gè)孩子一對(duì)一一對(duì)多樹(shù)的邏輯結(jié)構(gòu)7.1樹(shù)的基本概念

7.1.1樹(shù)的定義

7.1.3樹(shù)的基本術(shù)語(yǔ)7.1.2樹(shù)的表示7.1.1樹(shù)的定義:核心關(guān)系:層次關(guān)系。

樹(shù):n(n≥0)個(gè)結(jié)點(diǎn)的有限集合。當(dāng)n=0時(shí),稱(chēng)為空樹(shù);任意一棵非空樹(shù)滿(mǎn)足以下條件:⑴

有且僅有一個(gè)特定的稱(chēng)為根的結(jié)點(diǎn);⑵

當(dāng)n>1時(shí),除根結(jié)點(diǎn)之外的其余結(jié)點(diǎn)被分成m(m>0)個(gè)互不相交的有限集合T1,T2,…,Tm,其中每個(gè)集合又是一棵樹(shù),并稱(chēng)為這個(gè)根結(jié)點(diǎn)的子樹(shù)。1.1通俗定義樹(shù)形表示法廣義表表示法a(b(e,f,g),c(h),d(i,j))樹(shù)是n(n>0)個(gè)結(jié)點(diǎn)的有限集,在任意一棵樹(shù)中:1有且只有一個(gè)特定的根(root)結(jié)點(diǎn);2當(dāng)n>1時(shí),其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限子集T1,T2...Tm,每個(gè)子集是一棵樹(shù),稱(chēng)為子樹(shù)。判斷以下是否為樹(shù)型結(jié)構(gòu)7.1.3樹(shù)的基本術(shù)語(yǔ)

1.樹(shù)的結(jié)點(diǎn):包含一個(gè)數(shù)據(jù)元素和指向其子樹(shù)的所有分支。

2.結(jié)點(diǎn)的度:一個(gè)結(jié)點(diǎn)擁有的子樹(shù)的個(gè)數(shù)。

A

C

G

J

B

E

D

F

I

H

M

K

L

樹(shù)形表示法

AA的度:3B的度:2C的度:1D的度:2E的度:0I的度:33.分支結(jié)點(diǎn)與葉結(jié)點(diǎn):度不為零的結(jié)點(diǎn)稱(chēng)為非終端結(jié)點(diǎn),又叫分支結(jié)點(diǎn)。度為零的結(jié)點(diǎn)稱(chēng)為終端結(jié)點(diǎn)或葉結(jié)點(diǎn)。4.樹(shù)的度:樹(shù)中所有結(jié)點(diǎn)的度的最大值max(D(I))。含義:樹(shù)中最大分支數(shù)為樹(shù)的度。A的度:3B的度:2C的度:1D的度:2E的度:0I的度:3

A

C

G

B

D

I

JEFH

MKL

樹(shù)形表示法

樹(shù)的度:3結(jié)點(diǎn)所在層數(shù):根結(jié)點(diǎn)的層數(shù)為1;對(duì)其余任何結(jié)點(diǎn),若某結(jié)點(diǎn)在第k層,則其孩子結(jié)點(diǎn)在第k+1層。樹(shù)的深度:樹(shù)中所有結(jié)點(diǎn)的最大層數(shù),也稱(chēng)高度。1層2層4層3層高度=4CGBDEFKLHMIJC樹(shù)的基本術(shù)語(yǔ) 5.CBDEFKLHJA71234568910層序編號(hào):將樹(shù)中結(jié)點(diǎn)按照從上層到下層、同層從左到右的次序依次給他們編以從1開(kāi)始的連續(xù)自然數(shù)。樹(shù)的基本術(shù)語(yǔ)有序樹(shù)、無(wú)序樹(shù):如果一棵樹(shù)中結(jié)點(diǎn)的各子樹(shù)從左到右是有次序的,稱(chēng)這棵樹(shù)為有序樹(shù);反之,稱(chēng)為無(wú)序樹(shù)。數(shù)據(jù)結(jié)構(gòu)中討論的一般都是有序樹(shù)

樹(shù)的基本術(shù)語(yǔ) 6.ACBGFEDACBGFEDCBDEFKLHJ森林:m(m≥0)棵互不相交的樹(shù)的集合。

樹(shù)的基本術(shù)語(yǔ) 7.A路徑:如果樹(shù)的結(jié)點(diǎn)序列n1,n2,…,nk有如下關(guān)系:則把n1,n2,…,nk稱(chēng)為一條由n1至nk的路徑;路徑上經(jīng)過(guò)的邊的個(gè)數(shù)稱(chēng)為路徑長(zhǎng)度。CGBDEFKLHMIJA樹(shù)的基本術(shù)語(yǔ) 8.祖先、子孫:在樹(shù)中,如果有一條路徑從結(jié)點(diǎn)x到結(jié)點(diǎn)y,那么x就稱(chēng)為y的祖先,而y稱(chēng)為x的子孫。CGBDEFKLHMIJA樹(shù)的基本術(shù)語(yǔ) 9.

總結(jié)基本術(shù)語(yǔ)的理解:結(jié)點(diǎn)的度:一個(gè)結(jié)點(diǎn)含有的子樹(shù)的個(gè)數(shù)稱(chēng)為該結(jié)點(diǎn)的度;如結(jié)點(diǎn)D含有3個(gè)子樹(shù),則結(jié)點(diǎn)D的度為3,而結(jié)點(diǎn)C的度為1,結(jié)點(diǎn)K的度為0。葉結(jié)點(diǎn)或終端結(jié)點(diǎn):度為零的結(jié)點(diǎn)稱(chēng)為葉結(jié)點(diǎn);如結(jié)點(diǎn)F的度為0,則為葉子結(jié)點(diǎn)。非終端結(jié)點(diǎn)或分支結(jié)點(diǎn):度不為零的結(jié)點(diǎn);

雙親結(jié)點(diǎn)(父結(jié)點(diǎn)):含有孩子的結(jié)點(diǎn)稱(chēng)為其孩子的雙親結(jié)點(diǎn);例如,結(jié)點(diǎn)B是E,F的雙親結(jié)點(diǎn)(父結(jié)點(diǎn))。孩子結(jié)點(diǎn):一個(gè)結(jié)點(diǎn)子樹(shù)的根結(jié)點(diǎn)稱(chēng)為該結(jié)點(diǎn)的孩子結(jié)點(diǎn);例如,結(jié)點(diǎn)B的孩子結(jié)點(diǎn)有E,F兩個(gè)。兄弟結(jié)點(diǎn):具有相同雙親結(jié)點(diǎn)的結(jié)點(diǎn)互稱(chēng)為兄弟結(jié)點(diǎn);如E,F互為兄弟結(jié)點(diǎn)。CGBDEFKLHMIJA

總結(jié)基本術(shù)語(yǔ)的理解:樹(shù)的度:一棵樹(shù)中,最大的結(jié)點(diǎn)的度稱(chēng)為樹(shù)的度;結(jié)點(diǎn)的層次:從根開(kāi)始定義起,根為第一層,根的孩子為第二層;

樹(shù)的高度或深度:樹(shù)中結(jié)點(diǎn)的最大層次;堂兄弟:雙親在同一層的結(jié)點(diǎn)互為堂兄弟;

結(jié)點(diǎn)的祖先:從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn);子孫:以某結(jié)點(diǎn)為根的子樹(shù)中任一結(jié)點(diǎn)都稱(chēng)為該結(jié)點(diǎn)的子孫。森林:由m(m>=0)棵互不相交的樹(shù)的集合稱(chēng)為森林;CGBDEFKLHMIJA1.有一棵樹(shù)如圖所示,回答下面的問(wèn)題(1)這棵樹(shù)的葉子結(jié)點(diǎn)是___________。(2)結(jié)點(diǎn)k3的度是______________(3)這棵樹(shù)的度是_____________(4)這棵樹(shù)的深度是____________(5)結(jié)點(diǎn)k3的孩子結(jié)點(diǎn)是___________(6)這棵樹(shù)的根結(jié)點(diǎn)是___________(7)結(jié)點(diǎn)k3的雙親結(jié)點(diǎn)是____________樹(shù)的表示方法(廣義表法)二叉樹(shù)的定義

二叉樹(shù)是n(n≥0)個(gè)結(jié)點(diǎn)的有限集合,該集合或者為空集(稱(chēng)為空二叉樹(shù)),或者由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的、分別稱(chēng)為根結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。二叉樹(shù)的邏輯結(jié)構(gòu)問(wèn)題轉(zhuǎn)化:將樹(shù)轉(zhuǎn)換為二叉樹(shù),從而利用二叉樹(shù)解決樹(shù)的有關(guān)問(wèn)題。研究二叉樹(shù)的意義?設(shè)有八枚硬幣,分別表示為a、b、c、d、e、f、g、h,其中有且僅有一枚硬幣是假幣,并且假幣的重量與真幣的重量不同,可能輕,也可能重?,F(xiàn)要求以天平為工具,用最少的比較次數(shù)挑選出假幣,并同時(shí)確定這枚假幣的重量比其它真幣是輕還是重。把硬幣分成三組,從八枚硬幣中任取六枚a、b、c、d、e、f,在天平兩端各放三枚進(jìn)行比較。假設(shè)a、b、c三枚放在天平的一端,d、e、f三枚放在天平的另一端,可能出現(xiàn)如圖所示的三種比較結(jié)

7.2二叉樹(shù)概念和性質(zhì)

7.2.1二叉樹(shù)概念7.2.2二叉樹(shù)性質(zhì)7.2.3二叉樹(shù)存儲(chǔ)結(jié)構(gòu)7.2.1二叉樹(shù)概念二叉樹(shù)也稱(chēng)為二次樹(shù)或二分樹(shù),它是結(jié)點(diǎn)數(shù)為0或當(dāng)節(jié)點(diǎn)數(shù)不為0時(shí)每個(gè)結(jié)點(diǎn)最多只有左右兩棵子樹(shù)的樹(shù)。特點(diǎn)是:(1)每個(gè)結(jié)點(diǎn)最多只有兩棵樹(shù),既不存在度大于2的結(jié)點(diǎn)。(2)子樹(shù)有左右之分,不能顛倒。思考:二叉樹(shù)和度為2的樹(shù)一樣嗎有什么區(qū)別?結(jié)點(diǎn)的孩子數(shù)結(jié)點(diǎn)孩子的有序性二叉樹(shù)的特點(diǎn):⑴每個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù);⑵二叉樹(shù)是有序的,其次序不能任意顛倒。

7.2.1二叉樹(shù)的邏輯結(jié)構(gòu)注意:二叉樹(shù)和樹(shù)是兩種樹(shù)結(jié)構(gòu)。ABCDEFGABAB二叉樹(shù)的基本形態(tài)Ф空二叉樹(shù)只有一個(gè)根結(jié)點(diǎn)左子樹(shù)根結(jié)點(diǎn)只有左子樹(shù)右子樹(shù)根結(jié)點(diǎn)只有右子樹(shù)左子樹(shù)右子樹(shù)根結(jié)點(diǎn)同時(shí)有左右子樹(shù)二叉樹(shù)的邏輯結(jié)構(gòu)二叉樹(shù)的邏輯結(jié)構(gòu)具有3個(gè)結(jié)點(diǎn)的樹(shù)和具有3個(gè)結(jié)點(diǎn)的二叉樹(shù)的形態(tài)二叉樹(shù)和樹(shù)是兩種樹(shù)結(jié)構(gòu)。特殊的二叉樹(shù)斜樹(shù)1.所有結(jié)點(diǎn)都只有左子樹(shù)的二叉樹(shù)稱(chēng)為左斜樹(shù);2.所有結(jié)點(diǎn)都只有右子樹(shù)的二叉樹(shù)稱(chēng)為右斜樹(shù);3.左斜樹(shù)和右斜樹(shù)統(tǒng)稱(chēng)為斜樹(shù)。1.在斜樹(shù)中,每一層只有一個(gè)結(jié)點(diǎn);2.斜樹(shù)的結(jié)點(diǎn)個(gè)數(shù)與其深度相同。

二叉樹(shù)的邏輯結(jié)構(gòu)---斜樹(shù)的特點(diǎn):ABCABC滿(mǎn)二叉樹(shù)在一棵二叉樹(shù)中,如果所有分支結(jié)點(diǎn)都存在左子樹(shù)和右子樹(shù),并且所有葉子都在同一層上。滿(mǎn)二叉樹(shù)的特點(diǎn):葉子只能出現(xiàn)在最下一層;只有度為0和度為2的結(jié)點(diǎn)。CDEFGHIJKLMNO1112131415特殊的二叉樹(shù)二叉樹(shù)的邏輯結(jié)構(gòu)---滿(mǎn)二叉樹(shù)?不是滿(mǎn)二叉樹(shù),雖然所有分支結(jié)點(diǎn)都有左右子樹(shù),但葉子不在同一層上。滿(mǎn)二叉樹(shù)在同樣深度的二叉樹(shù)中結(jié)點(diǎn)個(gè)數(shù)最多滿(mǎn)二叉樹(shù)在同樣深度的二叉樹(shù)中葉子結(jié)點(diǎn)個(gè)數(shù)最多A1523467BCDEFGLM89特殊的二叉樹(shù)二叉樹(shù)的邏輯結(jié)構(gòu)---完全二叉樹(shù)對(duì)一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)按層序編號(hào),如果編號(hào)為i(1≤i≤n)的結(jié)點(diǎn)與同樣深度的滿(mǎn)二叉樹(shù)中編號(hào)為i的結(jié)點(diǎn)在二叉樹(shù)中的位置完全相同。CDEFGHIJKLMNO1112131415CDEFGHIJ特殊的二叉樹(shù)二叉樹(shù)的邏輯結(jié)構(gòu)---在滿(mǎn)二叉樹(shù)中,從最后一個(gè)結(jié)點(diǎn)開(kāi)始,連續(xù)去掉任意個(gè)結(jié)點(diǎn),即是一棵完全二叉樹(shù)。A1523467910BCDEFGHIJK11L12M13N14O158CDEFGHIJ不是完全二叉樹(shù),結(jié)點(diǎn)10與滿(mǎn)二叉樹(shù)中的結(jié)點(diǎn)10不是同一個(gè)結(jié)點(diǎn)特殊的二叉樹(shù)二叉樹(shù)的邏輯結(jié)構(gòu)---1.葉子結(jié)點(diǎn)只能出現(xiàn)在最下兩層,且最下層的葉子結(jié)點(diǎn)都集中在二叉樹(shù)的左部;2.完全二叉樹(shù)中如果有度為1的結(jié)點(diǎn),只可能有一個(gè),且該結(jié)點(diǎn)只有左孩子。

3.深度為k的完全二叉樹(shù)在k-1層上一定是滿(mǎn)二叉樹(shù)。完全二叉樹(shù)的特點(diǎn)CDEFGHIJ特殊的二叉樹(shù)二叉樹(shù)的邏輯結(jié)構(gòu)---總結(jié)二叉樹(shù)的概念二叉樹(shù)的五種形態(tài)斜二叉樹(shù)滿(mǎn)二叉樹(shù)完全二叉樹(shù)7.2.2二叉樹(shù)性質(zhì)(5個(gè))

性質(zhì)1非空二叉樹(shù)上第i層上至多有2i-1個(gè)結(jié)點(diǎn),這里應(yīng)有i≥1。

性質(zhì)1非空二叉樹(shù)上第i層上至多有2i-1個(gè)結(jié)點(diǎn),這里應(yīng)有i≥1。證明:用歸納法(1)當(dāng)i=120有一個(gè)根結(jié)點(diǎn)成立(2)假設(shè)對(duì)所有的j(1<=j<i)上述性質(zhì)成立。即第j層上至多有2j-1個(gè)結(jié)點(diǎn)成立(3)要證明j=i時(shí),命題也成立由歸納假設(shè):第j=i-1層上至多有2i-2

個(gè)結(jié)點(diǎn),又由于二叉樹(shù)上每個(gè)結(jié)點(diǎn)的度最大為2,所以第i層上結(jié)點(diǎn)總數(shù)最大為第i-1層上最大結(jié)點(diǎn)數(shù)的2倍,即2×2i-2=2i-1

性質(zhì)2高度為h的二叉樹(shù)至多有2h-1個(gè)結(jié)點(diǎn)(h≥1)。證明:深度為h的二叉樹(shù)的最大結(jié)點(diǎn)數(shù)是二叉樹(shù)中每層結(jié)點(diǎn)的最大數(shù)之和,即=20+21+22+……+2h-1=2h-1(等比級(jí)數(shù)求和)

性質(zhì)3非空二叉樹(shù)上葉結(jié)點(diǎn)數(shù)等于度為2的結(jié)點(diǎn)數(shù)加1。有如下關(guān)系:n0=n2+1

證明:設(shè)二叉樹(shù)上葉結(jié)點(diǎn)數(shù)為n0,單分支結(jié)點(diǎn)數(shù)為n1,雙分支結(jié)點(diǎn)數(shù)為n2,則總結(jié)點(diǎn)數(shù)n=n0+n1+n2。在一棵二叉樹(shù)中,度為i(i=0,1,2)的結(jié)點(diǎn),有i個(gè)孩子。孩子數(shù)=n1+2n2。由于二叉樹(shù)中除根結(jié)點(diǎn)以外,每個(gè)結(jié)點(diǎn)都是另一個(gè)結(jié)點(diǎn)的孩子,因此二叉樹(shù)中有:孩子數(shù)=總結(jié)點(diǎn)數(shù)-1=n-1。由上述三個(gè)等式可得:n1+2n2=n-1=n0+n1+n2-1即:n0=n2+1

A

B

C

D

E

H

J

K

F

G

L

M

N

O

二叉樹(shù)

(1)一棵二叉樹(shù)中雙分支結(jié)點(diǎn)有15個(gè),單分支結(jié)點(diǎn)30個(gè),則葉子結(jié)點(diǎn)有()。(2)若一棵滿(mǎn)二叉樹(shù)有2047個(gè)結(jié)點(diǎn),則該二叉樹(shù)中葉結(jié)點(diǎn)的個(gè)數(shù)為

A)512 B)1024 C)2048 D)4096(3)若一棵度為7的樹(shù)具有n1=8,n2=7,n3=6,n4=5,n5=4,n6=3,n7=2,則該樹(shù)一共有()個(gè)葉結(jié)點(diǎn)[提示:此不是二叉樹(shù),用性質(zhì)3的證明方法來(lái)推導(dǎo)]

在一棵二叉樹(shù)中,如果所有分支結(jié)點(diǎn)都有左孩子結(jié)點(diǎn)和右孩子結(jié)點(diǎn),并且葉結(jié)點(diǎn)都集中在二叉樹(shù)的最下一層,這樣的二叉樹(shù)稱(chēng)為滿(mǎn)二叉樹(shù)。下圖所示就是一棵滿(mǎn)二叉樹(shù)。可以對(duì)滿(mǎn)二叉樹(shù)的結(jié)點(diǎn)進(jìn)行連續(xù)編號(hào),約定編號(hào)從樹(shù)根為1開(kāi)始,按照層數(shù)從小到大、同一層從左到右的次序進(jìn)行。圖中每個(gè)結(jié)點(diǎn)外邊的數(shù)字為對(duì)該結(jié)點(diǎn)的編號(hào)。每一層上結(jié)點(diǎn)樹(shù)都達(dá)到最大度為1的結(jié)點(diǎn)n1=0完全二叉樹(shù):若二叉樹(shù)中度小于2的結(jié)點(diǎn)只能出現(xiàn)在最大層或次大層,并且最下面一層的葉結(jié)點(diǎn)都依次排列在該層最左邊的位置上,則這樣的二叉樹(shù)稱(chēng)為完全二叉樹(shù)。如下圖所示為一棵完全二叉樹(shù)。同樣可以對(duì)完全二叉樹(shù)中每個(gè)結(jié)點(diǎn)進(jìn)行連續(xù)編號(hào),編號(hào)的方法同滿(mǎn)二叉樹(shù)相同。

12

3

4

1

2

3

4

5

6

判斷是否為:完全二叉樹(shù)?(1)LH1=2RH1=1LH2=0RH2=10-1=-1不滿(mǎn)足(2)葉結(jié)點(diǎn)只能出現(xiàn)在最大層或次大層從左邊開(kāi)始結(jié)論:不是(1)LH1=3RH1=1LH1-RH1=2不滿(mǎn)足(2)葉結(jié)點(diǎn)只能出現(xiàn)在最大層或次大層且從從左邊開(kāi)始結(jié)論:不是

性質(zhì)4具有n個(gè)(n>0)結(jié)點(diǎn)的完全二叉樹(shù)的高(深)度為log2n+1。證明:設(shè)深度為H余下的性質(zhì)是針對(duì)完全二叉樹(shù)的:證明:假設(shè)具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為k,根據(jù)完全二叉樹(shù)的定義和性質(zhì)2,有下式成立

2k-1≤n<2k

2k-1-1…2k-12k-1———第k-1層———第k層…最少結(jié)點(diǎn)數(shù)最多結(jié)點(diǎn)數(shù)

log2n+1[log2n]log2n[log2n]+1k所在區(qū)間證明:假設(shè)具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為k,根據(jù)完全二叉樹(shù)的定義和性質(zhì)2,有下式成立

2k-1≤n<2k性質(zhì)4

具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為log2n+1。

對(duì)不等式取對(duì)數(shù),有:

k-1≤log2n<k即:

log2n<k≤log2n+1由于k是整數(shù),故必有k=log2n+1一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中從1開(kāi)始按層序編號(hào),則結(jié)點(diǎn)i的雙親結(jié)點(diǎn)為

i/2;結(jié)點(diǎn)i的左孩子為2i;結(jié)點(diǎn)i的右孩子為2i+1。

在完全二叉樹(shù)中,結(jié)點(diǎn)的層序編號(hào)反映了結(jié)點(diǎn)之間的邏輯關(guān)系。完全二叉樹(shù)的基本性質(zhì)

性質(zhì)5對(duì)n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中編號(hào)為i的結(jié)點(diǎn)(1≤i≤n,n≥1,n為結(jié)點(diǎn)數(shù))有:

(1)若i=1時(shí),結(jié)點(diǎn)i是樹(shù)根;否則(i>1),結(jié)點(diǎn)i的雙親為

i/2.(2)若2i>n時(shí)。結(jié)點(diǎn)i無(wú)左孩子,是葉結(jié)點(diǎn);否則結(jié)點(diǎn)i的左孩子為結(jié)點(diǎn)2i。

(3)若2i+1>n時(shí)。結(jié)點(diǎn)i無(wú)右孩子;否則結(jié)點(diǎn)i的左孩子為結(jié)點(diǎn)2i+1。余下的性質(zhì)是針對(duì)完全二叉樹(shù)的(很重要):先證明(2)(3)用歸納法

(2)若2i>n時(shí)。結(jié)點(diǎn)i無(wú)左孩子,是葉結(jié)點(diǎn);否則結(jié)點(diǎn)i的左孩子為結(jié)點(diǎn)2i。

(3)若2i+1>n時(shí)。結(jié)點(diǎn)i無(wú)右孩子;否則結(jié)點(diǎn)i的左孩子為結(jié)點(diǎn)2i+1。1)當(dāng)i=1時(shí),如果2i=2>n無(wú)左孩子,否則2i=2<=n

結(jié)點(diǎn)2存在是結(jié)點(diǎn)1的左孩子。第二條成立當(dāng)i=1時(shí),如果2i+1=3>n無(wú)右孩子,否則2i+1=3<=n

結(jié)點(diǎn)3存在是結(jié)點(diǎn)1的右孩子。第三條成立2)假設(shè)對(duì)所有的結(jié)點(diǎn)j(1<=j<=i)有:j的左孩子為2j(2j<=n),右孩子為2j+1(2j+1<=n)3)要證明j=i+1時(shí)等式成立i+1的左孩子為2(i+1) (2(i+1)<=n)i+1的右孩子為2(i+1)+1 (2(i+1)+1<=n)i2i2i+1

i+12i+22i+3…………i與i+1同層……

i2i2i+1……

i+12i+22i+3……i與i+1不同層結(jié)論:得證(1)若i=1時(shí),結(jié)點(diǎn)i是樹(shù)根;否則(i>1),結(jié)點(diǎn)i的雙親為

i/2.用歸納法自己證明第五條性質(zhì)非常重要,是二叉樹(shù)順序存儲(chǔ)的理論基礎(chǔ)7.2.3樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換1.兄弟加線(xiàn).樹(shù)轉(zhuǎn)化為二叉樹(shù)ABCDEFG2.保留雙親與第一孩子連線(xiàn),刪去與其他孩子的連線(xiàn).ABCDEFG1.兄弟加線(xiàn).7.2.3樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換3.順時(shí)針轉(zhuǎn)動(dòng),使之層次分明.2.保留雙親與第一孩子連線(xiàn),刪去與其他孩子的連線(xiàn).1.兄弟加線(xiàn).ABCDEFG7.2.3樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換樹(shù)和二叉樹(shù)之間的對(duì)應(yīng)關(guān)系3.順時(shí)針轉(zhuǎn)動(dòng),使之層次分明.2.保留雙親與第一孩子連線(xiàn),刪去與其他孩子的連線(xiàn).1.兄弟加線(xiàn).GDABECF7.2.3樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換樹(shù)和二叉樹(shù)之間的對(duì)應(yīng)關(guān)系總結(jié):樹(shù)轉(zhuǎn)換為二叉樹(shù)

⑴加線(xiàn)——樹(shù)中所有相鄰兄弟之間加一條連線(xiàn)。

⑵去線(xiàn)——對(duì)樹(shù)中的每個(gè)結(jié)點(diǎn),只保留它與第一個(gè)孩子結(jié)點(diǎn)之間的連線(xiàn),刪去它與其它孩子結(jié)點(diǎn)之間的連線(xiàn)。

⑶層次調(diào)整——以根結(jié)點(diǎn)為軸心,將樹(shù)順時(shí)針轉(zhuǎn)動(dòng)一定的角度,使之層次分明。

森林轉(zhuǎn)換為二叉樹(shù)

⑴將森林中的每棵樹(shù)轉(zhuǎn)換成二叉樹(shù);⑵從第二棵二叉樹(shù)開(kāi)始,依次把后一棵二叉樹(shù)的根結(jié)點(diǎn)作為前一棵二叉樹(shù)根結(jié)點(diǎn)的右孩子,當(dāng)所有二叉樹(shù)連起來(lái)后,此時(shí)所得到的二叉樹(shù)就是由森林轉(zhuǎn)換得到的二叉樹(shù)。7.2.3樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換IHGBCDAFE二叉樹(shù)轉(zhuǎn)換為樹(shù)或森林

⑴加線(xiàn)——若某結(jié)點(diǎn)x是其雙親y的左孩子,則把結(jié)點(diǎn)x的右孩子、右孩子的右孩子、……,都與結(jié)點(diǎn)y用線(xiàn)連起來(lái);⑵去線(xiàn)——?jiǎng)h去原二叉樹(shù)中所有的雙親結(jié)點(diǎn)與右孩子結(jié)點(diǎn)的連線(xiàn);⑶

層次調(diào)整——整理由⑴、⑵兩步所得到的樹(shù)或森林,使之層次分明。

7.2.3樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換FHGEAICDBFHGDCEBAIFEDCBAHGI加線(xiàn)去線(xiàn)層次調(diào)整IHGBCDAFE樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換例題:將下面的深林轉(zhuǎn)化為二叉樹(shù)ACDBEFGJIH7.3二叉樹(shù)存儲(chǔ)結(jié)構(gòu)

7.3.1二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)

7.3.2二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)7.3.1二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)用一組地址連續(xù)的存儲(chǔ)單元,以層序的順序存放二叉樹(shù)的數(shù)據(jù)元素,結(jié)點(diǎn)的相對(duì)位置蘊(yùn)含著結(jié)點(diǎn)的關(guān)系?!咀⒁狻窟壿嬯P(guān)系蘊(yùn)含在這里:結(jié)點(diǎn)的相對(duì)位置蘊(yùn)含著結(jié)點(diǎn)的關(guān)系。ABCDEFGHIJK123456789101112131415順序存儲(chǔ)結(jié)構(gòu)一般二叉樹(shù)的順序存儲(chǔ)沒(méi)有左右孩子的地方填0

A

B

C

D

E

FG

一般二叉樹(shù)

ABCDE0000FG0000123456789101112131415順序存儲(chǔ)結(jié)構(gòu)例:深度為K,只有K個(gè)結(jié)點(diǎn)的右單支樹(shù)的存放:分析:根據(jù)性質(zhì)2:二叉樹(shù)深度為K最多有2k-1個(gè)結(jié)點(diǎn)按順序存儲(chǔ)實(shí)際只使用K個(gè)存儲(chǔ)單元,浪費(fèi)掉2k-1-K

1

2

K

1

K

結(jié)論:順序存儲(chǔ)只適合完全二叉樹(shù),既不浪費(fèi)空間,又能很快的確定結(jié)點(diǎn)存放的位置,以及結(jié)點(diǎn)的雙親和左右孩子。但是對(duì)于一般二叉樹(shù)可能造成存儲(chǔ)空間的浪費(fèi)。7.3.2二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

常用的:二叉鏈表三叉鏈表線(xiàn)索鏈表

A

B

C

D

E

FG

一般二叉樹(shù)

在二叉樹(shù)的鏈接存儲(chǔ)中,結(jié)點(diǎn)的結(jié)構(gòu)如下:typedefstructnode{ ElemTypedata; structnode*lchild,*rchild;}BTNode;

其中,data表示值域,用于存儲(chǔ)對(duì)應(yīng)的數(shù)據(jù)元素,lchild和rchild分別表示左指針域和右指針域,用于分別存儲(chǔ)左孩子結(jié)點(diǎn)和右孩子結(jié)點(diǎn)(即左、右子樹(shù)的根結(jié)點(diǎn))的存儲(chǔ)位置。lchilddatarchild二叉樹(shù)及其鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)點(diǎn):找孩子比較容易,找雙親很難

A

B

C

E

F

D

G

A

B∧

C

D

E∧

F∧

G∧

(a)

(b)

在三叉鏈表的存儲(chǔ)中,結(jié)點(diǎn)的結(jié)構(gòu)如下:

typedefstructnode{ ElemTypedata; structnode*lchild,*parent,*rchild;}BTNode;

其中,data表示值域,用于存儲(chǔ)對(duì)應(yīng)的數(shù)據(jù)元素,lchild和rchild分別表示左指針域和右指針域,用于分別存儲(chǔ)左孩子結(jié)點(diǎn)和右孩子結(jié)點(diǎn)(即左、右子樹(shù)的根結(jié)點(diǎn))的存儲(chǔ)位置,parent

指向結(jié)點(diǎn)的雙親。lchilddataparentrchild二叉樹(shù)及其鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

A

B

C

E

F

D

G

(a)

∧A∧BCD∧∧F∧∧E∧∧G∧性質(zhì)6:含有n個(gè)結(jié)點(diǎn)的二叉鏈表中,有n+1個(gè)空鏈域證明:(1)n=n0+n1+n2(2)空鏈域=2n0+n1(3)no=n2+1

A

B

C

E

F

D

G

A

B∧

C

D

E∧

F∧

G∧

(a)

(b)

7.5二叉樹(shù)的遍歷7.5.1二叉樹(shù)遍歷的概念7.5.2二叉樹(shù)遍歷的實(shí)現(xiàn)遞歸及非遞歸算法二叉樹(shù)的遍歷操作

二叉樹(shù)的遍歷是指從根結(jié)點(diǎn)出發(fā),按照某種次序訪(fǎng)問(wèn)二叉樹(shù)中的所有結(jié)點(diǎn),使得每個(gè)結(jié)點(diǎn)被訪(fǎng)問(wèn)一次且僅被訪(fǎng)問(wèn)一次。二叉樹(shù)遍歷操作的結(jié)果?非線(xiàn)性結(jié)構(gòu)線(xiàn)性化7.5二叉樹(shù)的邏輯結(jié)構(gòu)抽象操作,可以是對(duì)結(jié)點(diǎn)進(jìn)行的各種處理,這里簡(jiǎn)化為輸出結(jié)點(diǎn)的數(shù)據(jù)。前序遍歷中序遍歷后序遍歷層序遍歷

如果限定先左后右,則二叉樹(shù)遍歷方式有三種:前序:DLR中序:LDR后序:LRD層序遍歷:按二叉樹(shù)的層序編號(hào)的次序訪(fǎng)問(wèn)各結(jié)點(diǎn)。

7.5.1二叉樹(shù)的邏輯結(jié)構(gòu)考慮二叉樹(shù)的組成:根結(jié)點(diǎn)D左子樹(shù)L右子樹(shù)R二叉樹(shù)前序遍歷若二叉樹(shù)為空,則空操作返回;否則:①訪(fǎng)問(wèn)根結(jié)點(diǎn);②前序遍歷根結(jié)點(diǎn)的左子樹(shù);③前序遍歷根結(jié)點(diǎn)的右子樹(shù)。前序遍歷序列:ABDGCEFABCDEFG二叉樹(shù)的遍歷操作

7.5二叉樹(shù)的邏輯結(jié)構(gòu)中序遍歷若二叉樹(shù)為空,則空操作返回;否則:①中序遍歷根結(jié)點(diǎn)的左子樹(shù);②訪(fǎng)問(wèn)根結(jié)點(diǎn);③中序遍歷根結(jié)點(diǎn)的右子樹(shù)。

中序遍歷序列:DGBAECFABCDEFG二叉樹(shù)的遍歷操作

7.5二叉樹(shù)的邏輯結(jié)構(gòu)后序遍歷若二叉樹(shù)為空,則空操作返回;否則:①后序遍歷根結(jié)點(diǎn)的左子樹(shù);②后序遍歷根結(jié)點(diǎn)的右子樹(shù)。③訪(fǎng)問(wèn)根結(jié)點(diǎn);后序遍歷序列:GDBEFCAABCDEFG二叉樹(shù)的遍歷操作

7.5二叉樹(shù)的邏輯結(jié)構(gòu)層序遍歷二叉樹(shù)的層次遍歷是指從二叉樹(shù)的第一層(即根結(jié)點(diǎn))開(kāi)始,從上至下逐層遍歷,在同一層中,則按從左到右的順序?qū)Y(jié)點(diǎn)逐個(gè)訪(fǎng)問(wèn)。

層序遍歷序列:ABCDEFGABCDEFG二叉樹(shù)的遍歷操作

7.5二叉樹(shù)的邏輯結(jié)構(gòu)

A

B

C

D

E

H

I

J

K

F

G

1

2

3

4

5

6

7

8

9

10

11

先序序列:ABDHIEJKCFG中序序列:HDIBJEKAFCG后序序列:HIDJKEBFGCA先序序列:ABDEHJKLMNCFGI中序序列:DBJHLKMNEAFCGI后序序列:DJLMNKHEBFGICA在二叉樹(shù)的鏈接存儲(chǔ)中,結(jié)點(diǎn)的結(jié)構(gòu)如下:typedefstructnode{ ElemTypedata; structnode*lchild,*rchild;}BTNode;

其中,data表示值域,用于存儲(chǔ)對(duì)應(yīng)的數(shù)據(jù)元素,lchild和rchild分別表示左指針域和右指針域,用于分別存儲(chǔ)左孩子結(jié)點(diǎn)和右孩子結(jié)點(diǎn)(即左、右子樹(shù)的根結(jié)點(diǎn))的存儲(chǔ)位置。lchilddatarchild二叉樹(shù)及其鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

(a)

(b)

A

B

C

E

F

D

A

B

C

D∧

E∧

F∧

∧1.先序遍歷DLR先序遍歷二叉樹(shù)的過(guò)程是:(1)訪(fǎng)問(wèn)根結(jié)點(diǎn)D;(2)先序遍歷左子樹(shù)L;(3)先序遍歷右子樹(shù)R。先序序列:ABDECF/*先序遍歷的遞歸算法*/voidPreOrder(BTNode*b){if(b!=NULL){printf("%c",b->data);/*訪(fǎng)問(wèn)根結(jié)點(diǎn)*/PreOrder(b->lchild);PreOrder(b->rchild);}}

A

B

C

E

F

D

lchilddatarchild/*先序遍歷的遞歸算法*/voidPreOrder(BTNode*b){if(b!=NULL){printf("%c",b->data);

/*訪(fǎng)問(wèn)根結(jié)點(diǎn)*/PreOrder(b->lchild);PreOrder(b->rchild);}}PreOrder(&A)APreOrder(A->lchild=B);BPreOrder(B->lchild=D);DPreOrder(D->lchild=NULL);PreOrder(D->rchild=NULL);PreOrder(B->rchild=E);EPreOrder(E->lchild=NULL);PreOrder(E->rchild=NULL);PreOrder(A->rchild=C);CPreOrder(C->lchild=NULL);PreOrder(C->rchild=F);FPreOrder(F->lchild=NULL);PreOrder(F->rchild=NULL);

A

B

C

D∧

E∧

F∧

∧2.中序遍歷LDR中序遍歷二叉樹(shù)的過(guò)程是:(1)中序遍歷左子樹(shù)L;(2)訪(fǎng)問(wèn)根結(jié)點(diǎn)D;(3)中序遍歷右子樹(shù)R。中序序列:DBEACF/*中序遍歷的遞歸算法*/voidInOrder(BTNode*b){if(b!=NULL){/*訪(fǎng)問(wèn)根結(jié)點(diǎn)*/

InOrder(b->lchild);

printf("%c",b->data);

InOrder(b->rchild);}}

A

B

C

E

F

D

3.后序遍歷后序遍歷二叉樹(shù)的過(guò)程是:(1)后序遍歷左子樹(shù);(2)后序遍歷右子樹(shù);(3)訪(fǎng)問(wèn)根結(jié)點(diǎn)。后序序列:DEBFCA

voidPostOrder(BTNode*b)/*后序遍歷遞歸算法*/{if(b!=NULL)

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
  • 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ì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論