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

非線性數(shù)據(jù)結(jié)構(gòu)第一頁(yè)，共一百頁(yè)，編輯于2023年，星期五3.1數(shù)組

3.1.1引言

數(shù)組是大家已經(jīng)很熟悉的一種數(shù)據(jù)類型，幾乎所有的程序設(shè)計(jì)語(yǔ)言都把數(shù)組類型設(shè)定為固有類型。

數(shù)組(array)可看成是線性表的推廣，是最常用的數(shù)據(jù)結(jié)構(gòu)之一。數(shù)組是有限個(gè)數(shù)組元素的集合；數(shù)組的每個(gè)元素與一組下標(biāo)相對(duì)應(yīng)；和線性表一樣，數(shù)組中所有數(shù)組元素的數(shù)據(jù)類型必須一致。

第二頁(yè)，共一百頁(yè)，編輯于2023年，星期五

3.1.2數(shù)組的邏輯結(jié)構(gòu)

邏輯關(guān)系是非線性的，實(shí)質(zhì)上是多個(gè)線性關(guān)系的組合。Amn=a11a12...a1na21a22...a2n

am1am2...amn

如下所示，就是一個(gè)m行n列的二維數(shù)組(也稱為矩陣)，記作A[m,n]。第三頁(yè)，共一百頁(yè)，編輯于2023年，星期五矩陣A可以看成是由m個(gè)行向量組成的向量，也可以看成是由n個(gè)列向量組成的向量。

在矩陣A中，每個(gè)元素aij都屬于兩個(gè)線性表。一個(gè)是第i行的行表(ai1，ai2，...，aij，...，ain)，另一個(gè)是第j列的列表(a1j，a2j，...，aij，...，amj)。這種行表(行向量)和列表(列向量)都相當(dāng)于線性表。所以說(shuō)，數(shù)組可看作是線性表的推廣，將線性表推廣到二維或高維，就是我們所說(shuō)的數(shù)組。第四頁(yè)，共一百頁(yè)，編輯于2023年，星期五

3.1.3數(shù)組的存儲(chǔ)結(jié)構(gòu)數(shù)組的順序分配就是用向量作為數(shù)組的存儲(chǔ)結(jié)構(gòu)。但是二維以上的多維數(shù)組，不像一維數(shù)組那樣，所有的元素已經(jīng)排成一個(gè)序列，所以要把多維數(shù)組順序地存儲(chǔ)到一維順序的存儲(chǔ)器中，則必須對(duì)多維數(shù)組里的元素存放順序做出一些規(guī)定。通常數(shù)組采用兩種順序存儲(chǔ)方式。第五頁(yè)，共一百頁(yè)，編輯于2023年，星期五

1)行優(yōu)先順序存儲(chǔ)

行優(yōu)先順序存儲(chǔ)就是數(shù)組元素按行表次序進(jìn)行存儲(chǔ)，即第i+1個(gè)行表緊跟在第i個(gè)行表后面進(jìn)行存儲(chǔ)。在C、BASIC、PASCAL、COBOL等高級(jí)語(yǔ)言中均采用這種方法。以二維數(shù)組Am×n為例，按行優(yōu)先順序存儲(chǔ)的數(shù)組元素次序?yàn)椋?/p>

a11，a12，…，a1n，a21，a22，…，a2n，…，am1，am2，…，amn

第六頁(yè)，共一百頁(yè)，編輯于2023年，星期五

2)列優(yōu)先順序存儲(chǔ)

列優(yōu)先順序存儲(chǔ)就是數(shù)組元素按列表次序進(jìn)行存儲(chǔ)，即第j+1個(gè)列表緊跟在第j個(gè)列表后面進(jìn)行存儲(chǔ)。在FORTRAN語(yǔ)言中，數(shù)組是按列優(yōu)先順序組織存儲(chǔ)。以二維數(shù)組Am×n為例，按列優(yōu)先順序存儲(chǔ)的數(shù)組元素次序?yàn)椋?/p>

a11，a21，…，am1，a12，a22，…，am2，…，a1n，a2n，…，amn

第七頁(yè)，共一百頁(yè)，編輯于2023年，星期五二維數(shù)組的兩種存儲(chǔ)方式第八頁(yè)，共一百頁(yè)，編輯于2023年，星期五同樣，對(duì)n維數(shù)組也有上述兩種不同的順序分配的存儲(chǔ)結(jié)構(gòu)。當(dāng)把n維數(shù)組的元素這樣順序地存放在存儲(chǔ)器里，則每個(gè)元素的存儲(chǔ)地址可以用公式計(jì)算出來(lái)。這些計(jì)算公式稱為“地址公式”。假設(shè)每個(gè)數(shù)據(jù)元素占k個(gè)存儲(chǔ)單元，則可得（1）一維數(shù)組的地址公式為：

Loc(ai)=Loc(a1)+(i-1)*k

（2）若存儲(chǔ)分配采用行優(yōu)先順序分配，則二維數(shù)組Am×n的地址公式為：

Loc(aij)=Loc(a11)+[(i-1)*n+(j-1)]*k第九頁(yè)，共一百頁(yè)，編輯于2023年，星期五同理，可寫(xiě)出三維數(shù)組、n維數(shù)組的數(shù)組元素存儲(chǔ)地址的計(jì)算公式。（3）若存儲(chǔ)分配采用列優(yōu)先順序分配，則二維數(shù)組Am×n的地址公式為：

Loc(aij)=Loc(a11)+[(j-1)*m+(i-1)]*L

同理，可寫(xiě)出三維數(shù)組、n維數(shù)組的數(shù)組元素存儲(chǔ)地址的計(jì)算公式。第十頁(yè)，共一百頁(yè)，編輯于2023年，星期五

3.1.4特殊矩陣的壓縮存儲(chǔ)

假若值相同的元素或零元素在矩陣中的分布有一定規(guī)律，則稱此類矩陣為特殊矩陣。像三角矩陣，對(duì)稱矩陣、三對(duì)角矩陣等都屬于特殊矩陣。通常在實(shí)際計(jì)算中經(jīng)常出現(xiàn)一些階數(shù)很高的矩陣，同時(shí)矩陣中有許多值相同的元素或者零元素。有時(shí)為了節(jié)省存儲(chǔ)空間，可以對(duì)這類矩陣進(jìn)行壓縮存儲(chǔ)。所謂壓縮存儲(chǔ)是指：為多個(gè)值相同的元素只分配一個(gè)存儲(chǔ)空間；對(duì)零元素不分配空間。第十一頁(yè)，共一百頁(yè)，編輯于2023年，星期五

