韓凱

摘要：在研究樹的遍歷和圖的遍歷時大多使用非遞歸算法。本文主要對數(shù)據(jù)結(jié)構(gòu)進行概述分析二叉樹遍歷和圖的深度優(yōu)化搜索的非遞歸推算，理清了在研究樹與圖的過程中的思路，希望有所啟發(fā)。

關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu);二叉樹;圖的深度優(yōu)化搜索;非遞歸算法

一、概述

數(shù)據(jù)結(jié)構(gòu)是計算機的專業(yè)課程，數(shù)據(jù)結(jié)構(gòu)一股比較抽象復(fù)雜的，二叉樹和圖的操作算法還是具有代表性的，這兩種算法都需要遍歷操作為基礎(chǔ)，所以只要了解了數(shù)據(jù)結(jié)構(gòu)中遍歷操作法，才能對樹和圖有深刻認識。

二、二叉樹的遍歷

（一）二叉樹的遍歷操作

許多樹的應(yīng)用都是基于樹的遍歷來實現(xiàn)的，例如查找元素、插入元素等。二叉樹主要是根和左右子樹三部分，訪問是有一定順序的，所以導(dǎo)致遍歷先序、中序和后序三種方法。遍歷思想是類似的，先看二叉樹是否為空，不是的話就按照先根后左子樹最后右子樹來訪問，二叉樹是空的時候不需要操作。二叉樹在計算科學(xué)中有著重要的作用，如計算機操作系統(tǒng)中的文件管理、編譯程序的語法結(jié)構(gòu)和數(shù)據(jù)庫系統(tǒng)信息組織形式等;在生活中，二叉樹可以用在密碼學(xué)中，利用二叉樹的先序遍歷、后序便利、中序遍歷對密碼進行加密和解密;在經(jīng)濟中，二叉樹可以用來研究期權(quán)的定價模型。

二、遍歷操作的非遞歸算法

二叉樹的非遞歸遍歷要借助堆棧來實現(xiàn)，具體算法為：

1）設(shè)置一個堆棧進行初始化。

2）把根節(jié)點所表示的指針入棧。

3）當堆棧非空時，重復(fù)執(zhí)行下列步驟：①出棧會取得一個結(jié)點指針，對該結(jié)點進行訪問;②若該結(jié)點的右孩子不是空，則該結(jié)點的右子樹指針進棧;⑧若該結(jié)點的左孩子不是空，則該結(jié)點的左子樹指針進棧。

二叉樹遍歷的非遞歸算法相對于遞歸算法，減少了函數(shù)調(diào)用等開銷，具有性能優(yōu)勢。

先序遍歷：

Int PreOrderl （BiTree T，Int （*Visit） （TElemTypee））

{

STack * S; 11 棧 S 中存儲指向樹結(jié)點的指針。

BiTree P;

......

//如果左子樹和右子樹均被訪問過，則結(jié)點退棧，并進行訪問。更新pre。else

Pop（S，&p）.

if（！ Visit（p- > data））

retum ER ROR;

pre =p;

}

}

retum oK;

對照非遞歸算法可以發(fā)現(xiàn)：非遞歸算法應(yīng)用指針和堆棧，進行出棧和入棧的方法實現(xiàn)了算法，非遞歸算法程序總體來說較長，編寫和調(diào)試要費些時間，但因為其一直在調(diào)用其他函數(shù)進行進棧出棧，所以其占用的空間較少、用時也較短。

三、圖的遍歷

（一）深度優(yōu)先搜索

圖的深度優(yōu)先搜索，是研究數(shù)據(jù)結(jié)構(gòu)圖的經(jīng)典方法。利用深度優(yōu)先搜索方法，把目標圖進行拓撲，對涂上一直點進行數(shù)字排列形成拓撲排序表，這種方法在解決圖論相關(guān)問題是是非常常見的，簡單方便又明晰易懂，只是在敲代碼的時間上比較久，但是不能以此忽略其解決問題的潛能。圖的遍歷主要是深度優(yōu)化搜索和廣度優(yōu)化搜索，這兩種遍歷方法，裝深度優(yōu)化搜索主要用數(shù)據(jù)的非遞歸算法。

（二）深度優(yōu)先搜索的非遞歸算法

深度優(yōu)化利用非遞歸算法，要記錄每一個從起點和所有臨接點之間的搜索記錄，記錄結(jié)果按照先出去后進來的原則進行存儲，只要把上一個點的搜索情況完成，下一個點

才能夠繼續(xù)。舉實例來證明：設(shè)連通圖G中的邊集E={（a，b）， （a，e）， （a，c）， （b，e）， （e，d）， （d，f），（f，c）}，則從頂點a出發(fā)可以得到一種深度優(yōu)先遍歷的頂點序列是什么呢？圖的深度優(yōu)化搜索遍歷類似于樹的前序遍歷.首先訪問出發(fā)點A，并將其標記為已訪問過;然后依次從A出發(fā)搜索A的每個鄰接點B、C、D、E，首先判斷B是否曾訪問過，若是B未訪問過需要以B為新的出發(fā)點繼續(xù)前一個步驟深度優(yōu)化搜索，直至圖中所有和A相連接的點或者是有路徑相通點均己被訪問為止。圖中只要存在一個未進行訪問的點，就把此未訪問點作為頂點成為新的源頭重復(fù)之前的步驟進行訪問判斷，直至所有的點都被訪問為止。所以從A點出發(fā)，找A的下一個點，A下一個點有B、C、D、E，首先到B，再以b為源點，再看B有沒有下一個點，發(fā)現(xiàn)B的下一個點是E，再以E為源點，E的下一個點是d，再以D為源點，下一個點是F，再以F的下一個點是C.這樣全部的點都得到了，該序列就是該圖的深度優(yōu)化搜索遍歷，即ABEDFC。

己訪問頂點當前搜索情況的類型定義如下：

struct V exSearchInfo

{ int vexIndex：//已訪問頂點的下標

AreNode * pNext;//指向已訪問頂點的下一個要判斷的鄰接點

圈的深度優(yōu)先搜索算法如下：

void DFSTraverse（ALGraph G）

{ VexSearchInfo sl[20];

for（v=0;v=G.VEXNUM ;v++）

......

//從最近已訪問頂點的鄰接點中尋找一個未訪問的頂點

if（visited[p-→adjvex]==false） //找到一個未訪問的頂點

{//訪問此頂點，并存儲其當前搜索情況

cout<adjvex]data<<””;

visited[p→adjvex]=true;

temp.vexIndex=p→adjvex; temp. pNext=G.vertices[p→ad-jvex]. firstarc：

sl[num++]=temp;

break：

if（p==NULL） num-;//如果最近已訪問頂點的所有鄰接點搜索完畢，則刪除頂點

搜索情況。

總體上而言，數(shù)據(jù)結(jié)構(gòu)的非遞歸算法是比較有效率的，很方便解決問題，但有一個弊端就是它的代碼比較長，需要自行管理。樹的遍歷和圖的遍歷在數(shù)據(jù)結(jié)構(gòu)分析中屬于比較復(fù)雜的結(jié)構(gòu)，而且他們的便利操作是最基本又最重要的操作。研究二叉樹和圖的深度優(yōu)化搜索通常使用遞歸函數(shù)，利用遞歸函數(shù)研究是存在一定的困難，便可以采用非遞歸算法，這種方法簡單明確，容易理解同樣可以對二叉樹和圖的深度優(yōu)化搜索進行描述。

參考文獻

[1]詹澤梅.數(shù)據(jù)結(jié)構(gòu)中遍歷操作的非遞歸算法[J].電腦知識與技術(shù)，2017（28）.