二叉數(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) //從右子樹回來

cout << p->element;

if ( !s.IsEmpty( ))

Cnode = s.pop( );

p = Cnode.ptr;

else

return;

4)Cnode.tag = 1;

s.push(Cnode);

p = p->Right; //從左子樹回來//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前序遍歷--訪問結(jié)點的操作發(fā)生在遍歷其左右子樹之前

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

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

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

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

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

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

(1)訪問結(jié)點本身(N)，

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

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

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

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

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

(2)訪問結(jié)點本身(N)，

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

對于中序遍歷，就是先訪問左子樹，再訪問根節(jié)點，最后訪問右子樹;

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

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

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

(3)訪問結(jié)點本身(N)，

對于后序遍歷，就是先訪問左子樹，再訪問右子樹，最后訪問根節(jié)點;

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

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

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

② LNR:中序遍歷(InorderTraversal)

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

③ LRN:后序遍歷(PostorderTraversal)

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

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

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

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

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

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

§ 對T進行前序遍歷是先訪問樹根n,然后依次前序遍歷T1,T2,..,Tk。

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

§ 對T進行后序遍歷是先依次對T1,T2,..,Tk進行后序遍歷，最后訪問樹根n。

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

void InOrder(BinTree T)

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

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

② printf("%c"，T->data); // 訪問結(jié)點 ③ 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)存申請節(jié)點空間

(*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 . . 運行結(jié)果:

圖二:

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

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

運行結(jié)果: