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

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

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

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

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

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

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

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

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

弧：頂點x到y(tǒng)的一條單向通路，則稱為弧，用<x,y>表示。?

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

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

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

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

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

(b)有向圖

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

圖的基本概念

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

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

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

0132401324012340123401230132(a)無向圖鄰接矩陣

(b)有向圖鄰接矩陣

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

圖的存儲方式

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

圖的存儲方式

圖的遍歷方法

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

圖的遍歷方法

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

哈夫曼樹和哈夫曼編碼

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

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