4中二叉樹(shù)的遍歷方式介紹

對(duì)于一種數(shù)據(jù)結(jié)構(gòu)而言，遍歷是常見(jiàn)操作。二叉樹(shù)是一種基本的數(shù)據(jù)結(jié)構(gòu)，是一種每個(gè)節(jié)點(diǎn)的兒子數(shù)目都不多于2的樹(shù)。二叉樹(shù)的節(jié)點(diǎn)聲明如下：

typedef struct TreeNode *PtrToNode;

typedef struct TreeNode *BinTree;

struct TreeNode

{

int Data; //為簡(jiǎn)單起見(jiàn)，不妨假設(shè)樹(shù)節(jié)點(diǎn)的元素為int型

BinTree Left;

BinTree Right;

};

二叉樹(shù)的遍歷主要有先序遍歷，中序遍歷，后序遍歷，層序遍歷四種方式，下面一一介紹。

1. 先序遍歷

在先序遍歷中，對(duì)節(jié)點(diǎn)的訪問(wèn)工作是在它的左右兒子被訪問(wèn)之前進(jìn)行的。換言之，先序遍歷訪問(wèn)節(jié)點(diǎn)的順序是根節(jié)點(diǎn)-左兒子-右兒子。由于樹(shù)可以通過(guò)遞歸來(lái)定義，所以樹(shù)的常見(jiàn)操作用遞歸實(shí)現(xiàn)常常是方便清晰的。遞歸實(shí)現(xiàn)的代碼如下：

void PreOrderTraversal(BinTree BT)

{

if( BT )

{

printf(“%d\n”, BT->Data); //對(duì)節(jié)點(diǎn)做些訪問(wèn)比如打印

PreOrderTraversal(BT->Left); //訪問(wèn)左兒子

PreOrderTraversal(BT->Right); //訪問(wèn)右兒子

}

}

由遞歸代碼可以看出，該遞歸為尾遞歸（尾遞歸即遞歸形式在函數(shù)末尾或者說(shuō)在函數(shù)即將返回前）。尾遞歸的遞歸調(diào)用需要用棧存儲(chǔ)調(diào)用的信息，當(dāng)數(shù)據(jù)規(guī)模較大時(shí)容易越出棧空間。雖然現(xiàn)在大部分的編譯器能夠自動(dòng)去除尾遞歸，但是即使如此，我們不妨自己去除。非遞歸先序遍歷算法基本思路：使用堆棧

a. 遇到一個(gè)節(jié)點(diǎn)，訪問(wèn)它，然后把它壓棧，并去遍歷它的左子樹(shù)；

b. 當(dāng)左子樹(shù)遍歷結(jié)束后，從棧頂彈出該節(jié)點(diǎn)并將其指向右兒子，繼續(xù)a步驟；

c. 當(dāng)所有節(jié)點(diǎn)訪問(wèn)完即最后訪問(wèn)的樹(shù)節(jié)點(diǎn)為空且?？諘r(shí)，停止。

實(shí)現(xiàn)代碼如下：

void PreOrderTraversal(BinTree BT)

{

BinTree T = BT;

Stack S = CreatStack(MAX_SIZE); //創(chuàng)建并初始化堆棧S

while(T || !IsEmpty(S))

{

while(T) //一直向左并將沿途節(jié)點(diǎn)訪問(wèn)（打印）后壓入堆棧

{

printf("%d\n", T->Data);

Push(S, T);

T = T->Left;

}

if (!IsEmpty(S))

{

T = Pop(S); //節(jié)點(diǎn)彈出堆棧

T = T->Right; //轉(zhuǎn)向右子樹(shù)

}

}

}

2. 中序遍歷

中序遍歷的遍歷路徑與先序遍歷完全一樣。其實(shí)現(xiàn)的思路也與先序遍歷非常相似。其主要的不同點(diǎn)是訪問(wèn)節(jié)點(diǎn)順序不同：中序遍歷是訪問(wèn)完所有左兒子后再訪問(wèn)根節(jié)點(diǎn)，最后訪問(wèn)右兒子，即為左兒子-根節(jié)點(diǎn)-右兒子。

遞歸實(shí)現(xiàn)的代碼如下:

void InOrderTraversal(BinTree BT)

{

if(BT)

{

InOrderTraversal(BT->Left);

printf("%d\n", BT->Data);

InOrderTraversal(BT->Right);

}

}

非遞歸輔助棧實(shí)現(xiàn)代碼如下:

void InOrderTraversal(BinTree BT)

{

BinTree T = BT;

Stack S = CreatStack(MaxSize); //創(chuàng)建并初始化堆棧S

while(T || !IsEmpty(S))

{

while(T) //一直向左并將沿途節(jié)點(diǎn)壓入堆棧

{

Push(S,T);

T = T->Left;

}

if(!IsEmpty(S))

{

T = Pop(S); //節(jié)點(diǎn)彈出堆棧

printf("%d\n", T->Data); //（訪問(wèn)） 打印結(jié)點(diǎn)

T = T->Right; //轉(zhuǎn)向右子樹(shù)

}

}

}

