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

1、第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) 第3章 非線性數(shù)據(jù)結(jié)構(gòu) 3.1 樹及其基本概念樹及其基本概念3.2 二叉樹二叉樹 3.3 二叉樹的遍歷二叉樹的遍歷 3.4 樹的存儲結(jié)構(gòu)和遍歷樹的存儲結(jié)構(gòu)和遍歷 3.5 樹、森林與二叉樹的轉(zhuǎn)換樹、森林與二叉樹的轉(zhuǎn)換 3.6 霍夫曼樹及其應(yīng)用霍夫曼樹及其應(yīng)用 第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) 3.7 圖及其基本概念圖及其基本概念 3.8 圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu) 3.9 圖的遍歷圖的遍歷 3.10 圖的連通性及最小生成樹圖的連通性及最小生成樹 本章小節(jié)本章小節(jié)習(xí)題習(xí)題 老祖宗老祖宗兒子兒子孫子孫子曾孫曾孫 定義：定義：樹是由樹是由n(n0

2、)個結(jié)點組個結(jié)點組成的有限集合成的有限集合T。其中。其中有且僅有一個結(jié)點稱有且僅有一個結(jié)點稱為根結(jié)點，其余結(jié)點為根結(jié)點，其余結(jié)點可分為可分為m(m0)個互不個互不相交的有限集合相交的有限集合T1，T2， Ti Tm，每個每個Ti本身又是一棵樹本身又是一棵樹，稱為根結(jié)點的子樹，稱為根結(jié)點的子樹。樹的定義是遞歸的！樹的定義是遞歸的！ 基本術(shù)語基本術(shù)語u 結(jié)點（結(jié)點（node）：）： 樹中元素。樹中元素。u 結(jié)點的度結(jié)點的度(degree)：結(jié)點擁有的子樹數(shù)。結(jié)點擁有的子樹數(shù)。樹形數(shù)據(jù)結(jié)構(gòu)是結(jié)點之間有分支，有樹形數(shù)據(jù)結(jié)構(gòu)是結(jié)點之間有分支，有層次的非線性數(shù)據(jù)結(jié)構(gòu)。層次的非線性數(shù)據(jù)結(jié)構(gòu)。一棵樹中最大的結(jié)

3、點度數(shù)為一棵樹中最大的結(jié)點度數(shù)為樹的樹的度。度。張源張源張明張明張亮張亮張麗張麗張林張林張維張維張平張平張華張華張群張群張晶張晶張磊張磊圖 3-1 樹型結(jié)構(gòu)3.1 樹及其基本概念樹及其基本概念u 雙親（雙親（parents）：）： 孩子結(jié)點的上層結(jié)點稱為這些結(jié)點的雙親。孩子結(jié)點的上層結(jié)點稱為這些結(jié)點的雙親。u 兄弟（兄弟（sibling）：）：同一雙親的孩子。同一雙親的孩子。u 結(jié)點的層次（結(jié)點的層次（level）：）：從根結(jié)點開始算起，根為第一層，根的從根結(jié)點開始算起，根為第一層，根的直接后繼結(jié)點為第二層，依次類推。直接后繼結(jié)點為第二層，依次類推。u 深度（深度（depth）：）： 樹中結(jié)點

4、的最大層次數(shù)。樹中結(jié)點的最大層次數(shù)。u 有序樹：有序樹：樹中結(jié)點在同一層中按從左到右有序排列，不樹中結(jié)點在同一層中按從左到右有序排列，不能互換的稱為有序樹。能互換的稱為有序樹。u 森林：森林：m(m0)棵互不相交的樹的集合?？没ゲ幌嘟坏臉涞募稀 孩子孩子(child)：除根結(jié)點外，每個結(jié)點都是其前趨結(jié)點的孩子。除根結(jié)點外，每個結(jié)點都是其前趨結(jié)點的孩子。u 葉子葉子(leaf)： 度為度為0的結(jié)點。的結(jié)點。 在計算機中表示一棵樹時，就隱含著一種確定的相對次序，在計算機中表示一棵樹時，就隱含著一種確定的相對次序，所以后面我們討論的都是有序樹。所以后面我們討論的都是有序樹。3.2.1 二叉樹的定

5、義及其性質(zhì)二叉樹的定義及其性質(zhì)二叉樹是二叉樹是n(n0)個結(jié)點的有限集合，它或為空個結(jié)點的有限集合，它或為空樹或是由一個根結(jié)點和兩棵分別稱為左子樹和樹或是由一個根結(jié)點和兩棵分別稱為左子樹和右子樹的互不相交的二叉樹構(gòu)成。右子樹的互不相交的二叉樹構(gòu)成。二叉樹也是遞歸定義的！二叉樹也是遞歸定義的！二叉樹的特點：二叉樹的特點：(1)每個結(jié)點最多有兩棵每個結(jié)點最多有兩棵子樹子樹(2)有左右之分有左右之分。ABEFABEF兩棵不同的二叉樹兩棵不同的二叉樹3.2 二二 叉叉 樹樹(a)(b)(c)(d)(e)圖圖3-2 二叉樹的五種基本形態(tài)二叉樹的五種基本形態(tài) 1 二叉樹的定義二叉樹的定義第第3 3章章 非

6、線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) 例3-1 畫出具有3個結(jié)點的樹和二叉樹的所有不同形態(tài)。(a)(b)圖圖3-3 有有3個結(jié)點的所有樹的不同形態(tài)個結(jié)點的所有樹的不同形態(tài) (a)(b)(c)(d)(e)圖圖3-4 3個結(jié)點的所有二叉樹的不同形態(tài)個結(jié)點的所有二叉樹的不同形態(tài) (2) 圖圖3-3 有有3個結(jié)點的所有樹的不同形態(tài)個結(jié)點的所有樹的不同形態(tài)解：解：(1) 具有具有3個結(jié)點的樹有個結(jié)點的樹有2種不同的形態(tài)，如圖種不同的形態(tài)，如圖3-3所示。所示。注意：注意：樹和二叉樹的區(qū)別主要是二叉樹的結(jié)點的子樹要區(qū)分左子樹和右子樹，即使在結(jié)點只有一個子樹的情況下，也要明確指出該子樹是左子樹還是右子樹。2 二叉樹的

7、性質(zhì)二叉樹的性質(zhì)u 性質(zhì)一：性質(zhì)一：二叉樹的第二叉樹的第i層上至多有層上至多有2i-1(i1)個結(jié)點。個結(jié)點。u 性質(zhì)二：性質(zhì)二：深度為深度為k的二叉樹上至多含有的二叉樹上至多含有2k-1個結(jié)點。個結(jié)點。u 性質(zhì)三：性質(zhì)三：在任意的二叉樹在任意的二叉樹T中，若有中，若有n0個葉子結(jié)點，個葉子結(jié)點，n2個度個度為為2的結(jié)點，則必有的結(jié)點，則必有: n0=n2+1。性質(zhì)三證明：性質(zhì)三證明：綜合這二者綜合這二者關(guān)系可得性關(guān)系可得性質(zhì)三質(zhì)三另一方面，度為另一方面，度為1的結(jié)點有的結(jié)點有1個孩子，度為個孩子，度為2的結(jié)點有的結(jié)點有2個孩子。故二叉樹中孩子結(jié)點個孩子。故二叉樹中孩子結(jié)點總數(shù)為：總數(shù)為：n1

