基于單鏈表的二叉樹非遞歸遍歷算法

王防修，周 康

(武漢工業(yè)學(xué)院數(shù)學(xué)與計算機(jī)學(xué)院，湖北武漢430023)

二叉樹是一種重要的非線性數(shù)據(jù)結(jié)構(gòu)，其應(yīng)用［1-4］相當(dāng)廣泛。因此，掌握二叉樹的各種特性是靈活使用二叉樹的基礎(chǔ)。在二叉樹的所有特性中，二叉樹的遍歷是需要掌握的重點。傳統(tǒng)遍歷二叉樹的方式一般采用遞歸遍歷算法［5-9］。然而，這種遞歸遍歷算法存在明顯缺點：①算法難以反映二叉樹被訪問的詳細(xì)過程;②在遍歷過程中需要消耗大量系統(tǒng)?？臻g;③遞歸算法比非遞歸算法需要花費更多的時間。

因此，為了克服二叉樹遞歸遍歷算法的這些缺點，相繼出現(xiàn)了二叉樹的非遞歸算法［10-17］。從這些論文的內(nèi)容可以明顯發(fā)現(xiàn)，所有遍歷二叉樹的非遞歸遍歷算法都需要借助棧或隊列來實現(xiàn)。如二叉樹的先序遍歷、中序遍歷和后序遍歷需要借助棧實現(xiàn)非遞歸算法，而二叉樹的層次遍歷需要借助隊列實現(xiàn)非遞歸算法。從現(xiàn)有的研究成果可以看出，所有的非遞歸遍歷二叉樹的算法都采用靜態(tài)?；蜢o態(tài)隊列來存儲節(jié)點地址。事實上，在未遍歷一棵二叉樹之前，是無法知道該二叉樹到底包含多少節(jié)點的。這直接導(dǎo)致靜態(tài)棧和靜態(tài)隊列應(yīng)該分配多大的內(nèi)存空間才比較合適的問題。如果空間分配太小，就會在遍歷過程中出現(xiàn)?？臻g或隊列空間不足的情形;相反，如果棧空間或隊列空間定義過大，對遍歷小規(guī)模的二叉樹又是一種內(nèi)存空間浪費。因此，如果不能精確定義棧空間和隊列空間的大小，就會大大限制二叉樹的非遞歸算法的應(yīng)用范圍和解決實際問題的能力。

本方案通過引入單鏈表并對其操作加以限制，從而得到鏈棧和鏈隊列。由于鏈棧和鏈隊列都能根據(jù)需要動態(tài)增加和減少各自的?？臻g和隊列空間，使得將鏈棧和鏈隊列應(yīng)用于二叉樹的非遞歸遍歷算法，就不會出現(xiàn)?？臻g和隊列空間浪費或不足的情形。因此，鏈棧和鏈隊列可以很好解決目前非遞歸遍歷二叉樹存在的缺點，大大提高非遞歸遍歷二叉樹算法的通用性。

1 鏈棧和鏈隊列的模塊設(shè)計

單鏈表的插入和刪除位置是任意的，可以是表首、表尾或表的中間任意位置。如果限定元素的插入和刪除只能在表首進(jìn)行，此時的單鏈表就變成鏈棧。同樣，如果限定只能在單鏈表的表首刪除元素，而在單鏈表的表尾插入元素，則此時的單鏈表就變成鏈隊列。為方便算法描述，特將單鏈表定義如下：

typedef struct node*link;

struct node{

elsemtype data;

link next;};

1.1 鏈棧的模塊設(shè)計

1.1.1 鏈棧的初始化

void ini_stack(link*s){

*s=NULL;}

鏈棧的初始化說明，在做棧操作之前的棧是沒有?？臻g的空棧。

1.1.2 元素入棧

void push(link*s，elemtype x){

link q;

q=(link)malloc(sizeof(*q));

q-＞data=x;q-＞next=*s;*s=q;}

每當(dāng)有一個元素入棧，就首先為該元素申請一個節(jié)點的空間，然后將該元素保存在該節(jié)點的數(shù)據(jù)域中，最后將該節(jié)點在表首插入，使得新入棧的元素總在棧頂。

1.1.3 元素彈棧

int pop(link*s，elemtype*x){

link q;

if(*s==NULL)return 0;

else{q=*s;*s=q-＞next;*x=q-＞data;free(q);return 1;}

}

如果函數(shù)返回0，表示棧已經(jīng)空，沒有元素可以出棧。當(dāng)函數(shù)返回1，表示保存在*x中的出棧元素有效。每從棧中彈出一個元素，就回收單鏈表的表首節(jié)點。

從鏈棧的入棧和出棧操作可以發(fā)現(xiàn)，每成功入棧一個元素，鏈棧就增加一個節(jié)點的?？臻g，每成功出棧一個元素，鏈棧就減少一個節(jié)點的棧空間。

1.2 鏈隊列的模塊設(shè)計

1.2.1 鏈隊列的初始化

void ini_queue(link*front，link*rear){

*rear=*front=NULL;}