非遞歸不用輔助棧實(shí)現(xiàn)中序遍歷：

試設(shè)計(jì)一個(gè)非遞歸算法，按中根順序遍歷非線索二叉樹(shù)，但不得用任何輔助棧。在執(zhí)行算法期間，允許改變左孩子指針和右孩子指針的值。

算法：右線索化+回溯

若當(dāng)前樹(shù)的根節(jié)點(diǎn)p有左孩子且未被線索化：將其左孩子的最右結(jié)點(diǎn)（可為左孩子本身）指向p，即右線索化，然后p = p->lChild；

若p有左孩子但已被線索化，說(shuō)明該p是回溯上來(lái)的，即左孩子已經(jīng)被訪問(wèn)了，則釋放線索化的指針；

若p無(wú)左孩子，打印p，向上回溯(即p = p->rChild)。

代碼如下：

/*

輸入：ABDH##I##E##CF#J##G##

*/

#include

typedef struct BTNode* Position;

typedef Position BTree;

typedef char ElementType;

struct BTNode {

ElementType data;

Position lChild, rChild;

};

BTree CreateBTree(void);

void Inorder(BTree bt);

int main()

{

BTree bt = CreateBTree();

Inorder(bt);

return 0;

}

void Inorder(BTree bt)

{

Position p = bt;

while (p)

{

Position pLeft = p->lChild;

if (pLeft)

{

while (pLeft->rChild && pLeft->rChild != p) //找到以p為根結(jié)點(diǎn)的樹(shù)的最右孩子

pLeft = pLeft->rChild;

if (pLeft->rChild == NULL) //線索化

{

pLeft->rChild = p;

p = p->lChild;

continue;

}

else //線索化后已被訪問(wèn)

{

pLeft->rChild = NULL; //釋放指向根節(jié)點(diǎn)(祖先)的指針

}

}

printf("%c ", p->data); //打印

p = p->rChild; //向上回溯或者轉(zhuǎn)向右子樹(shù)

}

printf("\n");

}

BTree CreateBTree() //按照先序序列建立二叉樹(shù)

{

BTree bt = NULL;

char ch;

scanf("%c", &ch);

if (ch != '#') //'#'代表空節(jié)點(diǎn)

{

bt = new BTNode;

bt->data = ch;

bt->lChild = CreateBTree();

bt->rChild = CreateBTree();

}

return bt;

}

運(yùn)行結(jié)果：

參考博客：http://m.blog.csdn.net/blog/Raito__/40618257

3. 后序遍歷

后序遍歷與中序遍歷，先序遍歷的路徑也完全一樣。主要的不同點(diǎn)是后序遍歷訪問(wèn)節(jié)點(diǎn)的順序是先訪問(wèn)左兒子和右兒子，最后訪問(wèn)節(jié)點(diǎn)，即左兒子-右兒子-根節(jié)點(diǎn)。

遞歸實(shí)現(xiàn)思路與中序遍歷和先序遍歷相似，代碼如下:

void PostOrderTraversal(BinTree BT)

{

if (BT)

{

PostOrderTraversal(BT->Left);

PostOrderTraversal(BT->Right);

printf("%d\n", BT->Data);

}

}

后序遍歷的非遞歸實(shí)現(xiàn)

思路一：

對(duì)于一個(gè)節(jié)點(diǎn)而言，要實(shí)現(xiàn)訪問(wèn)順序?yàn)樽髢鹤?右兒子-根節(jié)點(diǎn)，可以利用后進(jìn)先出的棧，在節(jié)點(diǎn)不為空的前提下，依次將根節(jié)點(diǎn)，右兒子，左兒子壓棧。故我們需要按照根節(jié)點(diǎn)-右兒子-左兒子的順序遍歷樹(shù)，而我們已經(jīng)知道先序遍歷的順序是根節(jié)點(diǎn)-左兒子-右兒子，故只需將先序遍歷的左右調(diào)換并把訪問(wèn)方式打印改為壓入另一個(gè)棧即可。最后一起打印棧中的元素。代碼如下：

void PostOrderTraversal(BinTree BT)

{

BinTree T = BT;

Stack S1 = CreatStack(MAX_SIZE); //創(chuàng)建并初始化堆棧S1

Stack S2 = CreatStack(MAX_SIZE); //創(chuàng)建并初始化堆棧S2

while(T || !IsEmpty(S1))

{

while(T) //一直向右并將沿途節(jié)點(diǎn)訪問(wèn)（壓入S2）后壓入堆棧S1

{

Push(S2, T);

Push(S1, T);

T = T->Right;

}

if (!IsEmpty(S1))

{

T = Pop(S1); //節(jié)點(diǎn)彈出堆棧

T = T->Left; //轉(zhuǎn)向左子樹(shù)

}

}

while(!IsEmpty(S2)) //訪問(wèn)（打?。㏒2中元素

{

T = Pop(S2);

printf("%d\n", T->Data);

}

}

