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

詹澤梅

摘要： 二叉樹和圖是數(shù)據(jù)結(jié)構(gòu)中非常重要的內(nèi)容，遍歷操作是它們的最基本的操作。由于遞歸函數(shù)執(zhí)行過程系統(tǒng)開銷較大，因此該文研究了遍歷操作的非遞歸算法。論文介紹了二叉樹遍歷和圖的深度優(yōu)先搜索操作定義，分析了操作的非遞歸算法解決思路，并給出詳細(xì)的非遞歸算法。

關(guān)鍵詞：非遞歸；先序遍歷；深度優(yōu)先搜索；數(shù)據(jù)結(jié)構(gòu)

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2017）28-0040-03

Abstract： Binary tree and graph are very important contents in data structure. Traversal operation is the basic operation of them. Because the system overhead of recursive function execution is larger than that of non-recursive function， this paper studies the non-recursive algorithm of traversal operations. The paper introduces the definition of the binary traversal and the depth_first search of graph， analyzes the solutions of these operations， and gives the detailed non-recursive algorithms.

Key words： non-recursion； preorder traversal； depth_first search； data structure

1 概述

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專業(yè)的一門重要專業(yè)基礎(chǔ)課。該課程介紹的數(shù)據(jù)結(jié)構(gòu)非常抽象，且算法比較復(fù)雜，特別是二叉樹和圖的操作算法。二叉樹和圖的很多相關(guān)操作是在遍歷操作的基礎(chǔ)上實(shí)現(xiàn)的，因此，理解遍歷操作對(duì)于樹和圖兩章內(nèi)容非常重要。

一般，二叉樹的遍歷和圖的深度優(yōu)先搜索算法通常使用遞歸算法來描述。遞歸算法具有結(jié)構(gòu)清晰、描述簡單、容易理解的特點(diǎn)。但是遞歸函數(shù)調(diào)用的過程既浪費(fèi)系統(tǒng)存儲(chǔ)空間 ， 還消耗系統(tǒng)處理的時(shí)間[1]，因此，有必要研究遍歷操作的非遞歸算法。

2 二叉樹的遍歷

2.1 二叉樹的遍歷操作

二叉樹可分為根D、左子樹L、右子樹R三部分，對(duì)這三部分的訪問順序可按DLR、LDR、LRD三種順序進(jìn)行，由此得到三種遍歷方法：先序遍歷、中序遍歷、后序遍歷。

先序遍歷的思想是[2]：若二叉樹為空，則空操作，否則：

（1） 訪問根結(jié)點(diǎn)；

（2） 先序遍歷左子樹；

（3） 先序遍歷右子樹。

中序遍歷算法、后序遍歷算法的思想與先序遍歷算法思想類似，區(qū)別在于訪問根結(jié)點(diǎn)操作的時(shí)機(jī)不同。中序遍歷操作時(shí)，根結(jié)點(diǎn)的訪問在遍歷左子樹和遍歷右子樹兩個(gè)操作中間；后序遍歷時(shí)，根結(jié)點(diǎn)的訪問在遍歷左子樹和遍歷右子樹兩個(gè)操作之后。

2.2 遍歷操作的非遞歸算法

遍歷二叉樹操作的給定條件是根指針，因此遍歷二叉樹操作從根結(jié)點(diǎn)開始。先序遍歷二叉樹過程中，對(duì)根結(jié)點(diǎn)、左子樹、右子樹三部分的操作順序是訪問根結(jié)點(diǎn)、遍歷左子樹、遍歷右子樹。圖1中虛線和數(shù)字畫出了對(duì)一棵非空二叉樹先序遍歷的操作順序。同樣，我們可分析出二叉樹中序遍歷和后序遍歷的操作順序，如圖2、圖3。

根據(jù)上述三圖可將一棵非空二叉樹遍歷時(shí)的狀態(tài)分為4種：開始遍歷、訪問根結(jié)點(diǎn)、遍歷左子樹、遍歷右子樹。遍歷過程中，二叉樹從一種狀態(tài)轉(zhuǎn)變?yōu)榱硪环N。例如先序遍歷，首先處于開始遍歷狀態(tài)，接著轉(zhuǎn)變?yōu)樵L問根結(jié)點(diǎn)狀態(tài)，然后轉(zhuǎn)變?yōu)楸闅v左子樹狀態(tài)，最后轉(zhuǎn)變?yōu)楸闅v右子樹狀態(tài)。我們可以定義一個(gè)枚舉類型表示二叉樹遍歷操作的狀態(tài)。

遍歷二叉樹的操作中，又有遍歷左子樹、遍歷右子樹，它是一個(gè)遞歸定義的操作。如果要用非遞歸算法來描述，需要記錄每一個(gè)遍歷子樹（即二叉樹）操作的信息，包括子樹根指針和操作狀態(tài)，以便根據(jù)信息對(duì)子樹進(jìn)行后續(xù)操作。因?yàn)檫f歸具有先調(diào)用后返回的特點(diǎn)，所以應(yīng)該用一個(gè)先進(jìn)后出特點(diǎn)的數(shù)據(jù)結(jié)構(gòu)來記錄所有遍歷子樹操作的信息，例如棧，或者只在末尾進(jìn)行操作的數(shù)組。