1）三角矩陣?yán)合氯蔷仃嘇n×n，當(dāng)i<j時(shí)，aij=0。A=a110?…0a21a22…0

an1an2…ann

在下三角矩陣中，對(duì)角線以上元素全部為0，我們只需存儲(chǔ)下三角的元素。第十二頁(yè)，共一百頁(yè)，編輯于2023年，星期五

特殊矩陣的壓縮存儲(chǔ)實(shí)際上就是把二維數(shù)組的數(shù)據(jù)元素壓縮到一維數(shù)組上，即要在下標(biāo)[i,j]與下標(biāo)[k]之間建立一個(gè)映像關(guān)系，使得對(duì)二維數(shù)組的存取操作通過(guò)一維數(shù)組來(lái)完成。

假設(shè)以一維數(shù)組Sa(1：n(n+1)/2)作為n階下三角矩陣A的存儲(chǔ)結(jié)構(gòu)，則Sa[k]和矩陣元素aij之間存在著一一對(duì)應(yīng)關(guān)系：k=i（i-1）/2+j第十三頁(yè)，共一百頁(yè)，編輯于2023年，星期五

n階對(duì)稱矩陣A的壓縮存儲(chǔ)如下圖所示。Loc(aij)=Loc(a11)+i(i?1)/2+(j?1)其地址公式為：對(duì)稱矩陣A的壓縮存儲(chǔ)

第十四頁(yè)，共一百頁(yè)，編輯于2023年，星期五

2)稀疏矩陣

如果一個(gè)矩陣中大多數(shù)元素為零，非零元素較少且分布無(wú)一定規(guī)律，這類矩陣稱之為稀疏矩陣。在存儲(chǔ)稀疏矩陣時(shí)，為了節(jié)省存儲(chǔ)單元，很自然的方法就是只存非零元素。由于每個(gè)矩陣元素可由它的行號(hào)和列號(hào)惟一地確定，這樣稀疏矩陣中的每個(gè)非零元素就由一個(gè)三元組(i，j，val)惟一確定。其中，i是行號(hào)；j是列號(hào)；val是非零元的數(shù)值。整個(gè)稀疏矩陣可用一個(gè)三元組表表示。三元組表以非零元行號(hào)遞增的順序排列。第十五頁(yè)，共一百頁(yè)，編輯于2023年，星期五例如，有一個(gè)稀疏矩陣A如下：行號(hào)列號(hào)元素值46513315121234-6424第十六頁(yè)，共一百頁(yè)，編輯于2023年，星期五3.1.5數(shù)組的應(yīng)用——迷宮問(wèn)題0000011000010001101111011000011111100111011011010010101000001100110101000001100111011000100000110111001100001111110101000第十七頁(yè)，共一百頁(yè)，編輯于2023年，星期五i,j東k=0i=i,j=j+1南k=1i=i+1,j=j西k=2i=i,j=j-1北k=3i=i-1,j=jg=i+move[k][0]h=j+move[k][1]第十八頁(yè)，共一百頁(yè)，編輯于2023年，星期五3.2樹(shù)3.2.1引言

數(shù)（tree）是一種應(yīng)用廣泛的非線性數(shù)據(jù)結(jié)構(gòu)。從形態(tài)上看，它很類似與自然界中的數(shù)，是一個(gè)以分支關(guān)系定義的具有明顯層次結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)。樹(shù)結(jié)構(gòu)被廣泛應(yīng)用于分類、檢索、數(shù)據(jù)庫(kù)、人工智能等方面。第十九頁(yè)，共一百頁(yè)，編輯于2023年，星期五3.2.2樹(shù)的定義及邏輯結(jié)構(gòu)樹(shù)的定義樹(shù)(Tree)是n(n≥0)個(gè)結(jié)點(diǎn)的有限集合。當(dāng)n=0時(shí)稱為空樹(shù)，否則在任一非空樹(shù)中：

(1)有且僅有一個(gè)特定的稱為根的結(jié)點(diǎn)；

(2)除根結(jié)點(diǎn)之外，其余結(jié)點(diǎn)可分為m(m≥0)個(gè)互不相交的集合T1，T2，…，Tm，且其中每一個(gè)集合本身又是一棵樹(shù)，并且稱為根的子樹(shù)(SubTree)。

這是一個(gè)遞歸定義，即在樹(shù)的定義中又用到了樹(shù)，它顯示了樹(shù)的固有特性。樹(shù)中的每一個(gè)結(jié)點(diǎn)都是該樹(shù)中某一棵子樹(shù)的根。第二十頁(yè)，共一百頁(yè)，編輯于2023年，星期五

A為根結(jié)點(diǎn)，其余的結(jié)點(diǎn)分為三個(gè)互不相交的有限集合：

T1={B，E，F(xiàn)}，

T2={C，G，J}，

T3={D，H，I}。T1、T2和T3都是A的子樹(shù)，而它們本身也是一棵樹(shù)。例如，T1是一棵以B為根的樹(shù)，其余結(jié)點(diǎn)分為互不相交的兩個(gè)集合{E}和{F}，而{E}和{F}本身又是僅有一個(gè)根結(jié)點(diǎn)的樹(shù)。第二十一頁(yè)，共一百頁(yè)，編輯于2023年，星期五

2.常用術(shù)語(yǔ)

結(jié)點(diǎn)的度：一個(gè)結(jié)點(diǎn)擁有的子樹(shù)數(shù)目。如A結(jié)點(diǎn)的度為3，它有三個(gè)子樹(shù)T1、T2和T3。E、F結(jié)點(diǎn)的度為0，它們沒(méi)有子樹(shù)。

葉子：度為零的結(jié)點(diǎn)稱葉子或終端結(jié)點(diǎn)。 樹(shù)的度：一棵樹(shù)上所有結(jié)點(diǎn)的度的最大值就是這棵樹(shù)的度。 結(jié)點(diǎn)的層次：根結(jié)點(diǎn)的層數(shù)為1，其它任何結(jié)點(diǎn)的層數(shù)等于它的父結(jié)點(diǎn)的層數(shù)加1。

