二叉樹及其遍歷算法的應用

王愛法， 楊梅梅，福春霞

(重慶理工大學 a.理學院; b.期刊社， 重慶 400054)

同一數據元素類中的數據元素之間的關系表示數據結構。它有4種常見的結構：集合、樹結構、線性結構和圖形結構。在計算機中，樹是一種表示元素層次和分支的非線性結構。樹形結構是一種常用的、重要的數據結構，在日常生活與學習中得到了廣泛的應用，比如判斷家族關系、部門機構設置等[1-6]。二叉樹是樹形結構的一種，二叉樹是一個連通的無環(huán)圖，由一個根元素和左子樹、右子樹構成[2-16]。

遍歷是指沿著某條特定的路線來搜索，對樹中各個結點依次做一次訪問，要將所有結點都遍歷一次方可結束。許多樹的應用都是基于樹的遍歷來實現的，例如查找元素、插入元素等。二叉樹的基本的遍歷規(guī)則有3種：前序遍歷、中序遍歷和后序遍歷。對于每一種遍歷，樹中每個結點都要經過3次。前序遍歷在第1次遇到結點時立即訪問，中序遍歷在第2次遇到結點時訪問，后序遍歷則在第3次遇到結點時才訪問。因為樹的定義本身就是遞中序歸定義，因此采用遞歸的方法去實現樹的3種遍歷不僅容易理解而且代碼很簡潔。而對于樹的遍歷若采用非遞歸的方法，就要采用棧去模擬實現。在3種遍歷中，前序和中序遍歷的非遞歸算法都很容易實現，非遞歸后序遍歷實現起來相對難一點。

二叉樹在計算科學中有著重要的作用，如計算機操作系統(tǒng)中的文件管理、編譯程序的語法結構和數據庫系統(tǒng)信息組織形式等；在生活中，二叉樹可以用在密碼學中，利用二叉樹的先序遍歷、后序便利、中序遍歷對密碼進行加密和解密；在經濟中，二叉樹可以用來研究期權的定價模型。所以，二叉樹及二叉樹的遍歷在生活中、學科學習中都有很重要的作用。下面我們著重介紹一下二叉樹中序遍歷的2種算法。

1 二叉樹中序遍歷的算法實現

二叉樹中序遍歷的算法實現包括遞歸算法和非遞歸算法。

1.1 遞歸算法

遞歸算法是一種直接或間接地調用自身算法的過程。在計算機編寫程序中，遞歸算法對解決一大類問題是十分有效的，它往往使算法的描述簡潔且易于理解。

遞歸算法解決問題的特點：① 遞歸就是在過程或函數里調用自身；② 在使用遞歸策略時，必須有一個明確的遞歸結束條件，稱為遞歸出口；③ 遞歸算法解題通常顯得很簡潔，但遞歸算法解題的運行效率較低，所以一般不提倡用遞歸算法設計程序；④ 在遞歸調用的過程當中系統(tǒng)為每一層的返回點、局部量等開辟了棧來存儲。遞歸次數過多容易造成棧溢出等，所以一般不提倡用遞歸算法設計程序。

先序遍歷：

Int PreOrder(BiTree T,Int(*Visit)(TElemType e))

{

if (T)

{

if (Visit(T->data))

if (PreOrder(T->lchild,Visit))

if (PreOrder(T->rchild,Visit))

return OK;

return ERROR; //函數不會執(zhí)行到這一步，不會返回Error。這樣寫只是為了沒有編譯警告。

}

else

return OK; //當T為空樹時，停止遞歸。

}

中序遍歷：

Int InOrder(BiTree T,Int(*Visit)(TElemType e))

{

if (T)

{

if (InOrder(T->lchild,Visit))

if (Visit(T->data))

if (InOrder(T->rchild,Visit))

return OK;

return ERROR;

}

else

return OK;

}

后序遍歷：

Int PostOrder(BiTree T,Int(*Visit)(TElemType e))

{

if (T)

{

if (PostOrder(T->lchild,Visit))

if (PostOrder(T->rchild,Visit))

if (Visit(T->data))

return OK;

return ERROR;

}

else

return OK;

}

1.2 非遞歸算法

二叉樹的非遞歸遍歷要借助堆棧來實現，具體算法為：

1) 設置一個堆棧進行初始化。

2) 把根節(jié)點所表示的指針入棧。

3) 當堆棧非空時，重復執(zhí)行下列步驟：① 出棧會取得一個結點指針，對該結點進行訪問；② 若該結點的右孩子不是空，則該結點的右子樹指針進棧；③ 若該結點的左孩子不是空，則該結點的左子樹指針進棧。

二叉樹遍歷的非遞歸算法相對于遞歸算法，減少了函數調用等開銷，具有性能優(yōu)勢。

先序遍歷：

Int PreOrder1(BiTree T,Int(*Visit)(TElemType e))

