《數(shù)據(jù)結(jié)構(gòu)》試驗(yàn)提醒

本文格式為Word版，下載可任意編輯——《數(shù)據(jù)結(jié)構(gòu)》試驗(yàn)提醒

《數(shù)據(jù)結(jié)構(gòu)》試驗(yàn)提醒

試驗(yàn)五、二叉樹(shù)的基本操作和應(yīng)用

（1）先定義宏，再定義元素、二叉樹(shù)的順序表等的類(lèi)型，并聲明順序表的基本操作。例如如下：

#include\#include\#include\#defineTRUE1#defineFALSE0#defineOK1#defineERROR0

typedefintStatus;

typedefcharElemType[6];//元素類(lèi)型typedefstructNode{

ElemTypedata;structNode*lchild;structNode*rchild;

}BiTNode,*BiTree;//二叉樹(shù)的二叉鏈表結(jié)構(gòu)

StatusCreateBiTree(BiTree//二叉樹(shù)的建立算法voidPreOrder(BiTreeroot);//先根遍歷算法voidInOrder(BiTreeroot);//中根遍歷算法voidPostOrder(BiTreeT);//后根遍歷算法

StatusPostOrder1(BiTreeT,Status(*Visit)(ElemTypee));//后根遍歷算法StatusVisit(ElemTypee);//訪問(wèn)結(jié)點(diǎn)數(shù)據(jù)

（2）二叉樹(shù)的基本操作例如如下：

StatusCreateBiTree(BiTreescanf(\

if(ch[0]=='.')T=NULL;else{

T=(BiTree)malloc(sizeof(BiTNode));//建立根結(jié)點(diǎn)strcpy(T->data,ch);

CreateBiTree(T->lchild);//建立左子樹(shù)CreateBiTree(T->rchild);//建立右子樹(shù)}

returnOK;

1

《數(shù)據(jù)結(jié)構(gòu)》試驗(yàn)提醒

}//CreateBiTree

StatusVisit(ElemTypee)

{//訪問(wèn)結(jié)點(diǎn)數(shù)據(jù)，輸出元素e的值

printf(\returnOK;}

voidInOrder(BiTreeroot){//中根遍歷算法if(root!=NULL){

InOrder(root->lchild);Visit(root->data);InOrder(root->rchild);}}

voidPreOrder(BiTreeroot){//先根遍歷算法

//不完整，要自己完善

}

StatusPostOrder1(BiTreeT,Status(*Visit)(ElemTypee)){//后根遍歷算法

//不完整，要自己完善

}//PostOrder1

（3）按層遍歷，需要使用隊(duì)列，隊(duì)列元素、順序隊(duì)列的等的類(lèi)型定義及其基本操作等

的聲明例如如下：

typedefBiTreeQElemType;//隊(duì)列的元素類(lèi)型QElemType，為二叉樹(shù)結(jié)點(diǎn)類(lèi)型的指針

typedefstruct{

QElemType*base;//動(dòng)態(tài)分派的存儲(chǔ)空間intfront;intrear;}Sueue;//順序隊(duì)列

StatusInitQueue(Sueue//循環(huán)隊(duì)列初始化

StatusEnQueue(Sueue//進(jìn)隊(duì)算法

2

《數(shù)據(jù)結(jié)構(gòu)》試驗(yàn)提醒

StatusDeQueue(Sueue//出隊(duì)算法StatusEmptyQueue(SueueQ);//循環(huán)隊(duì)列判空

（4）順序隊(duì)列的基本操作例如如下：

StatusEmptyQueue(SueueQ)……

StatusInitQueue(Sueue//否則返回ERROR。

if(Q.front==Q.rear)returnERROR;//隊(duì)列空……

}//DeQueue

（5）按層次遍歷二叉樹(shù)的算法如下：

StatusLevelTraverTree(BiTreeT){//按層次遍歷二叉樹(shù)

SueueQ;//循環(huán)隊(duì)列QElemTypee;

InitQueue(Q);//循環(huán)隊(duì)列初始化EnQueue(Q,T);//進(jìn)隊(duì)while(!EmptyQueue(Q)){

DeQueue(Q,e);//出隊(duì)