鏈隊列的初始化說明，在做隊列操作之前的鏈隊列是不占內(nèi)存空間的空隊列。

1.2.2 元素入隊模塊

void in_queue(link*front link，*rear，elemtype x){

link q;

q=(link)malloc(sizeof(*q));q-＞data=x;q-＞next=NULL;

if(*rear==NULL)*front=*rear=q;

else{(*rear)-＞next=q;*rear=q;}

}

每當(dāng)有一個元素入棧，就首先為該元素申請一個節(jié)點的空間，然后將該元素保存在該節(jié)點的數(shù)據(jù)域中，最后將該節(jié)點在表尾插入，使得新入隊的元素總在隊尾。需要注意的是，當(dāng)?shù)谝粋€元素入隊時，需要同時改變隊首指針，而不僅僅是隊尾指針。

1.2.3 元素出隊模塊

int out_queue(link*front，link*rear，elemtype*x){

link q;

if(*front==NULL)return 0;

else{q=*front;*front=q-＞next;*x=q-＞data;free(q);

if(*front==NULL)*rear=NULL;return 1;}

}

如果函數(shù)返回0，表示隊列已空，沒有元素可以出隊。當(dāng)函數(shù)返回1，表示保存在*x中的出隊元素有效。每從隊列中出隊一個元素，就回收單鏈表的表首節(jié)點。如果此時隊中只有一個元素可以出隊，注意出隊之后需要同時修改隊首和隊尾指針。

2 二叉樹的非遞歸遍歷算法描述

2.1 使用鏈棧的非遞歸遍歷算法

二叉樹的遍歷一般表現(xiàn)為先序遍歷、中序遍歷和后序遍歷三種。這三者的遞歸算法很簡單，但其非遞歸算法只有在深入理解二叉樹以及棧的先進(jìn)后出特性之后才能得到。

2.1.1 先序遍歷二叉樹的非遞歸算法

步驟1 首先將根節(jié)點入棧。

步驟2 彈出棧頂節(jié)點并訪問該節(jié)點。如果該節(jié)點的右孩子非空，則將其右孩子入棧。如果該節(jié)點的左孩子不空，則將其左孩子入棧。

步驟3 重復(fù)步驟2，直至?？諡橹?。

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

步驟1 從二叉樹的根節(jié)點出發(fā)，沿著左子樹一直往下走，將暫時不能處理的節(jié)點都入棧，直到找到一個節(jié)點的左子樹為空為止，并將該節(jié)點入棧。

步驟2 如果棧不空，則從棧中彈出一個節(jié)點并訪問之。

步驟3 轉(zhuǎn)向步驟2中被訪問節(jié)點的右孩子。

步驟4 重復(fù)步驟2和步驟3，直到棧空并且二叉樹中的所有節(jié)點被訪問為止。

2.1.3 后序遍歷二叉樹的非遞歸算法

步驟1 首先將根節(jié)點入棧。

步驟2 每次從棧中彈出一個節(jié)點，為了保證先訪問左右子樹后再訪問根節(jié)點，要檢查該節(jié)點的左、右子樹是否已經(jīng)被訪問過。如果未被訪問，則將該節(jié)點的右、左孩子依次入棧。如果已被訪問，則彈出該節(jié)點并訪問之。

步驟3 重復(fù)步驟2，直至棧空為止。

2.2 使用鏈隊列的二叉樹層次遍歷算法

步驟1 首先將根節(jié)點入隊。

步驟2 每次從隊首取出一個節(jié)點并訪問之，如果該節(jié)點的左孩子不為空，則將左孩子入隊;如果該節(jié)點的右孩子不空，則將右孩子入隊。

步驟3 重復(fù)步驟2，直至隊空為止。

3 算法實現(xiàn)

為了更加清楚地表達(dá)本文的主旨，有必要對上面介紹的部分算法的實現(xiàn)加以呈現(xiàn)。通過這兩個算法的實現(xiàn)，將更能體現(xiàn)鏈棧和鏈隊列在解決棧空間或隊列空間方面的優(yōu)勢?，F(xiàn)將二叉樹定義如下：

type struct node1*bintree;

struct node1{

datatyrpe data;

bintree lchild，rchild};

3.1 用鏈棧實現(xiàn)先序遍歷二叉樹的非遞歸算法

void preorder1(bintree t){

link s=NULL，q;bintree p;int flag;

if(t! =NULL)push(＆s，t);

while(s!=NULL)

{flag=pop(＆s，＆p);//彈棧

顯示出棧元素;

if(p-＞rchild! =NULL)push(＆s，p-＞rchild);//如果右孩子非空，則右孩子入棧

if(p-＞lchild! =NULL)push(＆s，p-＞lchild);//如果左孩子非空，則左孩子入棧

}}

3.2 用鏈隊列實現(xiàn)層次遍歷二叉樹的非遞歸算法

void level_order(bintree t)