樹(shù)的深度：一棵樹(shù)中，結(jié)點(diǎn)的最大層次值就是樹(shù)的深度。下圖中樹(shù)的深度為4。

森林：森林是m(m≥0)棵互不相交的樹(shù)的集合。

孩子(child)：某結(jié)點(diǎn)子樹(shù)的根稱為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)。第二十二頁(yè)，共一百頁(yè)，編輯于2023年，星期五

雙親(parent)：一個(gè)結(jié)點(diǎn)是它的那些子樹(shù)的根的雙親結(jié)點(diǎn)。

兄弟(sibling)：同一個(gè)雙親的孩子之間互為兄弟。如A是B、C、D的雙親；B、C、D是A的孩子；B、C、D互為兄弟。

堂兄弟(cousins)：其雙親在同一層的結(jié)點(diǎn)互為堂兄弟。如G與E、F、H、I互為堂兄弟。

森林：有m(m≥0)棵互不相交的樹(shù)構(gòu)成的集合。

有序樹(shù)：樹(shù)中每個(gè)結(jié)點(diǎn)的各個(gè)子樹(shù)從左到右依次有序，即不能互換。

在計(jì)算機(jī)中表示一棵樹(shù)時(shí)，就隱含著一種確定的相對(duì)次序，所以后面我們討論的都是有序樹(shù)。第二十三頁(yè)，共一百頁(yè)，編輯于2023年，星期五3.2.3二叉樹(shù)

3.2.3.1二叉樹(shù)的定義及其性質(zhì)

1．二叉樹(shù)的定義二叉樹(shù)是一個(gè)有限結(jié)點(diǎn)的集合，該集合或者為空，或由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的被稱為該根的左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。這是一個(gè)遞歸定義，由定義可知二叉樹(shù)有下面兩個(gè)主要特點(diǎn)：

(1)每個(gè)結(jié)點(diǎn)最多只能有兩個(gè)孩子，即二叉樹(shù)中不存在度大于2的結(jié)點(diǎn)。

(2)有序樹(shù)，即每個(gè)結(jié)點(diǎn)的子樹(shù)有左、右之分，不能交換。第二十四頁(yè)，共一百頁(yè)，編輯于2023年，星期五二叉樹(shù)可以有五種基本形態(tài)

空樹(shù)、只有根結(jié)點(diǎn)、只有左子樹(shù)、只有右子樹(shù)和兼有左右子樹(shù)注意：樹(shù)和二叉樹(shù)的區(qū)別主要是二叉樹(shù)的結(jié)點(diǎn)的子樹(shù)要區(qū)分左子樹(shù)和右子樹(shù)，即使在結(jié)點(diǎn)只有一個(gè)子樹(shù)的情況下，也要明確指出該子樹(shù)是左子樹(shù)還是右子樹(shù)。第二十五頁(yè)，共一百頁(yè)，編輯于2023年，星期五2．二叉樹(shù)的性質(zhì)二叉樹(shù)具有下列重要特性。性質(zhì)1：在二叉樹(shù)中，第i層的結(jié)點(diǎn)數(shù)最多有2i-1(i≥1)個(gè)。例如：層次i 第i層最多結(jié)點(diǎn)數(shù)

120=1221=2322=4

k 2k?1

此性質(zhì)可以用數(shù)學(xué)歸納法證明。第二十六頁(yè)，共一百頁(yè)，編輯于2023年，星期五性質(zhì)2：在深度為k的二叉樹(shù)中結(jié)點(diǎn)總數(shù)最多有2k–1個(gè)。由性質(zhì)1可見(jiàn)，深度為k的二叉樹(shù)的最大結(jié)點(diǎn)數(shù)為：=2k?1性質(zhì)3：?對(duì)任何一棵二叉樹(shù)T，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。證明：

(1)

由于在二叉樹(shù)中，任一結(jié)點(diǎn)的度數(shù)小于或等于2，所以其結(jié)點(diǎn)總數(shù)

n=n0+n1+n2第二十七頁(yè)，共一百頁(yè)，編輯于2023年，星期五

(2)設(shè)B為二叉樹(shù)中總的分支數(shù)目，由于二叉樹(shù)中除了根結(jié)點(diǎn)之外，其余結(jié)點(diǎn)都有一個(gè)分支進(jìn)入，所以

B=n?1 即 n=B+1而這些分支只能是由度數(shù)為1或2的結(jié)點(diǎn)所發(fā)出，所以

B=n1+2n2于是得：

n=n1+2n2+1(3)由(1)和(2)得：

n0+n1+n2=n1+2n2+1所以

n0=n2+1 證畢第二十八頁(yè)，共一百頁(yè)，編輯于2023年，星期五3.2.3.2特殊的二叉樹(shù)1、滿二叉樹(shù)如果一棵二叉樹(shù)的深度為k，并且含有2k–1個(gè)結(jié)點(diǎn)，則稱此二叉樹(shù)為滿二叉樹(shù)。下圖是一棵深度為4的滿二叉樹(shù)。第二十九頁(yè)，共一百頁(yè)，編輯于2023年，星期五2、完全二叉樹(shù) 深度為k，有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹(shù)中的編號(hào)從1到n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱之為完全二叉樹(shù)。如圖3-8所示是一棵深度為4的完全二叉樹(shù)。第三十頁(yè)，共一百頁(yè)，編輯于2023年，星期五圖3-8深度為4的完全二叉樹(shù)第三十一頁(yè)，共一百頁(yè)，編輯于2023年，星期五

可以看出，完全二叉樹(shù)有下面的特點(diǎn)：

(1)葉子只可能在層次最大的兩層上出現(xiàn)。

(2)最下面一層的結(jié)點(diǎn)都集中在該層最左邊的若干位置上。完全二叉樹(shù)是一個(gè)十分重要的概念，在許多算法和算法分析中，都明顯或隱含地用到了完全二叉樹(shù)的概念。下面介紹完全二叉樹(shù)的兩個(gè)重要特性。

性質(zhì)1：具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為第三十二頁(yè)，共一百頁(yè)，編輯于2023年，星期五

性質(zhì)2：如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的結(jié)點(diǎn)按層序編號(hào)(從第1層到第+1層，每層從左到右)，則對(duì)任一結(jié)點(diǎn)i(1≤i≤n)，有

(1)如果i=1，則i是二叉樹(shù)的根，無(wú)雙親；如果i>1，則其雙親是結(jié)點(diǎn)。

(2)如果2i>n，則結(jié)點(diǎn)i無(wú)左孩子；否則其左孩子是2i。

(3)如果2i+1>n，則結(jié)點(diǎn)i無(wú)右孩子；否則其右孩子是結(jié)點(diǎn)2i+1。證明從略。第三十三頁(yè)，共一百頁(yè)，編輯于2023年，星期五3、滿二叉樹(shù)和完全二叉樹(shù)的關(guān)系 滿二叉樹(shù)=〉完全二叉樹(shù) 滿二叉樹(shù)≠〉完全二叉樹(shù)4、平衡二叉樹(shù)二叉樹(shù)上任一結(jié)點(diǎn)的左子樹(shù)深度減去右子樹(shù)深度的差值，稱為此結(jié)點(diǎn)的平衡因子。若一棵二叉樹(shù)中，每個(gè)結(jié)點(diǎn)的平衡因子之絕對(duì)值都不大于1，則稱這棵二叉樹(shù)為平衡二叉樹(shù)。是平衡二叉樹(shù)不是平衡二叉樹(shù)第三十四頁(yè)，共一百頁(yè)，編輯于2023年，星期五

3.2.3.3二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)對(duì)于二叉樹(shù)，我們既可采用順序存儲(chǔ)，又可采用鏈?zhǔn)酱鎯?chǔ)。

1．順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)就是將一棵二叉樹(shù)的所有結(jié)點(diǎn)按照一定的次序順序存放到一組連續(xù)的存儲(chǔ)單元中，為此，必須把二叉樹(shù)中所有結(jié)點(diǎn)構(gòu)成一個(gè)適當(dāng)?shù)木€性序列，以使各個(gè)結(jié)點(diǎn)在這個(gè)序列中的相互位置能反映出結(jié)點(diǎn)之間的邏輯關(guān)系。第三十五頁(yè)，共一百頁(yè)，編輯于2023年，星期五對(duì)于完全二叉樹(shù)，按圖的編號(hào)順序，就能得到一個(gè)足以反映整個(gè)二叉樹(shù)結(jié)構(gòu)的線性序列。因此，可將完全二叉樹(shù)中所有結(jié)點(diǎn)按編號(hào)順序依次存儲(chǔ)到一組連續(xù)的存儲(chǔ)單元(即向量)中，這樣既不浪費(fèi)內(nèi)存，又可以利用地址公式確定其結(jié)點(diǎn)的位置。1234567ABDEFCJ第三十六頁(yè)，共一百頁(yè)，編輯于2023年，星期五但對(duì)于一般的二叉樹(shù)，順序分配常會(huì)造成內(nèi)存的浪費(fèi)，因?yàn)橐话愕亩鏄?shù)也必須按完全二叉樹(shù)的形式來(lái)存儲(chǔ)。1234567891011ABDEFCJGH第三十七頁(yè)，共一百頁(yè)，編輯于2023年，星期五

2．鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)因?yàn)闃?shù)型結(jié)構(gòu)是非線性的結(jié)構(gòu)，所以在存儲(chǔ)器里表示樹(shù)型結(jié)構(gòu)的最自然的方法是鏈?zhǔn)酱鎯?chǔ)。根據(jù)二叉樹(shù)的特性，任何一個(gè)結(jié)點(diǎn)最多有左、右兩棵子樹(shù)，所以每個(gè)結(jié)點(diǎn)至少設(shè)有三個(gè)域：數(shù)據(jù)域和左、右指針域。其結(jié)點(diǎn)結(jié)構(gòu)為：lchilddatarchild第三十八頁(yè)，共一百頁(yè)，編輯于2023年，星期五第三十九頁(yè)，共一百頁(yè)，編輯于2023年，星期五二叉鏈表結(jié)點(diǎn)的類型定義typedefstructnode{datatypedata;structnode*lchild,*rchild;}bstree;第四十頁(yè)，共一百頁(yè)，編輯于2023年，星期五3.2.3.4二叉樹(shù)的遍歷

遍歷二叉樹(shù)就是按一定的次序，系統(tǒng)地訪問(wèn)樹(shù)中的所有結(jié)點(diǎn)，使每個(gè)結(jié)點(diǎn)恰好被訪問(wèn)一次。所謂訪問(wèn)結(jié)點(diǎn)，其含義是很廣的，可以理解為對(duì)結(jié)點(diǎn)的增、刪、修改等各種運(yùn)算的抽象。在本節(jié)討論中，假定訪問(wèn)結(jié)點(diǎn)即為輸出結(jié)點(diǎn)數(shù)據(jù)域值。二叉樹(shù)的遍歷是最重要和最基本的運(yùn)算，二叉樹(shù)的許多操作都是以遍歷為基礎(chǔ)的。 按照對(duì)二叉樹(shù)中根結(jié)點(diǎn)、左子樹(shù)和右子樹(shù)訪問(wèn)的先后順序，共有三種遍歷二叉樹(shù)的方法： 根、左、右；左、根、右；左、右、根 根據(jù)這三種方法中根結(jié)點(diǎn)被訪問(wèn)的先后，分別稱之為二叉樹(shù)的先序(根)遍歷，中序(根)遍歷和后序(根)遍歷。第四十一頁(yè)，共一百頁(yè)，編輯于2023年，星期五(1)先序遍歷： 若二叉樹(shù)為空，則空操作；否則 ①訪問(wèn)根結(jié)點(diǎn)； ②先序遍歷左子樹(shù)； ③先序遍歷右子樹(shù)。遍歷序列：ABDEGHCF第四十二頁(yè)，共一百頁(yè)，編輯于2023年，星期五先序遍歷的算法voidpreorder(bstree*p){if(p!=NULcL){printf(“%5”,p->data);preorder(p->lchild);preorder(p->rchild);}}第四十三頁(yè)，共一百頁(yè)，編輯于2023年，星期五(2)中序遍歷：若二叉樹(shù)為空，則空操作；否則①中序遍歷左子樹(shù)；②訪問(wèn)根結(jié)點(diǎn)；③中序遍歷右子樹(shù)。遍歷序列：DBGEHACF第四十四頁(yè)，共一百頁(yè)，編輯于2023年，星期五中序遍歷算法voidpreorder(bstree*p){if(p!=NULcL){inorder(p->lchild);printf(“%5”,p->data);inorder(p->rchild);}}第四十五頁(yè)，共一百頁(yè)，編輯于2023年，星期五(3)后序遍歷： 若二叉樹(shù)為空，則空操作；否則 ①后序遍歷左子樹(shù)； ②后序遍歷右子樹(shù)。 ③訪問(wèn)根結(jié)點(diǎn)；遍歷序列：DGHEBFCA第四十六頁(yè)，共一百頁(yè)，編輯于2023年，星期五后序遍歷算法voidposorder(bstree*p){if(p!=NULcL){posorder(p->lchild);posorder(p->rchild);printf(“%5”,p->data);}}第四十七頁(yè)，共一百頁(yè)，編輯于2023年，星期五3.2.4樹(shù)的存儲(chǔ)結(jié)構(gòu)樹(shù)在計(jì)算機(jī)內(nèi)存儲(chǔ)，可以用順序存儲(chǔ)方式、也可以用鏈?zhǔn)酱鎯?chǔ)方式，這主要取決于要對(duì)樹(shù)結(jié)構(gòu)進(jìn)行什么運(yùn)算。這里主要介紹鏈?zhǔn)椒峙涞拇鎯?chǔ)結(jié)構(gòu)。 孩子-兄弟表示法的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示如下：firstdatanext鏈表中結(jié)點(diǎn)的兩個(gè)指針域分別指向該結(jié)點(diǎn)的第一個(gè)孩子和下一個(gè)兄弟結(jié)點(diǎn)。第四十八頁(yè)，共一百頁(yè)，編輯于2023年，星期五RADEFCBGKHRADECHFGBK第四十九頁(yè)，共一百頁(yè)，編輯于2023年，星期五