8、+2n2，又二叉樹中只有根結(jié)點，又二叉樹中只有根結(jié)點不是任何結(jié)點的孩子，故總結(jié)點數(shù)為不是任何結(jié)點的孩子，故總結(jié)點數(shù)為n=n1+2n2+1 ；設(shè)設(shè)ni表示度數(shù)為表示度數(shù)為i的結(jié)點，則總結(jié)點數(shù)的結(jié)點，則總結(jié)點數(shù)n為：為：n=n0+n1+n2； 幾種特殊形式的二叉樹幾種特殊形式的二叉樹u 滿二叉樹滿二叉樹: 深度為深度為k的二叉樹的的二叉樹的,并且含有并且含有2k-1個結(jié)點。個結(jié)點。特點：每一層的結(jié)點數(shù)都是最大結(jié)點數(shù)特點：每一層的結(jié)點數(shù)都是最大結(jié)點數(shù)ACDHIJKLMNOEFGB圖圖3-6 深度為深度為4的滿二叉樹的滿二叉樹u 完全二叉樹：完全二叉樹：對滿二叉樹的結(jié)點進行連續(xù)編號：從根結(jié)點起，自上對

9、滿二叉樹的結(jié)點進行連續(xù)編號：從根結(jié)點起，自上而下逐層從左到右給每個結(jié)點編一個從而下逐層從左到右給每個結(jié)點編一個從1開始的順序號。開始的順序號。圖圖3-6就成為圖就成為圖3-7。134891011121314155672圖圖3-7 深度為深度為4的滿二叉樹的滿二叉樹深度為深度為k，有，有n個結(jié)點的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)個結(jié)點的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)點都與深度為點都與深度為k的滿二叉樹中的編號從的滿二叉樹中的編號從1到到n的結(jié)點一一的結(jié)點一一對應(yīng)時，稱之為完全二叉樹。如圖對應(yīng)時，稱之為完全二叉樹。如圖3-8所示是一棵深度所示是一棵深度為為4的完全二叉樹。的完全二叉樹。第第3 3章章 非線性

10、數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) 134891011125672圖圖3-8 深度為深度為4的完全二叉樹的完全二叉樹特點：特點：(1) 葉子只可能在層次最大的兩層上出現(xiàn)。葉子只可能在層次最大的兩層上出現(xiàn)。 (2) 最下面一層的結(jié)點都集中在該層最左邊的若干最下面一層的結(jié)點都集中在該層最左邊的若干位置上。位置上。第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) 思考：深度為h的完全二叉樹的結(jié)點數(shù)目不少于？2h-1u 性質(zhì)四：性質(zhì)四： 具有具有n個結(jié)點的完全二叉樹的深度為個結(jié)點的完全二叉樹的深度為lbn1證明：假設(shè)深度為k，則根據(jù)性質(zhì)2 2k11n2k1或 2k1n2k于是 k1lbnk 因為 k是整數(shù) 所以k=

11、lbn1第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) 如果對一棵有如果對一棵有n個結(jié)點的完全二叉樹的結(jié)個結(jié)點的完全二叉樹的結(jié)點按層序編號點按層序編號(從第從第1層到第層到第n層，每層從左到層，每層從左到右右)，則對任一結(jié)點，則對任一結(jié)點i(1in)，有，有 (1) 如果如果i=1，則，則i是二叉樹的根，無雙是二叉樹的根，無雙親；如果親；如果i1，則其雙親是結(jié)點，則其雙親是結(jié)點 。 (2) 如果如果2in，則結(jié)點，則結(jié)點i無左孩子；否則無左孩子；否則其左孩子是其左孩子是2i。 (3) 如果如果2i+1n，則結(jié)點，則結(jié)點i無右孩子；否無右孩子；否則其右孩子是結(jié)點則其右孩子是結(jié)點2i+1。 證明從略

12、。證明從略。u 性質(zhì)五：性質(zhì)五：i2/u 平衡二叉樹平衡二叉樹特點：特點：左子樹與右子樹的深度之差的絕對值不左子樹與右子樹的深度之差的絕對值不超過超過1，且左、右子樹也都是平衡二叉樹。，且左、右子樹也都是平衡二叉樹。例3-2 圖3-9中有兩棵二叉樹，試判定其是否是平衡二叉樹？ABDECCBFEDA(a)(b)圖圖3-9 兩棵二叉樹兩棵二叉樹3.2.2 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)1 二叉樹的順序存儲結(jié)構(gòu)二叉樹的順序存儲結(jié)構(gòu) 為實現(xiàn)順序存儲，必須把二叉樹中所有結(jié)點按照一為實現(xiàn)順序存儲，必須把二叉樹中所有結(jié)點按照一定的次序組成一個線性序列，使得結(jié)點在這個序列中的定的次序組成一個線性序列，使得結(jié)

13、點在這個序列中的相互位置能反映出結(jié)點之間的邏輯關(guān)系。相互位置能反映出結(jié)點之間的邏輯關(guān)系。 對于完全二叉樹，從樹根起，自上層到下層，每層對于完全二叉樹，從樹根起，自上層到下層，每層從左到右的給結(jié)點進行編號，就能得到一個反映整棵從左到右的給結(jié)點進行編號，就能得到一個反映整棵二叉樹結(jié)構(gòu)的線性序列。二叉樹結(jié)構(gòu)的線性序列。第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) 對于對于完全二叉樹完全二叉樹，按圖，按圖3-8中的編號順中的編號順序存儲，就能得到一個足以反映整個二叉樹序存儲，就能得到一個足以反映整個二叉樹結(jié)構(gòu)的線性序列。將完全二叉樹中所有結(jié)點結(jié)構(gòu)的線性序列。將完全二叉樹中所有結(jié)點按編號順序依次按編號順

14、序依次存儲到一組連續(xù)的存儲單元存儲到一組連續(xù)的存儲單元(即向量即向量)中，既不浪費內(nèi)存，又可用地址公式中，既不浪費內(nèi)存，又可用地址公式確定其結(jié)點的位置確定其結(jié)點的位置。但對于一般的二叉樹，。但對于一般的二叉樹，順序分配造成內(nèi)存浪費，圖順序分配造成內(nèi)存浪費，圖3-8所示的完全二所示的完全二叉樹，其順序存儲結(jié)構(gòu)如圖叉樹，其順序存儲結(jié)構(gòu)如圖3-10(a)所示。所示。 134891011125672圖圖3-8 深度為深度為4的完全二叉樹的完全二叉樹第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) 12345678910 11 12(a)102000(c)3123(b)圖圖3-10 二叉樹的順序存儲結(jié)構(gòu)二叉