{

Stack *S; //棧S中存儲指向樹結點的指針。

BiTree p;

S = (Stack*)malloc(sizeof(Stack));

InitStack(S);

Push(S,T); //根指針進棧。

while (!StackEmpty(S))

{

//獲取棧頂指針，如果棧頂指針不為空，訪問該結點。并將該結點的左子樹進棧。

if (GetTop(S,&p) && p)

{

if (!Visit(p->data))

return ERROR;

Push(S,p->lchild);

}

//棧頂指針為空，表明之前壓入的左子樹或者右子樹為空。

else

{

Pop(S,&p); //空指針退棧

if (!StackEmpty(S))

{

Pop(S,&p); //已被訪問過的根結點退棧。此時，該退棧結點的左子樹已被全部訪問過。

Push(S,p->rchild); //右子樹進棧。

}

}

}

return OK;

}

中序遍歷：

Int InOrder1(BiTree T,Int(*Visit)(TElemType e))

{

Stack *S;

BiTree p;

S = (Stack *)malloc(sizeof(Stack));

InitStack(S);

Push(S,T); //根指針進棧

while (!StackEmpty(S))

{

//向左走到盡頭

while (GetTop(S,&p) && p)

{

Push(S,p->lchild);

}

//空指針退棧

Pop(S,&p);

//訪問節(jié)點，并向右一步

if (!StackEmpty(S))

{

Pop(S,&p);

if (!Visit(p->data))

return ERROR;

Push(S,p->rchild);

}

}

return OK;

}

后序遍歷：

Int PostOrder1(BiTree T,Int(*Visit)(TElemType e))

{

Stack *S;

BiTree p,pre=NULL;//pre指向已訪問過的最后一個結點。

S = (Stack*)malloc(sizeof(Stack));

InitStack(S);

Push(S,T);//根指針進棧

while (!StackEmpty(S))

{

//獲取棧頂指針，如果當前結點有左子樹，并且左子樹結點不是剛被訪問的節(jié)點。如果當前結點有右子樹，并且右子樹結點不是剛被訪問的結點。

//表明棧頂指針指向的樹結點未被訪問，且左子樹和右子樹均未被訪問。此時，將結點的左子樹進棧。

if (GetTop(S,&p) && p->lchild && pre != p->lchild && !(p->rchild && pre == p->rchild))

Push(S,p->lchild);

//如果棧頂指針的右子樹存在，且未被訪問。則將右子樹進棧

else if (p->rchild && pre != p->rchild)

Push(S,p->rchild);

//如果左子樹和右子樹均被訪問過，則結點退棧，并進行訪問。更新pre。

else

{

Pop(S,&p);

if (!Visit(p->data))

return ERROR;

pre = p;

}

}

return OK;

}

對照遞歸算法和非遞歸算法可以發(fā)現：遞歸算法簡潔、易懂、可讀性強，程序的編寫和調試也很方便，但是因為遞歸算法需要通過系統(tǒng)內部的進棧和出棧來實現，因此消耗的時間和空間多，運行效率低。非遞歸算法應用指針和堆棧，進行出棧和入棧的方法實現了算法，非遞歸算法程序總體來說較長，編寫和調試要費些時間，但因為其一直在調用其他函數進行進棧出棧，所以其占用的空間較少、用時也較短。

下面通過斐波那契的列子來說明遞歸算法與非遞歸算法的效率問題。由于斐波納契數列是以兔子的繁殖引入的，因此也叫“兔子數列”。它指的是這樣一個數列：0,1,1,2,3,5,8,13,…從這組數可以明顯看出這樣一個規(guī)律：從第3個數開始，后邊一個數一定是在其之前兩個數的和。在數學上，斐波納契數列可以用這樣的公式表示：F(0)=0；F(1)=1；F(n)=F(n-1)+F(n-2),n≥2。通過時間復雜度來比較2種算法的效率：

1) 遞歸算法時間復雜度O(2n)

由于使用遞歸時，其執(zhí)行步驟是：要得到后一個數，必須先計算出之前的兩個數，即在每個遞歸調用時都會觸發(fā)另外兩個遞歸調用，例如：要得到F(10)之前得先得到F(9)、F(8)，那么得到F(9)之前得先得到F(8)、F(7)、…如此遞歸下去。

從圖1可以看出：這樣的計算是以 2 的次方增長的。除此之外也可以看到：F(8)和F(7)的值都被多次計算，如果遞歸的深度越深，那么F(8)和F(7)的值會被計算更多次，但是這樣計算的結果都是一樣的，除了其中之一外，其余的都是浪費。遞歸算法在空間和時間上都比較浪費，占用內存也比較大，效率低下。

圖1 二叉樹

2) 非遞歸時間復雜度O(n)

創(chuàng)建一個數組，每次將前兩個數相加后直接賦給后一個數。這樣的話，有n個數就創(chuàng)建一個包含n個數的一維數組，所以空間復雜度為O(n)，由于只需從頭向尾遍歷一邊，所以時間復雜度也為O(n)。非遞歸算法雖然代碼較復雜，但是其在進棧出棧的過程中會釋放空間，時間復雜度和空間復雜度都較少，效率較高。

2 結束語

綜上可知，二叉樹的遞歸遍歷的代碼實現比較簡單，但是一般需要調用自身，容易出錯；二叉樹的非遞歸遍歷的代碼實現相對復雜，但不易出錯。而遞歸算法的時間復雜度要遠遠大于非遞歸算法的時間復雜度，所以遞歸算法的效率比較低，應用率低。