3.2.5樹(shù)的遍歷

樹(shù)的遍歷有兩種次序：一種是先序遍歷樹(shù)；另一種是后序遍歷樹(shù)。

(1)先序遍歷樹(shù)：先訪問(wèn)樹(shù)的根結(jié)點(diǎn)，然后從左到右依次先序遍歷根的每棵子樹(shù)。如先序遍歷右圖所示的樹(shù)，得到的結(jié)點(diǎn)序列為：RADEBCFGHK

。

(2)后序遍歷樹(shù)：先從左到右依次后根遍歷每棵子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)。如后序遍歷右圖所示的樹(shù)，得到的結(jié)點(diǎn)序列為：DEABGHKFCR。RADEFCBGKH第五十頁(yè)，共一百頁(yè)，編輯于2023年，星期五3.2.6樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換由于二叉樹(shù)和樹(shù)都可用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，則以二叉鏈表作為媒介可導(dǎo)出樹(shù)與二叉樹(shù)之間的一個(gè)對(duì)應(yīng)關(guān)系。也就是說(shuō)，給定一棵樹(shù)，可以找到惟一的一棵二叉樹(shù)與之對(duì)應(yīng)，從物理結(jié)構(gòu)來(lái)看，它們的二叉鏈表是相同的，只是解釋不同而已。圖3-15給出了樹(shù)與二叉樹(shù)之間的對(duì)應(yīng)關(guān)系。第五十一頁(yè)，共一百頁(yè)，編輯于2023年，星期五圖3-15樹(shù)與二叉樹(shù)的對(duì)應(yīng)關(guān)系第五十二頁(yè)，共一百頁(yè)，編輯于2023年，星期五下面給出樹(shù)與二叉樹(shù)之間的轉(zhuǎn)換規(guī)則。

1．一般樹(shù)轉(zhuǎn)換為二叉樹(shù)步驟：

(1)加線：親兄弟之間加一虛連線。

(2)抹線：抹掉(除最左一個(gè)孩子外)該結(jié)點(diǎn)到其余孩子之間的連線。

(3)旋轉(zhuǎn)：新加上去的虛線改實(shí)線且均向右斜(rchild)，原有的連線均向左斜(lchild)。第五十三頁(yè)，共一百頁(yè)，編輯于2023年，星期五圖3-16一般樹(shù)轉(zhuǎn)換為二叉樹(shù)的操作過(guò)程(a)一般樹(shù)；(b)加線后；(c)抹線后；(d)旋轉(zhuǎn)后第五十四頁(yè)，共一百頁(yè)，編輯于2023年，星期五

2．森林轉(zhuǎn)換為二叉樹(shù)森林是樹(shù)的有限集合，利用樹(shù)的轉(zhuǎn)換思想，可以實(shí)現(xiàn)森林到二叉樹(shù)的轉(zhuǎn)換。步驟：

(1)將各棵樹(shù)分別轉(zhuǎn)換為二叉樹(shù)。

(2)按給出森林中樹(shù)的次序，依次將后一棵二叉樹(shù)作為前一棵二叉樹(shù)根結(jié)點(diǎn)的右子樹(shù)，則第一棵樹(shù)的根結(jié)點(diǎn)是轉(zhuǎn)換后二叉樹(shù)的根。第五十五頁(yè)，共一百頁(yè)，編輯于2023年，星期五圖3-17森林轉(zhuǎn)換成對(duì)應(yīng)的二叉樹(shù)的過(guò)程(a)森林；(b)各棵樹(shù)對(duì)應(yīng)的二叉樹(shù)；(c)轉(zhuǎn)換成的二叉樹(shù)第五十六頁(yè)，共一百頁(yè)，編輯于2023年，星期五3.2.7樹(shù)的應(yīng)用樹(shù)結(jié)構(gòu)被廣泛地用于分類、檢索、數(shù)據(jù)庫(kù)及人工智能等方面。二叉排序樹(shù)

二叉排序樹(shù)是一種動(dòng)態(tài)樹(shù)表。

二叉排序樹(shù)的定義：二叉排序樹(shù)或者是一棵空樹(shù)，

或者是一棵具有如下性質(zhì)的二叉樹(shù)：

⑴若它的左子樹(shù)非空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；

⑵若它的右子樹(shù)非空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；

⑶左、右子樹(shù)本身又各是一棵二叉排序樹(shù)。二叉排序樹(shù)的性質(zhì)：按中序遍歷二叉排序樹(shù)，所得到的中序遍歷序列是一個(gè)遞增有序序列。第五十七頁(yè)，共一百頁(yè)，編輯于2023年，星期五（1）二叉排序樹(shù)生成：

