二叉樹(shù)及其遍歷算法的應(yīng)用

王愛(ài)法， 楊梅梅，福春霞

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

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

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

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

1 二叉樹(shù)中序遍歷的算法實(shí)現(xiàn)

二叉樹(shù)中序遍歷的算法實(shí)現(xiàn)包括遞歸算法和非遞歸算法。

1.1 遞歸算法

遞歸算法是一種直接或間接地調(diào)用自身算法的過(guò)程。在計(jì)算機(jī)編寫(xiě)程序中，遞歸算法對(duì)解決一大類問(wèn)題是十分有效的，它往往使算法的描述簡(jiǎn)潔且易于理解。

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

先序遍歷：

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; //函數(shù)不會(huì)執(zhí)行到這一步，不會(huì)返回Error。這樣寫(xiě)只是為了沒(méi)有編譯警告。

}

else

return OK; //當(dāng)T為空樹(shù)時(shí)，停止遞歸。

}

中序遍歷：

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 非遞歸算法

二叉樹(shù)的非遞歸遍歷要借助堆棧來(lái)實(shí)現(xiàn)，具體算法為：

1) 設(shè)置一個(gè)堆棧進(jìn)行初始化。

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

3) 當(dāng)堆棧非空時(shí)，重復(fù)執(zhí)行下列步驟：① 出棧會(huì)取得一個(gè)結(jié)點(diǎn)指針，對(duì)該結(jié)點(diǎn)進(jìn)行訪問(wèn)；② 若該結(jié)點(diǎn)的右孩子不是空，則該結(jié)點(diǎn)的右子樹(shù)指針進(jìn)棧；③ 若該結(jié)點(diǎn)的左孩子不是空，則該結(jié)點(diǎn)的左子樹(shù)指針進(jìn)棧。

二叉樹(shù)遍歷的非遞歸算法相對(duì)于遞歸算法，減少了函數(shù)調(diào)用等開(kāi)銷，具有性能優(yōu)勢(shì)。

先序遍歷：

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

{

Stack *S; //棧S中存儲(chǔ)指向樹(shù)結(jié)點(diǎn)的指針。

BiTree p;

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

InitStack(S);

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

while (!StackEmpty(S))

{

//獲取棧頂指針，如果棧頂指針不為空，訪問(wèn)該結(jié)點(diǎn)。并將該結(jié)點(diǎn)的左子樹(shù)進(jìn)棧。

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

{

if (!Visit(p->data))

return ERROR;

Push(S,p->lchild);

}

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

else

{

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

if (!StackEmpty(S))

{

Pop(S,&p); //已被訪問(wèn)過(guò)的根結(jié)點(diǎn)退棧。此時(shí)，該退棧結(jié)點(diǎn)的左子樹(shù)已被全部訪問(wèn)過(guò)。

Push(S,p->rchild); //右子樹(shù)進(jìn)棧。

}

}

}

return OK;

}

中序遍歷：

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

{

Stack *S;

BiTree p;

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

InitStack(S);

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

while (!StackEmpty(S))

{

//向左走到盡頭

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

{

Push(S,p->lchild);

}

//空指針退棧

Pop(S,&p);

//訪問(wèn)節(jié)點(diǎn)，并向右一步

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指向已訪問(wèn)過(guò)的最后一個(gè)結(jié)點(diǎn)。

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

InitStack(S);

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

while (!StackEmpty(S))

{

//獲取棧頂指針，如果當(dāng)前結(jié)點(diǎn)有左子樹(shù)，并且左子樹(shù)結(jié)點(diǎn)不是剛被訪問(wèn)的節(jié)點(diǎn)。如果當(dāng)前結(jié)點(diǎn)有右子樹(shù)，并且右子樹(shù)結(jié)點(diǎn)不是剛被訪問(wèn)的結(jié)點(diǎn)。

//表明棧頂指針指向的樹(shù)結(jié)點(diǎn)未被訪問(wèn)，且左子樹(shù)和右子樹(shù)均未被訪問(wèn)。此時(shí)，將結(jié)點(diǎn)的左子樹(shù)進(jìn)棧。

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

Push(S,p->lchild);

//如果棧頂指針的右子樹(shù)存在，且未被訪問(wèn)。則將右子樹(shù)進(jìn)棧

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

Push(S,p->rchild);

//如果左子樹(shù)和右子樹(shù)均被訪問(wèn)過(guò)，則結(jié)點(diǎn)退棧，并進(jìn)行訪問(wèn)。更新pre。

else

{

Pop(S,&p);

if (!Visit(p->data))

return ERROR;

pre = p;

}

}

return OK;

}

對(duì)照遞歸算法和非遞歸算法可以發(fā)現(xiàn)：遞歸算法簡(jiǎn)潔、易懂、可讀性強(qiáng)，程序的編寫(xiě)和調(diào)試也很方便，但是因?yàn)檫f歸算法需要通過(guò)系統(tǒng)內(nèi)部的進(jìn)棧和出棧來(lái)實(shí)現(xiàn)，因此消耗的時(shí)間和空間多，運(yùn)行效率低。非遞歸算法應(yīng)用指針和堆棧，進(jìn)行出棧和入棧的方法實(shí)現(xiàn)了算法，非遞歸算法程序總體來(lái)說(shuō)較長(zhǎng)，編寫(xiě)和調(diào)試要費(fèi)些時(shí)間，但因?yàn)槠湟恢痹谡{(diào)用其他函數(shù)進(jìn)行進(jìn)棧出棧，所以其占用的空間較少、用時(shí)也較短。

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

1) 遞歸算法時(shí)間復(fù)雜度O(2n)

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

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

圖1 二叉樹(shù)

2) 非遞歸時(shí)間復(fù)雜度O(n)

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

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

綜上可知，二叉樹(shù)的遞歸遍歷的代碼實(shí)現(xiàn)比較簡(jiǎn)單，但是一般需要調(diào)用自身，容易出錯(cuò)；二叉樹(shù)的非遞歸遍歷的代碼實(shí)現(xiàn)相對(duì)復(fù)雜，但不易出錯(cuò)。而遞歸算法的時(shí)間復(fù)雜度要遠(yuǎn)遠(yuǎn)大于非遞歸算法的時(shí)間復(fù)雜度，所以遞歸算法的效率比較低，應(yīng)用率低。