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

2012-01-15 03:52:04王防修

武漢輕工大學學報 2012年4期

王防修，周康

(武漢工業學院數學與計算機學院，湖北武漢430023)

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

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

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

1 鏈棧和鏈隊列的模塊設計

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

typedef struct node*link;

struct node{

elsemtype data;

link next;};

1.1 鏈棧的模塊設計

1.1.1 鏈棧的初始化

void ini_stack(link*s){

*s=NULL;}

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

1.1.2 元素入棧

void push(link*s，elemtype x){

link q;

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

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

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

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;}

}

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

從鏈棧的入棧和出棧操作可以發現，每成功入棧一個元素，鏈棧就增加一個節點的棧空間，每成功出棧一個元素，鏈棧就減少一個節點的?？臻g。

1.2 鏈隊列的模塊設計

1.2.1 鏈隊列的初始化

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

*rear=*front=NULL;}

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

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;}

}

每當有一個元素入棧，就首先為該元素申請一個節點的空間，然后將該元素保存在該節點的數據域中，最后將該節點在表尾插入，使得新入隊的元素總在隊尾。需要注意的是，當第一個元素入隊時，需要同時改變隊首指針，而不僅僅是隊尾指針。

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;}

}

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

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

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

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

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

步驟1 首先將根節點入棧。

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

步驟3 重復步驟2，直至棧空為止。

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

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

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

步驟3 轉向步驟2中被訪問節點的右孩子。

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

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

步驟1 首先將根節點入棧。

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

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

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

步驟1 首先將根節點入隊。

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

步驟3 重復步驟2，直至隊空為止。

3 算法實現

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

type struct node1*bintree;

struct node1{

datatyrpe data;

bintree lchild，rchild};

3.1 用鏈棧實現先序遍歷二叉樹的非遞歸算法

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 用鏈隊列實現層次遍歷二叉樹的非遞歸算法

void level_order(bintree t)

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

front=rear=NULL;

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

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 算法測試

現給出如圖1和圖2所示的二叉樹，當將其進行非遞歸遍歷，分別得到如表1和表2所示的結果。

圖1 7個節點的二叉樹

圖2 11個節點的二叉樹

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

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

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

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

5 結束語

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

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

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

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

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

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

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

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

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

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

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

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

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