王防修，周 康

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

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

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

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

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

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

typedef struct node*link;

struct node{

elsemtype data;

link next;};

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

1.1.1 鏈棧的初始化

void ini_stack(link*s){

*s=NULL;}

鏈棧的初始化說(shuō)明，在做棧操作之前的棧是沒(méi)有?？臻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)有一個(gè)元素入棧，就首先為該元素申請(qǐng)一個(gè)節(jié)點(diǎn)的空間，然后將該元素保存在該節(jié)點(diǎn)的數(shù)據(jù)域中，最后將該節(jié)點(diǎn)在表首插入，使得新入棧的元素總在棧頂。

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)空，沒(méi)有元素可以出棧。當(dāng)函數(shù)返回1，表示保存在*x中的出棧元素有效。每從棧中彈出一個(gè)元素，就回收單鏈表的表首節(jié)點(diǎn)。

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

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

1.2.1 鏈隊(duì)列的初始化

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

*rear=*front=NULL;}

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

1.2.2 元素入隊(duì)模塊

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)有一個(gè)元素入棧，就首先為該元素申請(qǐng)一個(gè)節(jié)點(diǎn)的空間，然后將該元素保存在該節(jié)點(diǎn)的數(shù)據(jù)域中，最后將該節(jié)點(diǎn)在表尾插入，使得新入隊(duì)的元素總在隊(duì)尾。需要注意的是，當(dāng)?shù)谝粋€(gè)元素入隊(duì)時(shí)，需要同時(shí)改變隊(duì)首指針，而不僅僅是隊(duì)尾指針。

1.2.3 元素出隊(duì)模塊

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，表示隊(duì)列已空，沒(méi)有元素可以出隊(duì)。當(dāng)函數(shù)返回1，表示保存在*x中的出隊(duì)元素有效。每從隊(duì)列中出隊(duì)一個(gè)元素，就回收單鏈表的表首節(jié)點(diǎn)。如果此時(shí)隊(duì)中只有一個(gè)元素可以出隊(duì)，注意出隊(duì)之后需要同時(shí)修改隊(duì)首和隊(duì)尾指針。

2 二叉樹(shù)的非遞歸遍歷算法描述

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

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

2.1.1 先序遍歷二叉樹(shù)的非遞歸算法

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

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

步驟3 重復(fù)步驟2，直至?？諡橹埂?/p>

2.1.2 中序遍歷二叉樹(shù)的非遞歸算法

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

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

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

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

2.1.3 后序遍歷二叉樹(shù)的非遞歸算法

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

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

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

2.2 使用鏈隊(duì)列的二叉樹(shù)層次遍歷算法

步驟1 首先將根節(jié)點(diǎn)入隊(duì)。

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

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

3 算法實(shí)現(xiàn)

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

type struct node1*bintree;

struct node1{

datatyrpe data;

bintree lchild，rchild};

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

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 用鏈隊(duì)列實(shí)現(xiàn)層次遍歷二叉樹(shù)的非遞歸算法

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é)點(diǎn)入隊(duì)

while(front!=NULL)

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

顯示出隊(duì)元素;

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

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

}}

4 算法測(cè)試

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

圖1 7個(gè)節(jié)點(diǎn)的二叉樹(shù)

圖2 11個(gè)節(jié)點(diǎn)的二叉樹(shù)

表1 7個(gè)節(jié)點(diǎn)的二叉樹(shù)非遞歸遍歷結(jié)果

表2 11個(gè)節(jié)點(diǎn)的二叉樹(shù)非遞歸遍歷結(jié)果

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

因此，采用動(dòng)態(tài)分配棧空間和隊(duì)列空間能夠按需分配二叉樹(shù)所需要的內(nèi)存空間，只要內(nèi)存空間足夠大，能夠適合于任意二叉樹(shù)的非遞歸遍歷。

5 結(jié)束語(yǔ)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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