二叉數(shù)的遍歷舉例

Preorder traversal(中->左->右)

template<class T>

void PreOrder(BinaryNode<T>* t) // preorder traversal of *t.

{if(t)

{visit(t);

PreOrder(tàLeft);

PreOrder(tàRight);}

Inorder traversal(左->中->右)

//遞歸算法

template<class T>

void InOrder(BinaryNode<T>* t)

{if(t)

InOrder(tàLeft);

visit(t);

InOrder(tàRight);

//非遞歸算法

void Inorder(BinaryNode <T> * t)

Sack<BinaryNode<T>*> s(10);

BinaryNode<T> * p = t;

for ( ; ; )

while(p!=NULL)

s.push(p);

p = p->Left;

if (!s.IsEmpty( ))

p = s.pop( );

cout << p->element;

p = p->Right;

else

return

Postorder traversal(左->右->中)

//遞歸算法

template<class T>

void PostOrder(BinaryNode<T>* t)

if(t)

PostOrder(tàLeft);

PostOrder(tàRight);

visit(t)

//非遞歸算法

struct StkNode

BinaryNode <T> * ptr;

int tag;

vid Postorder(BinaryNode <T> * t)

Stack <StkNode<T>>s(10);

StkNode<T> Cnode;

BinaryNode<T> * p = t;

for( ; ; )

while (p!=NULL)

Cnode.ptr = p;

Cnode.tag = 0;

s.push(Cnode);

p = p->Left;

Cnode = s.pop( );

p = Cnode.ptr;

while ( Cnode.tag = = 1) //從右子樹回來(lái)

cout << p->element;

if ( !s.IsEmpty( ))

Cnode = s.pop( );

p = Cnode.ptr;

else

return;

4)Cnode.tag = 1;

s.push(Cnode);

p = p->Right; //從左子樹回來(lái)//for

Level order: it is a non-recursive function and a queue is used.

template<class T>

void LevelOrder(BinaryNode<T>* t)

LinkedQueue<BinaryNode<T>*> Q;

while(t)

visit(t); //visit t

if(tàLeft)

Q.Add(tàLeft);

if(tàRight)

Q.Add(tàRight);

try

Q.Delete(t);

}catch(OutOfBounds){return;}

· Preorder前序遍歷--訪問(wèn)結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之前

· Inorder中序遍歷--訪問(wèn)結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之間

· Postorder后序遍歷--訪問(wèn)結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之后

· Level order層次遍歷--按每一層的節(jié)點(diǎn)，從左到右逐次訪問(wèn)

在使用擴(kuò)展先序遍歷創(chuàng)建二叉樹時(shí)，首先要根據(jù)一棵二叉樹寫出它的先序遍歷序列，然后根據(jù)圖中各個(gè)節(jié)點(diǎn)左右孩子的 狀況進(jìn)行加點(diǎn)遍歷，凡是沒(méi)有左右孩子的節(jié)點(diǎn)，遍歷到它的左右孩子是都用"."表示它的左右孩子，注意這里面的"."只是用來(lái)表示它的父節(jié)點(diǎn)沒(méi)有它這個(gè)左孩子或右孩子，并不表示節(jié)點(diǎn)，所以在遍歷過(guò)程中應(yīng)該訪問(wèn)到"."就結(jié)束了，不能再沿著"."繼續(xù)遍歷。

所謂遍歷(Traversal)是指沿著某條搜索路線，依次對(duì)樹中每個(gè)結(jié)點(diǎn)均做一次且僅做一次訪問(wèn)。訪問(wèn)結(jié)點(diǎn)所做的操作依賴于具體的應(yīng)用問(wèn) 題。 遍歷是二叉樹上最重要的運(yùn)算之一，是二叉樹上進(jìn)行其它運(yùn)算之基礎(chǔ)。本節(jié)主要講二叉樹中遍歷過(guò)程，遍歷方法，重點(diǎn)介紹擴(kuò)展先序遍歷序列以及利用此序列創(chuàng)建二叉樹的過(guò)程，順便比較一下各種遍歷方法的異同和應(yīng)用。

從二叉樹的遞歸定義可知，一棵非空的二叉樹由根結(jié)點(diǎn)及左、右子樹這三個(gè)基本部分組成。因此，在任一給定結(jié)點(diǎn)上，可以按某種次序執(zhí)行三個(gè)操作:

(1)訪問(wèn)結(jié)點(diǎn)本身(N)，

(2)遍歷該結(jié)點(diǎn)的左子樹(L)，

(3)遍歷該結(jié)點(diǎn)的右子樹(R)。

根據(jù)遍歷的原則:先左后右，對(duì)于先序遍歷，顧名思義就是先訪問(wèn)根節(jié)點(diǎn)，再訪問(wèn)左子樹，最后訪問(wèn)右子樹，

從二叉樹的遞歸定義可知，一棵非空的二叉樹由根結(jié)點(diǎn)及左、右子樹這三個(gè)基本部分組成。因此，在任一給定結(jié)點(diǎn)上，可以按某種次序執(zhí)行三個(gè)操作:

(1)遍歷該結(jié)點(diǎn)的左子樹(L)，