從空的二叉排序樹(shù)開(kāi)始，經(jīng)過(guò)一系列的查找插入操作以后，生成了一棵二叉排序樹(shù)。

插入一個(gè)結(jié)點(diǎn)的操作按下述方法完成：

①若原二叉排序樹(shù)為空，則將待插結(jié)點(diǎn)作為此數(shù)的根結(jié)點(diǎn)。

②若原二叉排序樹(shù)不為空，則比較待插結(jié)點(diǎn)和根結(jié)點(diǎn)的關(guān)鍵字值；若待插元素的關(guān)鍵字值小于根結(jié)點(diǎn)的的關(guān)鍵字值，則將其插入到左子數(shù)中；否則，將其插入到右子樹(shù)中；

③在二叉排序樹(shù)的左右子樹(shù)中的插入過(guò)程同上。例：對(duì)于一組關(guān)鍵字{51，34，79，18，45，86}，生成對(duì)應(yīng)的二叉排序樹(shù)第五十八頁(yè)，共一百頁(yè)，編輯于2023年，星期五（2）二叉排序樹(shù)的刪除:

假設(shè)被刪結(jié)點(diǎn)是*p，其雙親是*f，不失一般性，設(shè)*p是*f的左孩子，下面分三種情況討論：⑴若結(jié)點(diǎn)*p是葉子結(jié)點(diǎn)，則只需修改其雙親結(jié)點(diǎn)*f的指針即可.⑵若結(jié)點(diǎn)*p只有左子樹(shù)PL或者只有右子樹(shù)PR，則只要使PL或PR成為其雙親結(jié)點(diǎn)的左子樹(shù)即可。⑶若結(jié)點(diǎn)*p的左、右子樹(shù)均非空，先找到*p的中序前趨結(jié)點(diǎn)*s（注意*s是*p的左子樹(shù)中的最右下的結(jié)點(diǎn)，它的右鏈域?yàn)榭眨?，然后有兩種做法：①令*p的左子樹(shù)直接鏈到*p的雙親結(jié)點(diǎn)*f的左鏈上,而*p的右子樹(shù)鏈到*p的中序前趨結(jié)點(diǎn)*s的右鏈上。②以*p的中序前趨結(jié)點(diǎn)*s代替*p（即把*s的數(shù)據(jù)復(fù)制到*p中），將*s的左子樹(shù)鏈到*s的雙親結(jié)點(diǎn)*q的左（或右）鏈上。第五十九頁(yè)，共一百頁(yè)，編輯于2023年，星期五本節(jié)結(jié)束！第六十頁(yè)，共一百頁(yè)，編輯于2023年，星期五3.3圖3.3.1引言

圖是一種重要的，比樹(shù)更復(fù)雜的非線性數(shù)據(jù)結(jié)構(gòu)。在樹(shù)中，每個(gè)結(jié)點(diǎn)只與上層的父結(jié)點(diǎn)有聯(lián)系，并可以與其下層的多個(gè)子結(jié)點(diǎn)有聯(lián)系。但在圖中，結(jié)點(diǎn)之間的聯(lián)系是任意的，每個(gè)結(jié)點(diǎn)都可以與其它的結(jié)點(diǎn)相聯(lián)系。圖的應(yīng)用極為廣泛，特別是近年來(lái)發(fā)展迅速，已滲入到諸如語(yǔ)言學(xué)、邏輯學(xué)、物理、化學(xué)、電信工程、計(jì)算機(jī)、數(shù)學(xué)及其它分支中。第六十一頁(yè)，共一百頁(yè)，編輯于2023年，星期五3.3.2圖的定義及邏輯結(jié)構(gòu)

1、圖的定義

圖G由兩個(gè)集合V(G)和E(G)所組成，記作G=(V,?E)。其中，V(G)是圖中頂點(diǎn)的非空有限集合，E(G)是圖中邊的有限集合。 有向圖。如果圖中每條邊都是頂點(diǎn)的有序?qū)?，即每條邊都用箭頭表明了方向，則此圖為有向圖。有向圖中的邊也稱為弧，用尖括號(hào)括起一對(duì)頂點(diǎn)表示。

無(wú)向圖。如果圖中每條邊都是頂點(diǎn)的無(wú)序?qū)Γ瑒t稱此圖為無(wú)向圖。無(wú)向邊用圓括號(hào)括起的兩個(gè)相關(guān)頂點(diǎn)來(lái)表示。第六十二頁(yè)，共一百頁(yè)，編輯于2023年，星期五圖G1的頂點(diǎn)集合為：

V(G1)={V1,V2,V3,V4}邊集合為：E(G1)={(V1,V2),(V1,V3),(V1,V4),(V2,V4),(V3,V4)}第六十三頁(yè)，共一百頁(yè)，編輯于2023年，星期五圖G2的頂點(diǎn)集合為：

V(G2)={V1,V2,V3}邊集合為：E(G2)={<V1,V3>,<V2,V1>,<V2,V3>,<V3,V1>}第六十四頁(yè)，共一百頁(yè)，編輯于2023年，星期五

2、圖的有關(guān)術(shù)語(yǔ)

鄰接：在無(wú)向圖中，若邊(Ｖx,Ｖy)E，則Ｖx、Ｖy互為鄰接點(diǎn)；在有向圖中，若弧<Ｖx,Ｖy>E，則Ｖy是Ｖx的鄰接點(diǎn)。 度：VxVyＶx、Ｖy互為鄰接點(diǎn)VxVyＶy是Ｖx的鄰接點(diǎn)第六十五頁(yè)，共一百頁(yè)，編輯于2023年，星期五

度：無(wú)向圖中:頂點(diǎn)的度是連接該頂點(diǎn)的邊的條數(shù)。例如，G1中V2的度為3，V4的度為1。有向圖中:入度:以某頂點(diǎn)為弧頭的弧的數(shù)目G2中頂點(diǎn)1的入度為1。出度:以某頂點(diǎn)為弧尾的弧的數(shù)目。頂點(diǎn)1的出度為2。頂點(diǎn)的度=入度+出度。頂點(diǎn)1的度=2+1=3。213

G24oooov1v2v3v4