15、樹的順序存儲結(jié)構(gòu)在最壞情況下，一個深度為在最壞情況下，一個深度為k且只有且只有k個結(jié)點個結(jié)點的單支樹的單支樹(樹中樹中無度為無度為2的結(jié)點的結(jié)點)卻需要卻需要2k 1個存儲單元。浪費個存儲單元。浪費很大。很大。所以，所以，一般用鏈表來表示二叉樹一般用鏈表來表示二叉樹。第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) 2 二叉樹的鏈式存儲結(jié)構(gòu)二叉樹的鏈式存儲結(jié)構(gòu)二叉鏈表二叉鏈表lchild datarchild結(jié)點結(jié)構(gòu)的直觀形式結(jié)點結(jié)構(gòu)的直觀形式1：鏈表中每個結(jié)點由數(shù)據(jù)域鏈表中每個結(jié)點由數(shù)據(jù)域(data)、左指針、左指針域域(lchild)及右指針及右指針(rchild)構(gòu)成。這種存構(gòu)成。這種存儲結(jié)

16、構(gòu)又稱為二叉鏈表。儲結(jié)構(gòu)又稱為二叉鏈表。結(jié)點的結(jié)構(gòu)結(jié)點的結(jié)構(gòu)1：圖圖3-11 二叉樹及其二叉鏈表存儲結(jié)構(gòu)二叉樹及其二叉鏈表存儲結(jié)構(gòu)(a）ABCDEFABDEFCroot(b）第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) 為便于找到結(jié)點的雙親，還可增加一個指為便于找到結(jié)點的雙親，還可增加一個指向其雙親的指針向其雙親的指針域域(parent)。由這種結(jié)點結(jié)構(gòu)所得的二叉樹由這種結(jié)點結(jié)構(gòu)所得的二叉樹存儲結(jié)構(gòu)稱為存儲結(jié)構(gòu)稱為三叉鏈表。三叉鏈表。lchilddataparentrchild結(jié)點的結(jié)構(gòu)結(jié)點的結(jié)構(gòu)2：結(jié)點結(jié)構(gòu)的直觀形式結(jié)點結(jié)構(gòu)的直觀形式2：第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) 圖圖3-

17、12 二叉樹及三叉鏈表存儲結(jié)構(gòu)二叉樹及三叉鏈表存儲結(jié)構(gòu)(a)ABCDEF三叉鏈表三叉鏈表(b)第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) 3.3 二叉樹的遍歷 遍歷二叉樹遍歷二叉樹就是按一定的次序，系統(tǒng)就是按一定的次序，系統(tǒng)地訪問樹中的所有結(jié)點，使每個結(jié)點恰好地訪問樹中的所有結(jié)點，使每個結(jié)點恰好被訪問一次。被訪問一次。所謂訪問結(jié)點，其含義是很所謂訪問結(jié)點，其含義是很廣的，可以理解為對結(jié)點的增、刪、修改廣的，可以理解為對結(jié)點的增、刪、修改等各種運算的抽象。在本節(jié)討論中，假定等各種運算的抽象。在本節(jié)討論中，假定訪問結(jié)點即為輸出結(jié)點數(shù)據(jù)域值。二叉樹訪問結(jié)點即為輸出結(jié)點數(shù)據(jù)域值。二叉樹的遍歷是最重要

18、和最基本的運算，二叉樹的遍歷是最重要和最基本的運算，二叉樹的許多操作都是以遍歷為基礎(chǔ)的。的許多操作都是以遍歷為基礎(chǔ)的。 遍歷的含義：遍歷的含義：指沿某條搜索路線，依次訪問數(shù)據(jù)結(jié)構(gòu)中的全部結(jié)點，指沿某條搜索路線，依次訪問數(shù)據(jù)結(jié)構(gòu)中的全部結(jié)點，而且每個結(jié)點只被訪問一次。而且每個結(jié)點只被訪問一次。二叉樹的遍歷：二叉樹的遍歷：是指依次遍歷根結(jié)點、左子樹及右子樹。是指依次遍歷根結(jié)點、左子樹及右子樹。對于線性結(jié)構(gòu)來說，因此只需從開始結(jié)點順序掃描每對于線性結(jié)構(gòu)來說，因此只需從開始結(jié)點順序掃描每個結(jié)點即可。但是二叉樹為非線性結(jié)構(gòu)，每個結(jié)點最個結(jié)點即可。但是二叉樹為非線性結(jié)構(gòu)，每個結(jié)點最多可有兩個后繼，因此多可

19、有兩個后繼，因此必須人為設(shè)定遍歷路徑必須人為設(shè)定遍歷路徑！以以D，L，R分別表示分別表示訪問根結(jié)點、遍歷左訪問根結(jié)點、遍歷左子樹，遍歷右子樹子樹，遍歷右子樹DLR，LDR，LRD，DRL，RDL，RLD排列排列組合組合 DLR，LDR，LRD 規(guī)定先左后右規(guī)定先左后右三種基本遍歷方法：三種基本遍歷方法：uDLR：先序遍歷先序遍歷uLDR：中序遍歷中序遍歷uLRD：后序遍歷后序遍歷第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) 二叉鏈表的二叉鏈表的C語言描述如下：語言描述如下：struct tnode int data;struct tnode *lchild, *rchild;typedef s

20、truct tnode TNODE;第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) 算法算法3-1 先序遍歷根結(jié)點指針為先序遍歷根結(jié)點指針為bt的二叉樹。的二叉樹。void preorder(TNODE *bt)if (bt != NULL) printf(%d n, bt-data); preorder(bt-lchild); preorder(bt-rchild);根據(jù)先序遍歷的定義，先序遍歷二叉樹的遞歸算法如下：根據(jù)先序遍歷的定義，先序遍歷二叉樹的遞歸算法如下：第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) 算法算法3-2 中序遍歷根結(jié)點指針為中序遍歷根結(jié)點指針為bt的二叉樹。的二叉樹。vo

21、id inorder(TNODE *bt)if (bt != NULL) inorder(bt-lchild); printf(%d n, bt-data); inorder(bt-rchild);根據(jù)中序遍歷的定義，中序遍歷二叉樹的遞歸算法如下：根據(jù)中序遍歷的定義，中序遍歷二叉樹的遞歸算法如下：第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) 算法算法3-3 后序遍歷根結(jié)點指針為后序遍歷根結(jié)點指針為bt的二叉樹。的二叉樹。void postorder(TNODE *bt)if (bt != NULL) postorder(bt-lchild); postorder(bt-rchild); pri

22、ntf(%d n, bt-data); 根據(jù)后序遍歷的定義，后序遍歷二叉樹的遞歸算法如下：根據(jù)后序遍歷的定義，后序遍歷二叉樹的遞歸算法如下：ABECFGD中序遍歷結(jié)果：中序遍歷結(jié)果：C B D A E G FLD RLD RLD RC nilnilBLD RD nilnilALD RELD RFLD RGnilnilnilnil先序遍歷結(jié)果：先序遍歷結(jié)果：后序遍歷結(jié)果：后序遍歷結(jié)果：A B C D E F GC D B G F E A下面重點以中序遍歷為例，討論二叉樹的遍歷算法。下面重點以中序遍歷為例，討論二叉樹的遍歷算法。第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) 算法算法3-4 中序遍歷

