軟件開發(fā)技術(shù)基礎(chǔ) 第4版 課件 3.樹和圖

非線性數(shù)據(jù)結(jié)構(gòu)

—樹與圖樹的遞歸定義樹是由n個(gè)具有相同特性的數(shù)據(jù)元素組成的集合。若n=0，則稱其為空樹。一棵非空樹T必須滿足：1）其中有一個(gè)特定的元素稱為T的根root。2）除根以外的集合可劃分為m個(gè)不相交子集T1，T2，…，Tm，其中每個(gè)子集都是樹。它們稱為根root的子樹。

西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心2GACFDEB樹的一般形式與樹相關(guān)的術(shù)語結(jié)點(diǎn)：在樹結(jié)構(gòu)中一般把數(shù)據(jù)元素及其若干指向子樹的分支稱為結(jié)點(diǎn)。結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的非空子樹的個(gè)數(shù)。樹的度：樹中所有結(jié)點(diǎn)的度的最大值。葉子結(jié)點(diǎn)：沒有非空子樹的結(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)，同時(shí)該結(jié)點(diǎn)也稱為其孩子結(jié)點(diǎn)的父結(jié)點(diǎn)。西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心3與樹相關(guān)的術(shù)語兄弟結(jié)點(diǎn)：具有相同父結(jié)點(diǎn)的結(jié)點(diǎn)互為兄弟結(jié)點(diǎn)。結(jié)點(diǎn)的層次：根結(jié)點(diǎn)的層次為1,其子結(jié)點(diǎn)的層次為2。依次類推，子結(jié)點(diǎn)的層次總比父結(jié)點(diǎn)多一層。樹的深度：樹中結(jié)點(diǎn)所在的最大層次。有序樹和無序樹：將樹中各結(jié)點(diǎn)的子樹看成自左向右有序的，則稱該樹為有序樹。否則稱為無序樹。森林：由零棵或有限棵互不相交的樹組成的集合。

西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心4二叉樹的定義二叉樹可以是空樹，當(dāng)二叉樹非空時(shí)，其中有一個(gè)根元素，余下的元素組成兩個(gè)互不相交二叉樹，分別稱為根的左子樹和右子樹。二叉樹是有序樹，也就是說任意結(jié)點(diǎn)的左、右子樹不可交換。而一般樹的子樹間是無序的。特殊形式的二叉樹西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心5AFC滿二叉樹GDBEAC完全二叉樹DBE二叉樹有下列重要性質(zhì)在二叉樹的第k層上至多有2k-1個(gè)結(jié)點(diǎn)(k≥1)深度為h的二叉樹上至多含2h-1個(gè)結(jié)點(diǎn)(h≥1)包含n(n>0)個(gè)結(jié)點(diǎn)的二叉樹總的分支數(shù)為n-1任何一棵二叉樹，若含有n0個(gè)葉子結(jié)點(diǎn)、n2個(gè)度為2的結(jié)點(diǎn)，則必存在關(guān)系式n0=n2+1具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為[log2(n)]+1西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心6二叉樹有下列重要性質(zhì)6.若對(duì)含n個(gè)結(jié)點(diǎn)的完全二叉樹從上到下、從左至右進(jìn)行1至n的編號(hào)，則對(duì)二叉樹中任意一個(gè)編號(hào)為i的結(jié)點(diǎn)：①若i=1，則該結(jié)點(diǎn)是二叉樹的根，無父結(jié)點(diǎn)。否則，編號(hào)為[i/2]的結(jié)點(diǎn)為其父結(jié)點(diǎn)；②若2i>n，則該結(jié)點(diǎn)無左孩子。否則，編號(hào)為2i的結(jié)點(diǎn)為其左孩子結(jié)點(diǎn)；③若2i+1>n，則該結(jié)點(diǎn)無右孩子。否則，編號(hào)為2i+1的結(jié)點(diǎn)為其右孩子結(jié)點(diǎn)。西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心7二叉樹的鏈?zhǔn)酱鎯?chǔ)西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心8二叉樹的鏈?zhǔn)酱鎯?chǔ)ABC∧∧D∧∧E∧∧利用結(jié)點(diǎn)形式存儲(chǔ)的樹稱為二叉鏈表。從根結(jié)點(diǎn)出發(fā)，可以訪問二叉樹的任何結(jié)點(diǎn)。為了能夠訪問二叉樹，必須保留指向根結(jié)點(diǎn)的指針。這和單鏈表必須保留頭指針的道理一樣。

二叉樹的遍歷西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心9三種主要的遍歷算法——先序遍歷、中序遍歷和后序遍歷。

1）先序遍歷：首先訪問根結(jié)點(diǎn)，然后按先序遍歷方式訪問左子樹，最后按先序遍歷方式訪問右子樹。2）中序遍歷：首先按中序遍歷方式訪問左子樹，然后訪問根結(jié)點(diǎn)，最后按中序遍歷方式訪問右子樹。3）后序遍歷：首先按后序遍歷方式訪問左子樹，然后按后序遍歷方式訪問右子樹，最后訪問根結(jié)點(diǎn)。圖的基本概念