G1第六十六頁(yè)，共一百頁(yè)，編輯于2023年，星期五子圖有兩個(gè)圖G=(V,{E})和圖G’=(V’,{E’}),若V’V且E’E,則稱圖G’為G的子圖。第六十七頁(yè)，共一百頁(yè)，編輯于2023年，星期五路徑圖中從頂點(diǎn)Vx到頂點(diǎn)Vy的頂點(diǎn)序列稱為從Vx到Vy的路徑,路徑可能是不唯一的。例如:G1中V1到V3的路徑為:(V1V2V3)或(V1V3);G2中，1到4的路徑為<134>。oooov1v2v3v4G1213

G24第六十八頁(yè)，共一百頁(yè)，編輯于2023年，星期五路徑的長(zhǎng)度路徑上邊或弧的數(shù)目。例如，G1中V1到V3的長(zhǎng)度為1或2；

G2中1到4的長(zhǎng)度為2。oooov1v2v3v4G1213

G24第六十九頁(yè)，共一百頁(yè)，編輯于2023年，星期五連通圖

在無(wú)向圖G中，若從頂點(diǎn)V到頂點(diǎn)V’有路徑，則稱V和V’是連通的。無(wú)向圖中任意兩個(gè)頂點(diǎn)都連通，則稱G是連通圖。第七十頁(yè)，共一百頁(yè)，編輯于2023年，星期五強(qiáng)連通圖有向圖每對(duì)頂點(diǎn)之間都存在路徑第七十一頁(yè)，共一百頁(yè)，編輯于2023年，星期五完全無(wú)向圖 若一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖共有n(n-1)/2條邊，即每一對(duì)頂點(diǎn)之間都有邊相連，則稱其為完全無(wú)向圖完全有向圖 若一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖共有n(n-1)條邊，即每一對(duì)頂點(diǎn)之間都有兩條方向不同的邊相連，則稱其為完全有向圖第七十二頁(yè)，共一百頁(yè)，編輯于2023年，星期五網(wǎng)： 邊或弧上帶有權(quán)值的圖 權(quán)值是與邊或弧有關(guān)的書(shū)，可以表示從一個(gè)頂點(diǎn)到另一定點(diǎn)的距離或耗費(fèi)等。第七十三頁(yè)，共一百頁(yè)，編輯于2023年，星期五3.3.3圖的存儲(chǔ)結(jié)構(gòu)圖的結(jié)構(gòu)比較復(fù)雜，存儲(chǔ)的方法也很多，需要根據(jù)具體的圖形和將來(lái)所要做的運(yùn)算選取適當(dāng)?shù)拇鎯?chǔ)結(jié)構(gòu)。這里只討論兩種最常用的表示方法：鄰接矩陣表示法和鄰接表表示法。

第七十四頁(yè)，共一百頁(yè)，編輯于2023年，星期五

1、順序存儲(chǔ)結(jié)構(gòu)

鄰接矩陣：可用一個(gè)一維數(shù)組存放圖中所有頂點(diǎn)的信息；用一個(gè)二維數(shù)組來(lái)存放數(shù)據(jù)元素之間的關(guān)系的信息(即邊或弧的集合E)。這個(gè)二維數(shù)組稱之為鄰接矩陣。 鄰接矩陣是表示頂點(diǎn)之間的鄰接關(guān)系的矩陣。設(shè)G=(V，E)是有n(n≥1)個(gè)頂點(diǎn)的圖，則G的鄰接矩陣A是一個(gè)具有下列性質(zhì)的n×n階矩陣第七十五頁(yè)，共一百頁(yè)，編輯于2023年，星期五無(wú)向圖鄰接矩陣 定義:設(shè)圖G=(V,E)是有n(n1)個(gè)頂點(diǎn)的圖，則G的鄰接矩陣是具有下述性質(zhì)的對(duì)稱陣：