23、中序遍歷bt所指二叉樹，所指二叉樹，s為為存儲二叉樹結(jié)點指針的工作棧。存儲二叉樹結(jié)點指針的工作棧。 Step1. 初始化初始化 置堆棧置堆棧s為空，設(shè)置臨時為空，設(shè)置臨時指針變量指針變量p(btp)； Step2. 判定判定p=NULL 若若p=NULL，則，則執(zhí)行執(zhí)行Step4；上述示例給出了中序遍歷的非遞歸算法思路：利用一個輔上述示例給出了中序遍歷的非遞歸算法思路：利用一個輔助堆棧助堆棧S，可以寫出中序遍歷二叉樹的非遞歸算法。，可以寫出中序遍歷二叉樹的非遞歸算法。第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) Step3. P進棧進棧 將將p指針入棧，然后置指針入棧，然后置p = p-lch

24、ild，返回，返回Step2； Step4. 取棧頂元素，并退棧取棧頂元素，并退棧 若棧若棧s為空，為空，則算法結(jié)束，否則，將棧頂元素置指針變則算法結(jié)束，否則，將棧頂元素置指針變量量P； Step5. 訪問結(jié)點訪問結(jié)點p 訪問結(jié)點訪問結(jié)點P，然后置，然后置p = p-rchild，并返回，并返回Step2。 第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) #define N m/* m為二叉樹的結(jié)為二叉樹的結(jié)點個數(shù)點個數(shù)*/void inorderf(TNODE *pt)TNODE *p;TNODE *sN;int top=1; / Step1.p = bt; / Step1. while (p

25、!=NULL)|(top!= 1) / Step2. 如果設(shè)定棧如果設(shè)定棧s采用順序存儲結(jié)構(gòu)，則可給出采用順序存儲結(jié)構(gòu)，則可給出C語言描述如下。語言描述如下。第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) while (p!=NULL) / Step3. top+;stop=p;p=p-lchild; if (top!= 1) / Step4. p=stop; / Step5. top; p=p-rchild; printf(%dn, p-data);/先序遍歷先序遍歷第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) 分析此算法的運算量，假定二叉樹分析此算法的運算量，假定二叉樹T有有n個結(jié)點，每個結(jié)

26、點都要入棧和出棧一次。個結(jié)點，每個結(jié)點都要入棧和出棧一次。因此，入棧和出棧都要執(zhí)行因此，入棧和出棧都要執(zhí)行n次，對結(jié)點的次，對結(jié)點的訪問當(dāng)然也需執(zhí)行訪問當(dāng)然也需執(zhí)行n次。這樣，中序遍歷二次。這樣，中序遍歷二叉樹算法的時間復(fù)雜度為叉樹算法的時間復(fù)雜度為O(n)。 第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) 例例3-4 如圖如圖3-12所示的二叉樹表示下述表所示的二叉樹表示下述表達式：達式：a+b*ce/f 試寫出它的三種遍歷序列。試寫出它的三種遍歷序列。 解：解： 先序遍歷二叉樹，按訪問結(jié)先序遍歷二叉樹，按訪問結(jié)點的先后次序?qū)⒔Y(jié)點排列起來，點的先后次序?qū)⒔Y(jié)點排列起來，可得先序遍歷序列為：可得先

27、序遍歷序列為： +a*bc/ef中序遍歷序列為：中序遍歷序列為： a+b*ce/f后序遍歷序列為：后序遍歷序列為： abc*+ef/ 從表達式來看，以上三個序列恰好為表達式的前綴從表達式來看，以上三個序列恰好為表達式的前綴表示表示(波蘭式波蘭式)、中綴表示和后綴表示、中綴表示和后綴表示(逆波蘭式逆波蘭式)。/a*efbc圖圖3-12 二叉樹二叉樹 第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) 3.4 樹的存儲結(jié)構(gòu)和遍歷 樹在計算機內(nèi)存儲，可以用順序存儲樹在計算機內(nèi)存儲，可以用順序存儲方式、也可以用鏈式存儲方式，這主要取方式、也可以用鏈式存儲方式，這主要取決于要對樹結(jié)構(gòu)進行什么運算。決于要對樹結(jié)

28、構(gòu)進行什么運算。二叉樹的鏈式存儲結(jié)構(gòu)二叉樹的鏈式存儲結(jié)構(gòu)（1）從結(jié)點指針域的個數(shù)是否固定來區(qū)分：定長結(jié)點）從結(jié)點指針域的個數(shù)是否固定來區(qū)分：定長結(jié)點和不定長結(jié)點；和不定長結(jié)點；樹的鏈式分配樹的鏈式分配（2）從一個結(jié)點的各指針域存放的指針值的性質(zhì)來區(qū)）從一個結(jié)點的各指針域存放的指針值的性質(zhì)來區(qū)分：指向其所有孩子的多重鏈表和指向長子分：指向其所有孩子的多重鏈表和指向長子(最左邊的孩最左邊的孩子子)及次弟及次弟(右鄰的兄弟右鄰的兄弟)的二叉鏈表。的二叉鏈表。第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) 二叉鏈表表示法又稱二叉樹表示法，或二叉鏈表表示法又稱二叉樹表示法，或孩子兄弟表示法。即以二叉鏈表作

29、為樹的存孩子兄弟表示法。即以二叉鏈表作為樹的存儲結(jié)構(gòu)。鏈表中結(jié)點的兩個指針域分別指向儲結(jié)構(gòu)。鏈表中結(jié)點的兩個指針域分別指向該結(jié)點的第一個孩子和下一個兄弟結(jié)點。該結(jié)點的第一個孩子和下一個兄弟結(jié)點。 1二叉鏈表表示法二叉鏈表表示法childdatabrother圖圖3-13是一棵樹，該樹的二叉鏈表如圖是一棵樹，該樹的二叉鏈表如圖3-14所示。利用這種所示。利用這種存儲結(jié)構(gòu)便于實現(xiàn)各種樹的操作，首先易于實現(xiàn)找結(jié)點孩子存儲結(jié)構(gòu)便于實現(xiàn)各種樹的操作，首先易于實現(xiàn)找結(jié)點孩子等的操作，如果再為每個結(jié)點增設(shè)一個等的操作，如果再為每個結(jié)點增設(shè)一個PARENT域，則同樣域，則同樣能方便地實現(xiàn)求某結(jié)點雙親的操作。能