思路一的優(yōu)點(diǎn)是由于利用了先序遍歷的思想，代碼較簡(jiǎn)潔，思路較清晰。缺點(diǎn)是需要用一個(gè)棧來(lái)存儲(chǔ)樹(shù)的所有節(jié)點(diǎn)，空間占用較大。

思路二：

要訪問(wèn)一個(gè)節(jié)點(diǎn)的條件上一個(gè)訪問(wèn)的節(jié)點(diǎn)是右兒子。我們可以增加一個(gè)變量Prev來(lái)判斷當(dāng)前節(jié)點(diǎn)Curr的上一個(gè)節(jié)點(diǎn)與它的關(guān)系來(lái)執(zhí)行相應(yīng)的操作。

若Prev為空(Curr節(jié)點(diǎn)是根節(jié)點(diǎn))或者Prev是Curr的父節(jié)點(diǎn)，將Curr節(jié)點(diǎn)的左孩子和右孩子分別壓入棧；

若Prev是Curr的左兒子，則將Curr的右兒子壓入棧；

否則Prev是Curr的右兒子，訪問(wèn)Curr;

代碼如下:

void PostOrderTraversal(BinTree BT)

{

if(BT == NULL)

return ;

Stack S = CreatStack(MAX_SIZE);

BinTree Prev = NULL , Curr = NULL; //初始化

s.push(BT);

while(!IsEmpty(S))

{

Curr = Top(S); //將棧頂元素賦給Curr

if(Prev == NULL || Prev->Left == Curr || Prev->Right == Curr) //若Prev為NULL或是Curr的父節(jié)點(diǎn)

{

if(Curr->Left != NULL)

Push(S, Curr->Left);

else if(Curr->Right != NULL)

Push(S, Curr->Right);

}

else if(Curr->Left == Prev) //若Prev是Curr的左兒子

{

if(Curr->Right != NULL)

Push(S, Curr->Right);

}

else

{

printf("%d\n", Curr->Data); //訪問(wèn)當(dāng)前節(jié)點(diǎn)

Pop(S); //訪問(wèn)后彈出

}

Prev = Curr; //處理完當(dāng)前節(jié)點(diǎn)后將Curr節(jié)點(diǎn)變?yōu)镻rev節(jié)點(diǎn)

}

}

4. 層序遍歷

二叉樹(shù)遍歷的核心問(wèn)題是二維結(jié)構(gòu)的線性化。我們通過(guò)節(jié)點(diǎn)訪問(wèn)其左右兒子時(shí)，存在的問(wèn)題是訪問(wèn)左兒子后，右兒子怎么訪問(wèn)。因此我們需要一個(gè)存儲(chǔ)結(jié)構(gòu)保存暫時(shí)不訪問(wèn)的節(jié)點(diǎn)。前面三種遍歷方式的非遞歸實(shí)現(xiàn)，我們是通過(guò)堆棧來(lái)保存。事實(shí)上也可以通過(guò)隊(duì)列來(lái)保存。

隊(duì)列實(shí)現(xiàn)的基本思路：遍歷從根節(jié)點(diǎn)開(kāi)始，首先將根節(jié)點(diǎn)入隊(duì)，然后執(zhí)行循環(huán)：節(jié)點(diǎn)出隊(duì)，訪問(wèn)（訪問(wèn)）根節(jié)點(diǎn)，將左兒子入隊(duì)，將右兒子入隊(duì)，直到隊(duì)列為空停止。

這種遍歷方式的結(jié)果是將二叉樹(shù)從上到下，從左至右一層一層的遍歷，即層序遍歷，代碼實(shí)現(xiàn)如下:

void LevelOrderTraversal(BinTree BT)

{

BinTree T;

Queue Q; //聲明一個(gè)隊(duì)列

if (BT == NULL)

return; //如果樹(shù)為空，直接返回

Q = CreatQueue(MAX_SIZE); //創(chuàng)建并初始化隊(duì)列

AddQ(Q, BT); //將根節(jié)點(diǎn)入隊(duì)

while (!IsEmpty(Q))

{

T = DeleteQ(Q); //節(jié)點(diǎn)出隊(duì)

printf("%d\n", T->Data); //訪問(wèn)出隊(duì)的節(jié)點(diǎn)

if (T->Left) AddQ(Q, T->Left); //若左兒子不為空，將其入隊(duì)

if (T->Right) AddQ(Q, T->Right) //若右兒子不為空，將其入隊(duì)

}

}