西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心10圖是由頂點(diǎn)集合及頂點(diǎn)間的關(guān)系集合組成的一種數(shù)據(jù)結(jié)構(gòu)。一般記作Graph＝(V,E)。其中V是頂點(diǎn)的有限非空集合；E是頂點(diǎn)之間關(guān)系的有限集合。?

邊：頂點(diǎn)x到y(tǒng)的一條雙向通路，稱為邊，用(x,y)表示。?

?。喉旤c(diǎn)x到y(tǒng)的一條單向通路，則稱為弧，用<x,y>表示。?

鄰接點(diǎn)：如果(x,y)是圖中的一條邊，則稱x與y互為鄰接點(diǎn)；如果<x,y>是圖中的一條弧，則稱y為x的鄰接點(diǎn)。?

頂點(diǎn)的度：一個(gè)頂點(diǎn)v的度是與它相關(guān)聯(lián)的邊的條數(shù)。圖的基本概念

西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心11?無向圖：若圖是由一些頂點(diǎn)和邊構(gòu)成則稱之為無向圖。?

有向圖：若圖是由一些頂點(diǎn)和弧構(gòu)成則稱之為有向圖。?

權(quán)：某些圖的邊或弧具有與它相關(guān)的數(shù)，稱之為權(quán)。這種帶權(quán)圖叫做網(wǎng)絡(luò)。0132528130123410234(a)無向圖

(b)有向圖

(c)網(wǎng)絡(luò)

圖的基本概念

西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心12?路徑：在圖中，若從頂點(diǎn)vi出發(fā)，沿一些邊或弧，經(jīng)過頂點(diǎn)vp1、vp2、…、vpm到達(dá)頂點(diǎn)vj。則稱頂點(diǎn)序列(vi，vp1，…，vpm，vj)為從頂點(diǎn)vi到頂點(diǎn)vj的路徑。若路徑上各頂點(diǎn)均不互相重復(fù)，則稱這樣的路徑為簡(jiǎn)單路徑。?路徑長(zhǎng)度：非帶權(quán)圖的路徑長(zhǎng)度是指此路徑上邊或弧的條數(shù)，帶權(quán)圖的路徑長(zhǎng)度是指路徑上各邊或弧的權(quán)之和?子圖：設(shè)有兩個(gè)圖G＝(V，E)和G′＝(V′，E′)。若V包含V′且E包含E′，則稱圖G′是圖G的子圖。圖的存儲(chǔ)方式

西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心131．鄰接矩陣:利用數(shù)組實(shí)現(xiàn)的。它利用一維數(shù)組存儲(chǔ)頂點(diǎn)信息，利用二維數(shù)組存儲(chǔ)頂點(diǎn)間邊或弧的信息。此二維數(shù)組又稱鄰接矩陣。0132528130123410234(a)無向圖

(b)有向圖 (c)網(wǎng)絡(luò)

0132401324012340123401230132(a)無向圖鄰接矩陣

(b)有向圖鄰接矩陣

(c)網(wǎng)絡(luò)鄰接矩陣

圖的存儲(chǔ)方式

西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心142．鄰接表鄰接表的結(jié)點(diǎn)結(jié)構(gòu)(c)網(wǎng)絡(luò)的表結(jié)點(diǎn)infonextadjvexnextadjvexfirstdata(a)頭結(jié)點(diǎn)(b)無權(quán)圖的表結(jié)點(diǎn)圖的存儲(chǔ)方式

圖的存儲(chǔ)方式

圖的遍歷方法

1．深度優(yōu)先搜索

圖的遍歷方法

2．廣度優(yōu)先搜索

哈夫曼樹和哈夫曼編碼

假定有n個(gè)具有權(quán)值的結(jié)點(diǎn)，則哈夫曼樹的構(gòu)造算法如下：①根據(jù)給定的n個(gè)權(quán)值{w1,w2,…,wn}，構(gòu)造n棵二叉樹的集合F={T1,T2,…,Tn}，其中每棵二叉樹中均只含一個(gè)帶權(quán)值為wi的根結(jié)點(diǎn)，其左、右子樹為空樹；②在F中選取其根結(jié)點(diǎn)的權(quán)值為最小的兩棵二叉樹，分別作為左、右子樹構(gòu)造一棵新的二叉樹，并置這棵新的二叉樹根結(jié)點(diǎn)的權(quán)值為其左、右子樹根結(jié)點(diǎn)的權(quán)值之和；③從F中刪去這兩棵樹，同時(shí)加入剛生成的新樹；④重復(fù)⑵和⑶兩步，直至F中只含一棵樹為止。哈夫曼樹和哈夫曼編碼

假定有一段報(bào)文由a、b、c、d四個(gè)字符構(gòu)成，它們的使用頻