1(Vi，Vj）EA[i][j]=A[j][i]= 0(Vi，Vj）EG1的鄰接矩陣為：oooov1v3v4G1A=G.edge=

01101011110001004x4G.nodes=

1234第七十六頁(yè)，共一百頁(yè)，編輯于2023年，星期五有向圖鄰接矩陣 定義:設(shè)圖G=（V，E）是有n（n1）個(gè)頂點(diǎn)的圖，則G的鄰接矩陣是具有下述性質(zhì)的nxn的方陣：

1〈Vi，Vj>EA[i][j]=0〈Vi，Vj>E

例如，G2的鄰接矩陣為：G.nodes=1234A=G.Arc=

01100000000110004x41324

G2第七十七頁(yè)，共一百頁(yè)，編輯于2023年，星期五借助于鄰接矩陣，可以很容易地求出圖中頂點(diǎn)的度。從上例可以很容易看出，鄰接矩陣有如下結(jié)論：

(1)無(wú)向圖的鄰接矩陣是對(duì)稱的，而有向圖的鄰接矩陣不一定對(duì)稱。對(duì)無(wú)向圖可考慮只存下三角(或上三角)元素。

(2)對(duì)于無(wú)向圖，鄰接矩陣第i行(或第i列)的元素之和是頂點(diǎn)Vi的度。

(3)對(duì)于有向圖，鄰接矩陣第i行元素之和為頂點(diǎn)Vi的出度；第i列的元素之和為頂點(diǎn)Vi的入度。第七十八頁(yè)，共一百頁(yè)，編輯于2023年，星期五

2、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

圖的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是通過(guò)為每一個(gè)頂點(diǎn)建立一個(gè)相應(yīng)的單鏈表來(lái)實(shí)現(xiàn)的，這種存儲(chǔ)結(jié)構(gòu)被稱為鄰接鏈表。 鄰接鏈表是一種順序分配和鏈?zhǔn)椒峙湎嘟Y(jié)合的存儲(chǔ)結(jié)構(gòu)。它包括兩個(gè)部分：一部分是鏈表；另一部分是向量。

第七十九頁(yè)，共一百頁(yè)，編輯于2023年，星期五 在鄰接表中，對(duì)圖中每個(gè)頂點(diǎn)建立一個(gè)單鏈表，第i個(gè)單鏈表中的結(jié)點(diǎn)包含了頂點(diǎn)Vi的所有鄰接頂點(diǎn)。每個(gè)結(jié)點(diǎn)由三個(gè)域組成：adjvex、data和nextarc，如下圖所示。第八十頁(yè)，共一百頁(yè)，編輯于2023年，星期五為便于鄰接表操作，在每個(gè)單鏈表上附設(shè)一個(gè)頭結(jié)點(diǎn)，在頭結(jié)點(diǎn)中有兩個(gè)域：vexdata和firstarc。如下圖所示。第八十一頁(yè)，共一百頁(yè)，編輯于2023年，星期五第八十二頁(yè)，共一百頁(yè)，編輯于2023年，星期五圖的鄰接鏈表數(shù)據(jù)類型定義如下：structadjnode{intadjv;structadjnode*next;};structvernode{charver;structadjnode*first;}adjlist[N+1];第八十三頁(yè)，共一百頁(yè)，編輯于2023年，星期五有向圖建立鄰接鏈表的算法structvernodeg[N+1]voidcreatadjlist(){inti,j,k;adjnode*s;for(i=1;i<=N;i++){g[i].ver=getchar();g[i].first=NULL;}

for(k=1;k<=E;k++){scanf(“%d,%d”,&i,&j);s=(structadjnode*)mallov(sizeof(adjnode));s->adjv=j;s->next=g[i].first;g[i].first=s;}}

第八十四頁(yè)，共一百頁(yè)，編輯于2023年，星期五

對(duì)一個(gè)圖來(lái)說(shuō)，鄰接鏈表不是惟一的，它取決于建立鄰接鏈表時(shí)，結(jié)點(diǎn)在每個(gè)單鏈表中的插入策略。另外，對(duì)于有向圖，其鄰接鏈表中第i個(gè)單鏈表的結(jié)點(diǎn)個(gè)數(shù)就是此結(jié)點(diǎn)的出度；對(duì)于無(wú)向圖，其鄰接表中第i個(gè)單鏈表的結(jié)點(diǎn)個(gè)數(shù)就是此結(jié)點(diǎn)的度。第八十五頁(yè)，共一百頁(yè)，編輯于2023年，星期五3.3.4圖

的

遍

歷 圖的遍歷(traversinggraph)是指從圖中某一頂點(diǎn)出發(fā)，沿著一定的搜索路徑，對(duì)圖中各個(gè)頂點(diǎn)進(jìn)行訪問(wèn)，使每個(gè)頂點(diǎn)都被訪問(wèn)且僅被訪問(wèn)一次。圖的遍歷算法是求解圖的連通性問(wèn)題、拓?fù)渑判蚝颓箨P(guān)鍵路徑等算法的基礎(chǔ)。第八十六頁(yè)，共一百頁(yè)，編輯于2023年，星期五然而，圖的遍歷要比樹(shù)的遍歷復(fù)雜得多，因?yàn)閳D中任一頂點(diǎn)都可能和其余的頂點(diǎn)相鄰接，所以在訪問(wèn)了某個(gè)頂點(diǎn)之后，可能沿著某條路徑搜索之后，又回到該頂點(diǎn)上。為避免同一頂點(diǎn)被訪問(wèn)多次，在遍歷圖的過(guò)程中，必須記下每個(gè)已訪問(wèn)過(guò)的頂點(diǎn)。為此，設(shè)一個(gè)輔助數(shù)組visited[n]，它的初值為“假”或者零，一旦訪問(wèn)了頂點(diǎn)Vi，便置visited[i]為“真”或者為被訪問(wèn)時(shí)的次序號(hào)。通常有兩種遍歷圖的方法，深度優(yōu)先搜索和廣度優(yōu)先搜索。第八十七頁(yè)，共一百頁(yè)，編輯于2023年，星期五

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

圖的深度優(yōu)先搜索遍歷(depth-firstsearch)類似于樹(shù)的先序遍歷，是樹(shù)的先序遍歷的推廣。特點(diǎn)：遍歷時(shí)盡可能向縱深的方向搜索。 步驟（從Vi出發(fā)）

1)訪問(wèn)Vi，并將其對(duì)應(yīng)的訪問(wèn)標(biāo)志為visited[i]置為1；

2)搜索出Vi的一個(gè)未訪問(wèn)過(guò)的鄰接點(diǎn)Vj。

3)從Vj出發(fā)，按以上步驟繼續(xù)進(jìn)行深度優(yōu)先搜索，直到所有頂點(diǎn)均訪問(wèn)完畢。第八十八頁(yè)，共一百頁(yè)，編輯于2023年，星期五顯然，這個(gè)遍歷過(guò)程是個(gè)遞歸過(guò)程。在設(shè)計(jì)具體算法時(shí)，首先要確定圖的存儲(chǔ)結(jié)構(gòu)，下面以鄰接表為例，討論深度優(yōu)先搜索法。例連通圖G6的鄰接表表示如下圖所示，以頂點(diǎn)V1為始點(diǎn)，按深度優(yōu)先搜索遍歷圖中所有頂點(diǎn)，寫(xiě)出頂點(diǎn)的遍歷序列。第八十九頁(yè)，共一百頁(yè)，編輯于2023年，星期五解：先訪問(wèn)V1，再訪問(wèn)與V1鄰接的V2，再訪問(wèn)V2的第一個(gè)鄰接點(diǎn)，因V1已被訪問(wèn)過(guò)，則訪問(wèn)V2的下一個(gè)鄰接點(diǎn)V4，然后依次訪問(wèn)V8，V5。這時(shí)，與V5相鄰接的頂點(diǎn)均已被訪問(wèn)，于是反向回到V8去訪問(wèn)與V8相鄰接且尚未被訪問(wèn)的V6，接著訪問(wèn)V3，V7，至此，全部頂點(diǎn)均被訪問(wèn)。相應(yīng)的訪問(wèn)序列為：V1→V2→V4→V8→V5→V6→V3→V7。第九十頁(yè)，共一百頁(yè)，編輯于2023年，星期五深度優(yōu)先搜索的遞歸算法（鄰接矩陣存儲(chǔ)結(jié)構(gòu)）#defineNULL0intg[N+1][N+1];charver[N+1];intvisited[N+1];

voiddfsm(i)inti;{intj;printf(“%c”,ver[i]);visited[i]=1;for(j=1;j<=N;j++)if((g[i][j]==1)&&(!visited[j]))

dfsm(j);}第九十一頁(yè)，共一百頁(yè)，編輯于2023年，星期五

structvernodeg[N+1];intvisited[N+1];

voiddfsa(i)inti;{intj;structadjnode*p;printf(“%c”,g[i].ver);visited[i]=1;p=g[i].first;

while(p!=NULL){if!Visited[p->adjv])

dfsa(p->adjv);

p=p->next;}