30、方便地實現(xiàn)求某結(jié)點雙親的操作。二叉鏈表結(jié)點的直觀表示：二叉鏈表結(jié)點的直觀表示：第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) ABCDHEGIF圖圖3-13 樹樹ABCEDFHGI圖圖3-14 圖圖3-13中樹的二叉鏈表中樹的二叉鏈表第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) (2) 后序遍歷樹：后序遍歷樹：先從左到右依次后根遍歷先從左到右依次后根遍歷每棵子樹，然后訪問根結(jié)點。如后序遍歷圖每棵子樹，然后訪問根結(jié)點。如后序遍歷圖3-13所示的樹，得到的結(jié)點序列為：所示的樹，得到的結(jié)點序列為：D G H I E B F C A。 2樹的遍歷樹的遍歷次序：先序遍歷樹和次序：先序遍歷樹和 后序遍歷樹后

31、序遍歷樹(1) 先序遍歷樹：先序遍歷樹：先訪問樹的根結(jié)點，然后從先訪問樹的根結(jié)點，然后從左到右依次先序遍歷根的每棵子樹。如先序遍左到右依次先序遍歷根的每棵子樹。如先序遍歷圖歷圖3-13所示的樹，得到的結(jié)點序列為：所示的樹，得到的結(jié)點序列為：A B D E G H I C F。第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) 3.5 樹、森林與二叉樹的轉(zhuǎn)換 由于二叉樹和樹都可用二叉鏈表作為存由于二叉樹和樹都可用二叉鏈表作為存儲結(jié)構(gòu)，則以二叉鏈表作為媒介可導(dǎo)出樹與二儲結(jié)構(gòu)，則以二叉鏈表作為媒介可導(dǎo)出樹與二叉樹之間的一個對應(yīng)關(guān)系。叉樹之間的一個對應(yīng)關(guān)系。第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) AB

32、CDEABEDC樹對應(yīng)二叉樹存儲存儲ABCDEECBDABCEDA解釋解釋圖圖3-15 樹與二叉樹樹與二叉樹的對應(yīng)關(guān)系的對應(yīng)關(guān)系第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) 步驟： (1) 加線：加線：親兄弟之間加一虛連線。親兄弟之間加一虛連線。 (2) 抹線：抹線：抹掉抹掉(除最左一個孩子外除最左一個孩子外)該結(jié)該結(jié)點到其余孩子之間的連線。點到其余孩子之間的連線。 (3) 旋轉(zhuǎn)：旋轉(zhuǎn)：新加上去的虛線改實線且均新加上去的虛線改實線且均向右斜向右斜(rchild)，原有的連線均，原有的連線均向左向左斜斜(lchild)。1一般樹轉(zhuǎn)換為二叉樹一般樹轉(zhuǎn)換為二叉樹第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)

33、據(jù)結(jié)構(gòu) 例例3-5 將圖將圖3-16(a)所示的一般樹轉(zhuǎn)換所示的一般樹轉(zhuǎn)換為二叉樹。為二叉樹。 解：轉(zhuǎn)換過程如圖解：轉(zhuǎn)換過程如圖3-16(a)、(b)、(c)、(d)所示所示(a)(b)(c)(d)加線加線抹線抹線旋轉(zhuǎn)旋轉(zhuǎn)圖圖3-16 一般樹轉(zhuǎn)換為二叉樹的操作過程一般樹轉(zhuǎn)換為二叉樹的操作過程(a) 一般樹；一般樹；(b) 加線后；加線后；(c) 抹線后；抹線后；(d) 旋轉(zhuǎn)后旋轉(zhuǎn)后第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) 步驟：步驟： (1) 將各棵樹分別轉(zhuǎn)換為二叉樹。將各棵樹分別轉(zhuǎn)換為二叉樹。 (2) 按給出森林中樹的次序，依次將后一棵按給出森林中樹的次序，依次將后一棵二叉樹作為前一棵二

34、叉樹根結(jié)點的右子樹，則二叉樹作為前一棵二叉樹根結(jié)點的右子樹，則第一棵樹的根結(jié)點是轉(zhuǎn)換后二叉樹的根。第一棵樹的根結(jié)點是轉(zhuǎn)換后二叉樹的根。2森林轉(zhuǎn)換為二叉樹森林轉(zhuǎn)換為二叉樹森林是樹的有限集合，利用樹的轉(zhuǎn)換思想，森林是樹的有限集合，利用樹的轉(zhuǎn)換思想，可以實現(xiàn)森林到二叉樹的轉(zhuǎn)換可以實現(xiàn)森林到二叉樹的轉(zhuǎn)換。第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) 例例3-6 將圖將圖3-17(a)的森林轉(zhuǎn)換成二叉的森林轉(zhuǎn)換成二叉樹樹 解：轉(zhuǎn)換過程如圖解：轉(zhuǎn)換過程如圖3-17(b)、(c)所示。所示。(a) 例例3-6 將圖將圖3-17(a)的森林轉(zhuǎn)換成二叉樹的森林轉(zhuǎn)換成二叉樹(a) 森林森林(b)各棵數(shù)對應(yīng)的二叉樹

35、各棵數(shù)對應(yīng)的二叉樹(c)轉(zhuǎn)換成的二叉樹轉(zhuǎn)換成的二叉樹圖圖3-17森林轉(zhuǎn)換成對應(yīng)的二叉樹的過程森林轉(zhuǎn)換成對應(yīng)的二叉樹的過程第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) 思考：思考：將如下二叉樹轉(zhuǎn)換成森林？轉(zhuǎn)換結(jié)果唯一嗎？123645897第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) 結(jié)點間的路徑長度：結(jié)點間的路徑長度：從樹中一個結(jié)點到從樹中一個結(jié)點到另一個結(jié)點之間的分支構(gòu)成這兩個結(jié)點之另一個結(jié)點之間的分支構(gòu)成這兩個結(jié)點之間的路徑，路徑上的分支數(shù)稱為這兩個結(jié)間的路徑，路徑上的分支數(shù)稱為這兩個結(jié)點之間的路徑長度。點之間的路徑長度。霍夫曼樹霍夫曼樹(Huffman Tree)，又稱最優(yōu)樹，是一類帶權(quán)，

36、又稱最優(yōu)樹，是一類帶權(quán)路徑長度最短的樹。路徑長度最短的樹。1樹的路徑長度和帶權(quán)路徑長度樹的路徑長度和帶權(quán)路徑長度 樹的路徑長度：樹的路徑長度：從樹根到樹中每一個結(jié)點的路徑長度從樹根到樹中每一個結(jié)點的路徑長度之和稱為樹的路徑長度，一般記作之和稱為樹的路徑長度，一般記作PL。3.6 霍夫曼樹及其應(yīng)用霍夫曼樹及其應(yīng)用第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) 如圖如圖3-18所示的兩棵二叉樹，其路徑長度分別計所示的兩棵二叉樹，其路徑長度分別計算如算如下：下： (a) PL=0+1+1+2+2+2+2+3=13 (b) PL=0+1+1+2+2+2+3=11187654321765432(a)(b)