{bintree p;int flag;link front，rear，q;

front=rear=NULL;

if(t! =NULL)in_queue(＆front，＆rear，t);//根節(jié)點入隊

while(front!=NULL)

{flag=out_queue(＆front，＆rear，＆p);//出隊

顯示出隊元素;

if(p-＞lchild! =NULL)in_queue(＆front，＆rear，p-＞lchild);//左孩子入隊

if(p-＞rchild! =NULL)in_queue(＆front，＆rear，p-＞rchild);//右孩子入隊

}}

4 算法測試

現(xiàn)給出如圖1和圖2所示的二叉樹，當(dāng)將其進(jìn)行非遞歸遍歷，分別得到如表1和表2所示的結(jié)果。

圖1 7個節(jié)點的二叉樹

圖2 11個節(jié)點的二叉樹

表1 7個節(jié)點的二叉樹非遞歸遍歷結(jié)果

表2 11個節(jié)點的二叉樹非遞歸遍歷結(jié)果

表中的A(1)表示字符A在棧頂或表首時，此時的單鏈表的長度為1，其他如此類推。從表1和表2的結(jié)果可以明顯發(fā)現(xiàn)：①非遞歸遍歷所需要的?？臻g和隊列空間都比二叉樹的節(jié)點數(shù)少;②不同結(jié)構(gòu)的二叉樹，它對?？臻g和隊列空間的需求量是不一樣的;(3)二叉樹遍歷所需的棧空間和隊列空間是沒有任何規(guī)律的。

因此，采用動態(tài)分配?？臻g和隊列空間能夠按需分配二叉樹所需要的內(nèi)存空間，只要內(nèi)存空間足夠大，能夠適合于任意二叉樹的非遞歸遍歷。

5 結(jié)束語

基于單鏈表實現(xiàn)鏈棧和鏈隊列的方法，實現(xiàn)了?？臻g和隊列空間的動態(tài)增加和減少，大大提高了非遞歸遍歷二叉樹的適用范圍，同時降低了內(nèi)存空間的浪費，提高了二叉樹的遍歷速度，且能在任何情況下按需分配棧空間和隊列空間?？傊?，只要內(nèi)存空間允許，鏈棧和鏈隊列在實現(xiàn)二叉樹的非遞歸遍歷算法的過程中總能滿足算法對?？臻g和隊列空間的需求。

［1］ 裴洪虎，郭銳鋒.三角形二叉樹在數(shù)控加工仿真中的應(yīng)用［J］.計算機(jī)工程，2011，37(21)：214-216，219.

［2］ 孫文勝，劉婷.一種改進(jìn)的基于二叉樹搜索的防碰撞算法［J］.計算機(jī)工程，2011，37(10)：257-259.

［3］ 周燕，侯整風(fēng).基于有序二叉樹的快速多模式字符串匹配算法［J］.計算機(jī)工程，2010，36(17)：42-44.

［4］ 范柏超，王建宇.結(jié)合特征選擇的二叉樹SVM多分類算法［J］.計算機(jī)工程與設(shè)計，2010，31(12)：2883-2885.

［5］ 楊智明.基于二叉樹前序遍歷的遞歸算法分析［J］.保山學(xué)院學(xué)報，2010(2)：62-64.

［6］ 郭金華，占明.淺議二叉樹的遍歷［J］.科技信息，2010(17)：65.

［7］ 尹幫治.基于鏈棧數(shù)組的二叉樹按層遍歷遞歸算法［J］.重慶科技學(xué)院學(xué)報，2009，11(3)：167-169.

［8］ 尹幫治.二叉樹遍歷的通用遞歸算法研究與實現(xiàn)［J］.電腦知識與技術(shù)，2008(3)：132-134.

［9］ 郝陽陽.二叉樹遍歷方法的研究和應(yīng)用［J］.內(nèi)江科技，2008(4)：45.

［10］ 陳宇，于洋.遍歷二叉樹的非遞歸算法［J］.計算機(jī)應(yīng)用，2009(9)：160，146.

［11］ 羅帥.二叉樹遍歷的非遞歸算法分析與實現(xiàn)［J］.電腦知識與技術(shù)，2008(2)：678-680.

［12］ 張亞萍，陳得寶.二叉樹遍歷教學(xué)方法研究［J］.牡丹江師范學(xué)院學(xué)報，2010，73(4)：69-70.

［13］ 黃霞.二叉樹的先序遍歷和中序遍歷的非遞歸算法［J］.電腦開發(fā)與應(yīng)用，2009，23(1)：53-54，59.

［14］ 黃霞.二叉樹后序遍歷的非遞歸算法［J］.現(xiàn)代計算機(jī)，2009(10)：57-60.

［15］ 孫毅，張麗.新型二叉樹后序遍歷非遞歸算法［J］.金陵科技學(xué)院學(xué)報，2008，24(1)：27-29.

［16］ 柴寶杰，馬弘偉.用棧無標(biāo)記變量后序遍歷二叉樹算法［J］.牡丹江師范學(xué)院學(xué)報，2008，64(3)：18-20.

［17］ 馬相芬.中序遍歷二叉樹的算法實現(xiàn)［J］.科技信息，2008(12)：227，281.