一種二叉樹非遞歸遍歷算法的C語言實(shí)現(xiàn)

龔佳　袁赟　劉遠(yuǎn)軍

摘要：針對二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)，分析了二叉樹的各種遍歷算法，探討了遞歸算法的遞推消除問題，提出了一種改進(jìn)的非遞歸遍歷算法并用C語言予以實(shí)現(xiàn)。

關(guān)鍵詞：二叉樹；遍歷算法；非遞歸；C語言實(shí)現(xiàn)

中圖分類號：TP301 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2014）01-0223-03

1 概述

樹形結(jié)構(gòu)是一種非常常見的數(shù)據(jù)結(jié)構(gòu)，而二叉樹又是其中最重要的一種樹形結(jié)構(gòu)。二叉樹的遍歷是指按照一定的規(guī)則和次序?qū)⒍鏄渲械拿恳粋€(gè)結(jié)點(diǎn)都訪問一次，既不能重復(fù)，也不能漏掉。一般而言，對二叉樹的遍歷有前序遍歷、中序遍歷、后序遍歷和按層遍歷等幾種方式。在具體的算法設(shè)計(jì)上，以上遍歷方式一般采取遞歸算法來實(shí)現(xiàn)，該文將探討采用非遞歸算法來實(shí)現(xiàn)二叉樹的遍歷。

2 二叉樹的數(shù)據(jù)結(jié)構(gòu)描述

二叉樹作為一種非線性結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)最多有一個(gè)雙親結(jié)點(diǎn)和兩個(gè)子結(jié)點(diǎn)。二叉樹可以采用順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。對于完全二叉樹而言，采用順序存儲是非常方便并且節(jié)省空間的，但是對于大部分的非完全二叉樹而言，采用順序存儲將導(dǎo)致空間浪費(fèi)嚴(yán)重且結(jié)構(gòu)混亂、效率低下。因此，更多的時(shí)候，大家都更愿意用鏈?zhǔn)酱鎯Y(jié)構(gòu)來表示二叉樹，這樣結(jié)構(gòu)更加清晰，尤其是對于左右子樹的描述和雙親節(jié)點(diǎn)的描述更加方便。該文中擬采用鏈?zhǔn)浇Y(jié)構(gòu)來表示二叉樹。用鏈?zhǔn)酱鎯Y(jié)構(gòu)來表示二叉樹，一個(gè)結(jié)點(diǎn)至少由3個(gè)域組成，即數(shù)據(jù)域、左子結(jié)點(diǎn)域和右子結(jié)點(diǎn)域（如圖1所示）。

3 二叉樹的遍歷及遞歸算法實(shí)現(xiàn)

3.1 二叉樹的遍歷

二叉樹的遍歷就是一個(gè)不漏的訪問樹中的每個(gè)結(jié)點(diǎn)，同時(shí)也不能重復(fù)。所謂“訪問”，就是指對結(jié)點(diǎn)的數(shù)據(jù)域進(jìn)行某種操作，比如說讀取、刪除、更新、求該節(jié)點(diǎn)深度等等。對于二叉樹中的任意一個(gè)部分，都可以把它看作三部分，根節(jié)點(diǎn)、左子樹、右子樹，我們用D表示訪問跟結(jié)點(diǎn)，用L表示遍歷左子樹，用R表示遍歷右子樹，則共有以下6種遍歷方式[1]。

1） DLR：先訪問根結(jié)點(diǎn)，再遍歷左子樹，然后遍歷右子樹；

2） DRL：先訪問根結(jié)點(diǎn)，再遍歷右子樹，然后遍歷左子樹；

3） LDR：先遍歷左子樹，再訪問根結(jié)點(diǎn)，然后遍歷右子樹；

4） RDL：先遍歷右子樹，再訪問根結(jié)點(diǎn)，然后遍歷左子樹；

5） LRD：先遍歷左子樹，再遍歷右子樹，然后訪問根結(jié)點(diǎn)；

6） RLD：先遍歷右子樹，再遍歷左子樹，然后訪問根結(jié)點(diǎn)。

為了方便和規(guī)范化，通常都規(guī)定遍歷順序是先左后右的，所以以上6種遍歷算法，經(jīng)常采用的是DLR（前序遍歷）、LDR（中序遍歷）和LRD（后序遍歷）。在有些情況下，特別是對于完全二叉樹的情況，還可以采用按層遍歷的方式。該文將以中序遍歷（LDR）為例，分析并探討LDR的遞歸算法和非遞歸算法。

3.2 LDR的遞歸算法

對于中序遍歷（LDR）而言，在二叉樹的任何一個(gè)結(jié)點(diǎn)，都執(zhí)行以下步驟：

1） 判斷是否為空，如果為空，遍歷結(jié)束；

2） 按中序遍歷左子樹；

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

4） 按中序遍歷右子樹。

其中，步驟（1）是結(jié)束條件，步驟（2）和步驟（4）則是一個(gè)典型的遞歸調(diào)用過程。依據(jù)這個(gè)算法思想，寫出C語言代碼如下：

void InOrder（Tnode root）