37、第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) 容易知道，對于有容易知道，對于有n個結(jié)點的所有二叉樹而言，個結(jié)點的所有二叉樹而言，滿二叉樹或者完全二叉樹具有最小的路徑長度。滿二叉樹或者完全二叉樹具有最小的路徑長度。 我們把路徑長度的概念推廣到帶權(quán)的路徑長我們把路徑長度的概念推廣到帶權(quán)的路徑長度度(Weighted Path Length)。niii 1WPLWL注意：只有葉子節(jié)點有權(quán)值注意：只有葉子節(jié)點有權(quán)值第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) 則它們的帶權(quán)路徑長度分別為則它們的帶權(quán)路徑長度分別為 (a) WPL = 2*2 + 4*2 + 6*2 + 8*2 = 40 (b) WPL

38、= 4*2 + 6*3 + 8*3 + 2*1 = 52 (c) WPL = 8*1 + 6*2 + 4*3 + 2*3 = 38246824688642(a)(b)(c)第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) 由此可見，帶權(quán)路徑長度最小的二叉樹不由此可見，帶權(quán)路徑長度最小的二叉樹不一定是完全二叉樹。通常，在帶權(quán)路徑長度最一定是完全二叉樹。通常，在帶權(quán)路徑長度最小的二叉樹中，權(quán)值越大的終端結(jié)點離二叉樹小的二叉樹中，權(quán)值越大的終端結(jié)點離二叉樹的根越近。的根越近。第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) 給定：給定：一組權(quán)值一組權(quán)值W1，W2，Wn 構(gòu)造：構(gòu)造：一棵有一棵有n個葉子結(jié)點的

39、最小帶權(quán)個葉子結(jié)點的最小帶權(quán)路徑長度的二叉樹，即路徑長度的二叉樹，即霍夫曼樹霍夫曼樹或者最優(yōu)二叉或者最優(yōu)二叉樹，相應(yīng)的算法稱為霍夫曼算法。樹，相應(yīng)的算法稱為霍夫曼算法。2霍夫曼樹和霍夫曼編碼霍夫曼樹和霍夫曼編碼第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) (1) 給定的權(quán)值為給定的權(quán)值為W1，W2，Wn，據(jù)此，據(jù)此生成森林生成森林F=T1，T2，Tn (2) 在在F中選取兩棵根結(jié)點的權(quán)值中選取兩棵根結(jié)點的權(quán)值最小最小和和次小次小的二叉樹的二叉樹作為左、右子樹作為左、右子樹構(gòu)造一棵新的二叉樹，構(gòu)造一棵新的二叉樹，新二叉樹根結(jié)點的權(quán)值為其左、右子樹根結(jié)點的新二叉樹根結(jié)點的權(quán)值為其左、右子樹根結(jié)點的

40、權(quán)值之和。權(quán)值之和。 (3) 在在F中刪除這兩棵權(quán)值最小和次小的二叉中刪除這兩棵權(quán)值最小和次小的二叉樹，同時將新生成的二叉樹并入森林樹，同時將新生成的二叉樹并入森林F中。中。 (4) 重復(fù)重復(fù)(2)和和(3)，直到，直到F中只有一棵二叉樹為中只有一棵二叉樹為止。止。第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) 例如，給定一組權(quán)值例如，給定一組權(quán)值2，7，4，8，圖，圖3-20給出了構(gòu)造相應(yīng)給出了構(gòu)造相應(yīng)霍夫曼樹的過程?；舴蚵鼧涞倪^程。2748786248624137862413217(a)(b)(c)(d)圖圖3-20 霍夫曼樹的構(gòu)造過程霍夫曼樹的構(gòu)造過程第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)

41、據(jù)結(jié)構(gòu) 霍夫曼樹應(yīng)用：霍夫曼樹應(yīng)用：信息編碼，判定過程，排序過程 （1）信息編碼中權(quán)值可看成是某個符號出現(xiàn)的頻率； （2）判定過程中，權(quán)值可看成是某類數(shù)據(jù)出現(xiàn)的頻率； （3）排序過程中，權(quán)值可看成是已排好次序而待合并的序列的長度等。第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) 不等長二進制前綴編碼：不等長二進制前綴編碼： 在信息通信中，以字符傳送為主。眾所周知，字符集中的每個字符使用的頻率是不等的。如果能讓使用頻率較高的字符的編碼盡可能短，這樣就可以縮短整個信息通信過程中所需傳送的二進制編碼序列的長度，從而達到節(jié)省通信資源的目的。第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) 問題：問題：設(shè)D=

42、d1，d2，dn 為需要編碼的字符集合。又設(shè)Wi為di在文本中出現(xiàn)的次數(shù)，現(xiàn)要求對D進行二進制編碼。 第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) 解決方法解決方法：以Wi為權(quán)值構(gòu)造霍夫曼樹。在生成的霍夫曼樹中，令所有的左分支取編碼為0，令所有的右分支取編碼為1，將從根結(jié)點出發(fā)到葉子結(jié)點的路徑上各左、右分支的編碼順序排列就得到了該葉子結(jié)點所對應(yīng)的字符的二進制前綴編碼，也稱為霍夫曼編碼。第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) 例例 給出下面一個文本： CAST CATS SAT AT A TASA 則有D=C，A，S，T、W=2，7，4，5，得到D中每個字符的二進制前綴編碼為 C：110S

43、：111 A：0 T：10576241118010101霍夫曼樹霍夫曼樹第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) 可以看出，出現(xiàn)次數(shù)最多的字符，其編碼位數(shù)最少。相應(yīng)文本的編碼為 110011110 110010111111010 010 0 1001110 21543圖圖3-22 無向圖無向圖（1）圖）圖：是由頂點集合和頂點間：是由頂點集合和頂點間關(guān)系組成，記作關(guān)系組成，記作 G=（V，R）。）。V為頂點集合，為頂點集合，V= v1，v2，vn 。R是兩個頂點之間的關(guān)系的集合。是兩個頂點之間的關(guān)系的集合。（2）無向圖）無向圖：當(dāng)圖中頂點之間：當(dāng)圖中頂點之間關(guān)系為無序時，稱為無向圖。關(guān)系為無

44、序時，稱為無向圖。 特點：特點：(Vi,Vj)=(Vj,Vi)，稱為邊，稱為邊。無向圖記作無向圖記作G（V，E）。）。V=（v1，v2，v3，v4，v5）E= (v1,v2)，(v1,v3)，(v1,v4)，(v2,v3)，(v3,v5) 對圖對圖3-22：3.7 圖及其基本概念圖及其基本概念1324圖圖3-23 有向有向圖圖（3）有向圖）有向圖：當(dāng)圖中頂點之間當(dāng)圖中頂點之間關(guān)系為有序時，稱為有向圖。關(guān)系為有序時，稱為有向圖。V=（v1，v2，v3，v4）E= ， 圖中有序?qū)D中有序?qū)ΨQ為弧，其中稱為弧，其中Vi為弧尾為弧尾(起始點起始點)，Vj為弧頭為弧頭(終點終點)。此時。此時 。有向圖。