(2)訪問(wèn)結(jié)點(diǎn)本身(N)，

(3)遍歷該結(jié)點(diǎn)的右子樹(R)。

對(duì)于中序遍歷，就是先訪問(wèn)左子樹，再訪問(wèn)根節(jié)點(diǎn)，最后訪問(wèn)右子樹;

從二叉樹的遞歸定義可知，一棵非空的二叉樹由根結(jié)點(diǎn)及左、右子樹這三個(gè)基本部分組成。因此，在任一給定結(jié)點(diǎn)上，可以按某種次序執(zhí)行三個(gè)操作:

(1)遍歷該結(jié)點(diǎn)的左子樹(L)，

(2)遍歷該結(jié)點(diǎn)的右子樹(R)。

(3)訪問(wèn)結(jié)點(diǎn)本身(N)，

對(duì)于后序遍歷，就是先訪問(wèn)左子樹，再訪問(wèn)右子樹，最后訪問(wèn)根節(jié)點(diǎn);

根據(jù)訪問(wèn)結(jié)點(diǎn)操作發(fā)生位置命名：

① NLR:前序遍歷(PreorderTraversal亦稱(先序遍歷))

--訪問(wèn)根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之前。

② LNR:中序遍歷(InorderTraversal)

--訪問(wèn)根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之中(間)。

③ LRN:后序遍歷(PostorderTraversal)

--訪問(wèn)根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之后。

樹的遍歷是樹的一種重要的運(yùn)算。所謂遍歷是指對(duì)樹中所有結(jié)點(diǎn)的系統(tǒng)的訪問(wèn)，即依次對(duì)樹中每個(gè)結(jié)點(diǎn)訪問(wèn)一次且僅訪問(wèn)一次。樹的3種最重要的遍歷方式分別稱為前序遍歷、中序遍歷和后序遍歷。以這3種方式遍歷一棵樹時(shí)，若按訪問(wèn)結(jié)點(diǎn)的先后次序?qū)⒔Y(jié)點(diǎn)排列起來(lái)，就可分別得到樹中所有結(jié)點(diǎn)的前序列表，中序列表和后序列表。相應(yīng)的結(jié)點(diǎn)次序分別稱為結(jié)點(diǎn)的前序、中序和后序。

樹的這3種遍歷方式可遞歸地定義如下:

§ 如果T是一棵空樹，那么對(duì)T進(jìn)行前序遍歷、中序遍歷和后序遍歷都是空操作，得到的列表為空表。

§ 如果T是一棵單結(jié)點(diǎn)樹，那么對(duì)T進(jìn)行前序遍歷、中序遍歷和后序遍歷都只訪問(wèn)這個(gè)結(jié)點(diǎn)。這個(gè)結(jié)點(diǎn)本身就是要得到的相應(yīng)列表。

§ 否則，設(shè)T如圖6所示，它以n為樹根，樹根的子樹從左到右依次為T1,T2,..,Tk，那么有:

§ 對(duì)T進(jìn)行前序遍歷是先訪問(wèn)樹根n,然后依次前序遍歷T1,T2,..,Tk。

§ 對(duì)T進(jìn)行中序遍歷是先中序遍歷T1，然后訪問(wèn)樹根n，接著依次對(duì)T2,T2,..,Tk進(jìn)行中序遍歷。

§ 對(duì)T進(jìn)行后序遍歷是先依次對(duì)T1,T2,..,Tk進(jìn)行后序遍歷，最后訪問(wèn)樹根n。

用二叉鏈表做為存儲(chǔ)結(jié)構(gòu)，先序遍歷算法可描述為:

void InOrder(BinTree T)

{ //算法里①~⑥是為了說(shuō)明執(zhí)行過(guò)程加入的標(biāo)號(hào)

① if(T) { // 如果二叉樹非空

② printf("%c"，T->data); // 訪問(wèn)結(jié)點(diǎn) ③ InOrder(T->lchild); ④ InOrder(T->rchild); ⑤ }

⑥ } // InOrder

void createBiTree(BiTree *bt){

char ch;

ch = getchar();

if(ch == '.')

*bt = NULL;

else{

*bt = (BiTree)malloc(sizeof(BiTNode));//向內(nèi)存申請(qǐng)節(jié)點(diǎn)空間

(*bt)->data = ch;

createBiTree(&((*bt)->LChild));//生成左子樹

createBiTree(&((*bt)->RChild));//生成右子樹

}

}/*createBiTree*/

/*==================打印二叉樹=============*/

void printTree(BiTree bt,int nLayer){

int i;

if(bt == NULL)

return ;

printTree(bt ->RChild,nLayer+1);

for(i=0;i<nLayer;i++)

printf(" ");

printf("%c\n",bt->data);

printTree(bt->LChild,nLayer+1);

}

圖一:

(a)1 2 4 . . 6 . . 3 . 5 . 7 . 8 . .

(b)1 2 4 . . 5 . . 3 6 . . 7 . . 運(yùn)行結(jié)果:

圖二:

(a)7 3 1 . . 2 . . 9 . 10 . 8 . 4 . .

(b)7 3 1 . . 5 4 . . . 11 10 . . 15 . .

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