數(shù)據(jù)結(jié)構(gòu)中遍歷操作的非遞歸算法

韓凱

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

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

一、概述

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

二、二叉樹(shù)的遍歷

（一）二叉樹(shù)的遍歷操作

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

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

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

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

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

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

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

先序遍歷：

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

{

STack * S; 11 棧 S 中存儲(chǔ)指向樹(shù)結(jié)點(diǎn)的指針。

BiTree P;

......

//如果左子樹(shù)和右子樹(shù)均被訪問(wèn)過(guò)，則結(jié)點(diǎn)退棧，并進(jìn)行訪問(wèn)。更新pre。else

Pop（S，&p）.

if（！ Visit（p- > data））

retum ER ROR;

pre =p;

}

}

retum oK;

對(duì)照非遞歸算法可以發(fā)現(xiàn)：非遞歸算法應(yīng)用指針和堆棧，進(jìn)行出棧和入棧的方法實(shí)現(xiàn)了算法，非遞歸算法程序總體來(lái)說(shuō)較長(zhǎng)，編寫和調(diào)試要費(fèi)些時(shí)間，但因?yàn)槠湟恢痹谡{(diào)用其他函數(shù)進(jìn)行進(jìn)棧出棧，所以其占用的空間較少、用時(shí)也較短。

三、圖的遍歷

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

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

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

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

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

己訪問(wèn)頂點(diǎn)當(dāng)前搜索情況的類型定義如下：

struct V exSearchInfo

{ int vexIndex：//已訪問(wèn)頂點(diǎn)的下標(biāo)

AreNode * pNext;//指向已訪問(wèn)頂點(diǎn)的下一個(gè)要判斷的鄰接點(diǎn)

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

void DFSTraverse（ALGraph G）

{ VexSearchInfo sl[20];

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

......

//從最近已訪問(wèn)頂點(diǎn)的鄰接點(diǎn)中尋找一個(gè)未訪問(wèn)的頂點(diǎn)

if（visited[p-→adjvex]==false） //找到一個(gè)未訪問(wèn)的頂點(diǎn)

{//訪問(wèn)此頂點(diǎn)，并存儲(chǔ)其當(dāng)前搜索情況

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-;//如果最近已訪問(wèn)頂點(diǎn)的所有鄰接點(diǎn)搜索完畢，則刪除頂點(diǎn)

搜索情況。

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

參考文獻(xiàn)

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