45、有向圖記作記作G（V，A）。）。3.7 圖及其基本概念圖及其基本概念第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) （4）子圖：）子圖：設(shè)有兩個圖設(shè)有兩個圖GA和和GB，且滿足，且滿足 V(GB) V(GA) E(GB) E(GA)則稱則稱GB是是GA的子圖。如圖的子圖。如圖3-24所示。所示。132112132132G3G3的子圖 圖圖3-24 圖與子圖圖與子圖 第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) （5）帶權(quán)圖帶權(quán)圖：無向圖中每條邊附一：無向圖中每條邊附一個對應(yīng)的數(shù)（權(quán)），該圖為帶權(quán)圖。個對應(yīng)的數(shù)（權(quán)），該圖為帶權(quán)圖。14235915251030 圖圖3-25帶權(quán)圖帶權(quán)圖 (網(wǎng)網(wǎng))（

46、6）路徑）路徑：圖中一個頂點的序：圖中一個頂點的序列稱路徑。如列稱路徑。如v到到v的路徑為的路徑為(V = Vi0，Vi1，Vi2，Vin = V)，都屬于集合都屬于集合E。路徑上弧的數(shù)目。路徑上弧的數(shù)目稱為該路徑的長度。稱為該路徑的長度。 在在無向圖無向圖中，若每一對頂點之間都有路徑，中，若每一對頂點之間都有路徑，則稱此圖為則稱此圖為連通圖連通圖。 在在有向圖有向圖中，若每一對頂點中，若每一對頂點u和和v之間都存在之間都存在v到到u及及u到到v的路徑，則稱此圖為的路徑，則稱此圖為強連通圖強連通圖。第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) （7）鄰接點）鄰接點：在在無向圖無向圖中，如果邊中

47、，如果邊 (u,v)E，則，則u和和v互為鄰結(jié)點，即互為鄰結(jié)點，即u是是v的鄰結(jié)點，的鄰結(jié)點，v也是也是u的鄰結(jié)點。的鄰結(jié)點。 在在有向圖有向圖中，如果弧中，如果弧E，則，則v是是u的鄰結(jié)點。稱的鄰結(jié)點。稱u鄰接到鄰接到v，或頂點，或頂點v鄰接自頂點鄰接自頂點u。(8) 頂點的度：頂點的度：在在無向圖無向圖中，頂點中，頂點的度就是和該頂點相關(guān)聯(lián)的邊的數(shù)的度就是和該頂點相關(guān)聯(lián)的邊的數(shù)目，記為目，記為TD(V)。如圖。如圖3-22中，中，TD(V3)=3。21543圖圖3-221324圖圖3-23第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) 入度、出度入度、出度：在：在有向圖有向圖中，以某頂點為尾

48、的（初中，以某頂點為尾的（初始點）的弧的數(shù)目稱為該頂點的出度；而以該頂始點）的弧的數(shù)目稱為該頂點的出度；而以該頂點為頭（終端點）的弧的數(shù)目稱為該頂點的入度。點為頭（終端點）的弧的數(shù)目稱為該頂點的入度。圖圖3-23中，中，ID(V3)=1, OD(V3)=1,TD(V3)= ID(V3)+ OD(V3)=2。1324圖圖3-23第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) 3.8 圖的存儲結(jié)構(gòu) 要求：要求：掌握鄰接矩陣表示法和鄰接表表示法。掌握鄰接矩陣表示法和鄰接表表示法。 需在計算機中存儲：需在計算機中存儲：（1）圖的頂點的集合；）圖的頂點的集合；（2）頂點之間的聯(lián)系，即邊或弧的集合。）頂點之

49、間的聯(lián)系，即邊或弧的集合。3.8.1 鄰接矩陣鄰接矩陣第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) （1）用一維數(shù)組存放圖中所有頂點的信息；）用一維數(shù)組存放圖中所有頂點的信息；（2）用一個二維數(shù)組來存放數(shù)據(jù)元素之間的關(guān)）用一個二維數(shù)組來存放數(shù)據(jù)元素之間的關(guān)系的信息系的信息(即邊或弧的集合即邊或弧的集合E)。這個二維數(shù)組稱。這個二維數(shù)組稱之為之為鄰接矩陣鄰接矩陣。解決辦法：解決辦法：第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) 鄰接矩陣是表示頂點之間的鄰接關(guān)系的矩鄰接矩陣是表示頂點之間的鄰接關(guān)系的矩陣。陣。設(shè)設(shè)G =(V，E)是有是有n(n1)個頂點的圖，則個頂點的圖，則G的鄰接矩陣的鄰接矩陣A

50、是一個具有下列性質(zhì)的是一個具有下列性質(zhì)的nn階階矩陣：矩陣：ijij1 (V, V ) V, VE(G)Ai, j0 反之若若若將頂點編號為若將頂點編號為1Vtxnum，設(shè)弧上或邊上無權(quán)，設(shè)弧上或邊上無權(quán)值，則圖的存儲結(jié)構(gòu)可以簡化為用一個二維數(shù)組值，則圖的存儲結(jié)構(gòu)可以簡化為用一個二維數(shù)組表示：表示： int adjmatrixvtxnumvtxnum； 第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) 0 0 1 0 00 0 0 0 11 0 0 1 10 0 1 0 10 1 1 1 01 2 3 4 5 123450 0 0 11 0 0 00 0 0 00 1 1 01 2 3 4 123

51、4215431324圖圖3-26 圖與鄰接矩陣之間的轉(zhuǎn)換圖與鄰接矩陣之間的轉(zhuǎn)換第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) 借助于接矩陣，能夠判定任意兩個頂點之間借助于接矩陣，能夠判定任意兩個頂點之間是否有邊（?。┫噙B，亦能求得各個頂點的是否有邊（?。┫噙B，亦能求得各個頂點的度。度。 （1）在）在無向圖無向圖中，頂點的中，頂點的度度是鄰接矩陣中是鄰接矩陣中該點所在該點所在行行（列）的元素之和；（列）的元素之和； （2）在）在有向圖有向圖中，頂點的中，頂點的出度是出度是該頂點所該頂點所在在行行的元素之的元素之和和，頂點的，頂點的入度是入度是頂點所在頂點所在列列的元素之的元素之和和。第第3 3章章

52、 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) 網(wǎng)的鄰接矩陣可定義為：網(wǎng)的鄰接矩陣可定義為：ijijijW (V, V ) V, VE(G)Ai, j 若或反之其中其中Wij是邊是邊(Vi, Vj)或弧或弧上的權(quán)值。上的權(quán)值。第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) 鄰接表包括兩個部分：一部分是鏈表；另鄰接表包括兩個部分：一部分是鏈表；另一部分是向量。一部分是向量。adjvexdatanextarc頂點Vi的下一鄰接點地址權(quán)值頂點Vi的鄰接點在圖中的位置3.8.2 鄰接表鄰接表 在鄰接表中，對圖中每個頂點建立一個單鏈在鄰接表中，對圖中每個頂點建立一個單鏈表，第表，第i個單鏈表中的結(jié)點包含了頂點個單鏈表中的