//中序遍歷二叉樹，root 表示二叉樹或當(dāng)前子樹的根結(jié)點(diǎn)指針

{if（root！=NULL）

{InOrder（root→L_child）；

//中序遍歷左子樹

visit（root→Data）；

//訪問當(dāng)前根節(jié)點(diǎn)的數(shù)據(jù)域

InOrder（root→R_child）；

//中序遍歷右子樹

}}

其中，visit（ ）為訪問函數(shù)，對二叉樹或當(dāng)前子樹的根結(jié)點(diǎn)的數(shù)據(jù)域進(jìn)行訪問，訪問方式可以是讀取數(shù)據(jù)、刪除、修改等等各種操作，這里不再贅述。

4 二叉樹的非遞歸算法

4.1 遞歸算法的缺點(diǎn)與采用非遞歸算法的必要性

遞歸算法是一種化繁為簡，把復(fù)雜問題分解成若干簡單問題的求解方式，他對某些復(fù)雜問題的求解是非常有效的[2]。但是，遞歸算法實(shí)際上是在頂層把要解決的問題往后推，然后等到遞推到最底層，等解決完一個(gè)子問題后再往后回溯遞歸，再返回到最頂層，同時(shí)，遞歸算法的執(zhí)行需要系統(tǒng)提供隱式棧來支持，這必然會導(dǎo)致遞歸算法的執(zhí)行效率較低。并且在以下兩種情況下，必須要用非遞歸算法來代替遞歸算法。

1） 某些語言環(huán)境不支持遞歸。如Fortran語言中無遞歸機(jī)制。

2） 遞歸算法是一次性執(zhí)行的，中間過程對用戶是不可見的，而有時(shí)需要設(shè)置斷點(diǎn)，調(diào)試程序，或者有其他的特殊要求時(shí)，不能采用遞歸算法[1，2]。

4.2 中序遍歷的非遞歸算法

首先，我們要分析遞歸算法中進(jìn)層和退層時(shí)的操作。

遞歸進(jìn)層時(shí)系統(tǒng)需要做三件事：

1） 保留本層參數(shù)與返回地址（將所有的實(shí)參、返回地址等信息傳遞給被調(diào)用函數(shù)保存）；

2） 給下層參數(shù)賦值（為被調(diào)用函數(shù)的局部變量分配存儲區(qū)）；

3） 將程序轉(zhuǎn)移到被調(diào)函數(shù)的入口。

遞歸退層時(shí)系統(tǒng)需要做三件事：

1） 保存被調(diào)函數(shù)的計(jì)算結(jié)果；

2） 恢復(fù)上層參數(shù)（釋放被調(diào)函數(shù)的數(shù)據(jù)區(qū)）；

3） 依照被調(diào)函數(shù)保存的返回地址，將控制轉(zhuǎn)移回調(diào)用函數(shù)。

同時(shí)考慮到遞歸調(diào)用算法需要系統(tǒng)提供隱式棧來執(zhí)行，所以在將復(fù)雜的遞歸算法改寫成非遞歸算法時(shí)，必須引入棧。下面給出基于棧的二叉樹中序遍歷非遞歸算法的C語言實(shí)現(xiàn)：

void InOrder（Tnode root）

//中序遍歷二叉樹的非遞歸算法

{ int top=0；

p=root；

L1：if（p！=NULL） //遍歷左子樹

{ top+=2；

if（top>m） return； //棧滿退出

s[top-1]=p； //本層參數(shù)進(jìn)棧

s[top]=L2； //返回地址進(jìn)棧

p=p→L_child； //給下層參數(shù)賦值

goto L1； //轉(zhuǎn)向開始

L2： Visit（p→Data）； //訪問根

top+=2；

if（top>m） return； //棧滿溢出

s[top-1]=p； //遍歷右子樹

s[top]=L3；

p=p→R_child；

goto L1；}

L3：if（top！=0）

{ addr=s[top]；

p=s[top-1]； //取出返回地址

top=top-2； //退出本層參數(shù)

goto addr；}}

5 結(jié)束語

二叉樹的遍歷是進(jìn)行二叉樹其他操作的基礎(chǔ)，如二叉樹的線索化、二叉樹的構(gòu)造、二叉樹的還原等等，都要用到二叉樹的遍歷算法。二叉樹的遍歷算法可以采用遞歸算法，也可以采用非遞歸算法。遞歸算法具有簡潔明了的優(yōu)點(diǎn)，程序代碼短，容易理解，但是遞歸算法的執(zhí)行效率往往不高，而非遞歸算法雖然語法上稍顯繁瑣，但是卻有著執(zhí)行效率高、應(yīng)用環(huán)境廣的特點(diǎn)。

參考文獻(xiàn)：

[1] 陳衛(wèi)衛(wèi)， 王慶瑞. 數(shù)據(jù)結(jié)構(gòu)與算法[M]. 北京：高等教育出版社， 2010.

[2] 耿國華. 數(shù)據(jù)結(jié)構(gòu)——用C語言描述[M]. 北京：高等教育出版社， 2011.