最初遍歷二叉樹時(shí)，將該二叉樹的遍歷操作狀態(tài)設(shè)置為開始遍歷狀態(tài)，并存儲(chǔ)該遍歷操作信息。遍歷操作過程中，根據(jù)當(dāng)前遍歷操作狀態(tài)進(jìn)行相應(yīng)狀態(tài)轉(zhuǎn)變和處理。在處理時(shí)，如遇到遍歷子樹操作，必須存儲(chǔ)子樹的遍歷操作信息，此時(shí)信息中遍歷操作狀態(tài)應(yīng)設(shè)置為開始遍歷狀態(tài)。一直根據(jù)遍歷操作狀態(tài)進(jìn)行處理，直到所有遍歷操作處理完為止。例如先序遍歷，其根據(jù)遍歷操作信息進(jìn)行處理的規(guī)則如下：

若二叉樹為空，則刪除該遍歷操作信息。

若二叉樹的遍歷操作狀態(tài)為開始遍歷，則接下來將其狀態(tài)轉(zhuǎn)變?yōu)樵L問根結(jié)點(diǎn)，并執(zhí)行訪問根節(jié)點(diǎn)操作。

若二叉樹的遍歷操作狀態(tài)為訪問根結(jié)點(diǎn)，則接下來將其狀態(tài)轉(zhuǎn)變?yōu)楸闅v左子樹，并存儲(chǔ)左子樹的遍歷操作信息。

若二叉樹的遍歷操作狀態(tài)為遍歷左子樹，則接下來將其狀態(tài)轉(zhuǎn)變?yōu)楸闅v右子樹，并存儲(chǔ)右子樹的遍歷操作信息。

若二叉樹的遍歷操作狀態(tài)為遍歷右子樹，則接下來該遍歷操作結(jié)束，刪除該遍歷操作信息。

中序遍歷和后序遍歷的處理與先序遍歷類似，只是遍歷操作的狀態(tài)轉(zhuǎn)變順序不同。對(duì)上述先序遍歷算法進(jìn)行簡單的修改，就可獲得中序遍歷和后序遍歷的非遞歸算法。

3 圖的遍歷

3.1 深度優(yōu)先搜索

圖的遍歷方法有兩種：深度優(yōu)先搜索和廣度優(yōu)先搜索。其中，深度優(yōu)先搜索的算法通常采用遞歸定義形式。

從某頂點(diǎn)V0出發(fā)進(jìn)行深度優(yōu)先搜索的算法思想如下：

（1） 訪問V0

（2） 對(duì)V0的所有鄰接點(diǎn)依次判斷，若鄰接點(diǎn)未訪問，則從此鄰接點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜索。

對(duì)圖G進(jìn)行深度優(yōu)先搜索的算法思想：對(duì)圖的所有頂點(diǎn)依次判斷，若未訪問，則從此頂點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜索。

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

由上述算法可以看出，訪問一個(gè)頂點(diǎn)Vi后，接下來要根據(jù)此頂點(diǎn)Vi尋找下一個(gè)未訪問的頂點(diǎn)。從Vi的所有鄰接點(diǎn)中去尋找，只有所有鄰接點(diǎn)都被判斷完了，從Vi出發(fā)進(jìn)行的深度優(yōu)先搜索操作才結(jié)束。因此，深度搜索過程中要記錄每一個(gè)已訪問頂點(diǎn)的當(dāng)前搜索情況，包括頂點(diǎn)位置和它的下一個(gè)要判斷的鄰接點(diǎn)的位置。已訪問頂點(diǎn)的當(dāng)前搜索情況應(yīng)按后進(jìn)先出的規(guī)則存儲(chǔ)，因?yàn)槿粼L問了一個(gè)頂點(diǎn)，則要從此新的頂點(diǎn)開始搜索，新頂點(diǎn)的所有鄰接點(diǎn)搜索完了，才能繼續(xù)以前頂點(diǎn)的搜索。

4 總結(jié)

數(shù)據(jù)結(jié)構(gòu)中樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)是較復(fù)雜的結(jié)構(gòu)，他們的遍歷操作是最重要的操作。通常，使用遞歸函數(shù)描述二叉樹的遍歷和圖的深度優(yōu)先搜索，但遞歸函數(shù)執(zhí)行時(shí)的系統(tǒng)開銷較大，因此，本文研究了遍歷操作的非遞歸算法，分析了算法思想，給出了非遞歸算法的詳細(xì)描述。

參考文獻(xiàn)：

[1] 余艷， 劉燕麗.數(shù)據(jù)結(jié)構(gòu)中遞歸算法的教學(xué)要點(diǎn)及方法探討[J].電腦知識(shí)與技術(shù)，2014（2）.

[2] 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].清華大學(xué)出版社，2008.endprint