53、結(jié)點包含了頂點Vi的所有鄰的所有鄰接頂點。接頂點。結(jié)點結(jié)構(gòu)：結(jié)點結(jié)構(gòu)：第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) 為便于鄰接表操作，在每個單鏈表為便于鄰接表操作，在每個單鏈表上附設(shè)一個頭結(jié)點。上附設(shè)一個頭結(jié)點。vexdatafirstarc頂點Vi的名字或位置頂點Vi的第一個鄰接點地址頭結(jié)點結(jié)構(gòu)：頭結(jié)點結(jié)構(gòu)：第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) 鄰接表中將每個單鏈表的鄰接表中將每個單鏈表的頭結(jié)點以順序結(jié)頭結(jié)點以順序結(jié)構(gòu)構(gòu)的形式存儲的形式存儲，鄰接表的存儲結(jié)構(gòu)可以用鄰接表的存儲結(jié)構(gòu)可以用C語言描述如下：語言描述如下： #define VTXUNM n /*n為圖中頂點個數(shù)的最大可能值*

54、/第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) struct arcnode int adjvex; float data;struct arcnode *nextarc; ;typedef struct arcnode ARCNODE;struct headnode int vexdata;ARCNODE *firstarc;adjlistVTXUNM;/*頂點頂點Vi的鄰結(jié)點在圖中的位置為整數(shù)的鄰結(jié)點在圖中的位置為整數(shù) */*結(jié)點數(shù)據(jù)類型結(jié)點數(shù)據(jù)類型*/*將結(jié)點將結(jié)點arcnode重新命名為重新命名為 ARCNODE */*定義鄰接表數(shù)組定義鄰接表數(shù)組adjlist*/第第3 3章章 非線

55、性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) 對于圖對于圖3-29中的圖中的圖G4和圖和圖3-30中的圖中的圖G5，其鄰接表存儲結(jié)構(gòu)如圖其鄰接表存儲結(jié)構(gòu)如圖3-29(b)和圖和圖3-30(b)所示。所示。231231437ABCABC734(a)(b)圖圖3-29 有向帶權(quán)圖及其鄰接表有向帶權(quán)圖及其鄰接表第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) 42123123124(a)(b)3413412412343圖圖3-30 無向圖及其鄰接表無向圖及其鄰接表 第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) 鄰接表優(yōu)點：鄰接表優(yōu)點：容易找到任一頂點的第一容易找到任一頂點的第一個鄰接點和下一個鄰接點個鄰接點和下一個鄰接點

56、鄰接表缺點：鄰接表缺點：要判定任意兩個頂點要判定任意兩個頂點(Vi和和Vj)之間是否有邊或弧相連，則需搜索第之間是否有邊或弧相連，則需搜索第i個個或第或第j個鏈表，因此不及鄰接矩陣方便。個鏈表，因此不及鄰接矩陣方便。 注意注意：（1）鄰接表不惟一；鄰接表不惟一；（2）對于）對于有向圖有向圖，其鄰接表中第，其鄰接表中第i個單鏈個單鏈表的結(jié)點個數(shù)就是此結(jié)點的出度；對于表的結(jié)點個數(shù)就是此結(jié)點的出度；對于無無向圖向圖，其鄰接表中第，其鄰接表中第i個單鏈表的結(jié)點個數(shù)個單鏈表的結(jié)點個數(shù)就是此結(jié)點的度。就是此結(jié)點的度。第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) 3.9 圖 的 遍 歷 和樹的遍歷類似，從圖

57、中某一頂點出發(fā)和樹的遍歷類似，從圖中某一頂點出發(fā)訪問圖中其余的頂點，使每個頂點都被訪問且訪問圖中其余的頂點，使每個頂點都被訪問且僅被訪問一次，這個過程就叫做圖的遍歷僅被訪問一次，這個過程就叫做圖的遍歷(traversing graph)。要求：要求：能寫圖出的深度優(yōu)先搜索和廣度優(yōu)先搜索能寫圖出的深度優(yōu)先搜索和廣度優(yōu)先搜索的序列的序列第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) 同一頂點可能被訪問多次，因此，在遍同一頂點可能被訪問多次，因此，在遍歷圖的過程中，必須記下每個已訪問過的頂點。歷圖的過程中，必須記下每個已訪問過的頂點。 為此，設(shè)一個輔助數(shù)組為此，設(shè)一個輔助數(shù)組visitedn，它，它的

58、初值為的初值為“假假”或者零，一旦訪問了頂點或者零，一旦訪問了頂點Vi，便置便置visitedi為為“真真”或者為被訪問時的次或者為被訪問時的次序號。序號。 通常有兩種遍歷圖的方法：通常有兩種遍歷圖的方法： （1）深度優(yōu)先搜索；）深度優(yōu)先搜索； （2）廣度優(yōu)先搜索。）廣度優(yōu)先搜索。 第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) 算法步驟：算法步驟： (1) 首先訪問圖首先訪問圖G的的指定起始點指定起始點V0； (2) 從從V0出發(fā)，訪問一個與出發(fā)，訪問一個與V0鄰接的頂點鄰接的頂點W1后，再從后，再從W1出發(fā)，訪問與出發(fā)，訪問與W1鄰接且未被鄰接且未被訪問過的頂點訪問過的頂點W2。從。從W2出

59、發(fā)，重復(fù)上述過程，出發(fā)，重復(fù)上述過程，直到遇到一個所有與之鄰接的頂點均被訪問直到遇到一個所有與之鄰接的頂點均被訪問過的頂點為止；過的頂點為止； 1深度優(yōu)先搜索深度優(yōu)先搜索圖的深度優(yōu)先搜索遍歷圖的深度優(yōu)先搜索遍歷(depth-first search)類似于樹的類似于樹的先序遍歷，是樹的先序遍歷的推廣。先序遍歷，是樹的先序遍歷的推廣。第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) (3) 沿著剛才訪問的次序，反向回退到沿著剛才訪問的次序，反向回退到尚有未被訪問過的鄰接點的頂點，從該頂尚有未被訪問過的鄰接點的頂點，從該頂點出發(fā)，重復(fù)步驟點出發(fā)，重復(fù)步驟(2)、(3)，直到所有被訪，直到所有被訪問過的

60、頂點的鄰接點都已被訪問過為止；問過的頂點的鄰接點都已被訪問過為止；若此時圖中尚有頂點未被訪問，則另選圖若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作起始點，重復(fù)中一個未曾被訪問的頂點作起始點，重復(fù)上述過程，直至圖中所有頂點都被訪問到上述過程，直至圖中所有頂點都被訪問到為止。為止。326451987遍歷結(jié)果：遍歷結(jié)果：3 2 4 9 1 65 8 7第第3 3章章 非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu) 顯然，這個遍歷過程是個遞歸過程。在設(shè)顯然，這個遍歷過程是個遞歸過程。在設(shè)計具體算法時，首先要確定圖的存儲結(jié)構(gòu)，下計具體算法時，首先要確定圖的存儲結(jié)構(gòu)，下面以鄰接表為例，討論深度優(yōu)先搜索法。面