數(shù)據(jù)結(jié)構(gòu)樹的試驗(yàn)報(bào)告

本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)樹的試驗(yàn)報(bào)告數(shù)據(jù)結(jié)構(gòu)

實(shí)驗(yàn)報(bào)告

目的要求

1．把握二叉樹的存儲實(shí)現(xiàn)。

2．把握二叉樹的遍歷思想。

3．把握二叉樹的常見算法的程序?qū)崿F(xiàn)。

試驗(yàn)內(nèi)容

1．輸入字符序列，建立二叉鏈表。2．中序遍歷二叉樹:遞歸算法。3．中序遍歷二叉樹:非遞歸算法。（最好也能實(shí)現(xiàn)先序，后序非遞歸算法）4．求二叉樹的高度。

5．求二叉樹的葉子個數(shù)。

6．借助隊(duì)列實(shí)現(xiàn)二叉樹的層次遍歷。

7．在主函數(shù)中設(shè)計(jì)一個簡單的菜單，分別調(diào)試上述算法。

源程序：

1.頭文件：棧和隊(duì)列stack#include#include#defineTRUE1#defineFALSE0#defineOK1#defineERROR0

#defineOVERFLOW-2typedefcharTElemType;typedefstructBiTNode{TElemTypedata;

structBiTNode*lchild,*rchild;}BiTNode,*BiTree;typedefBiTreeSElemType;typedefBiTreeQElemType;typedefBiTreeStatus;

typedefstructNode{//鏈棧的定義SElemTypedata;structNode*next;}NODE;

typedefstruct{

NODE*top;//鏈?zhǔn)綏５臈ｍ斨羔榼Stack;

//鏈?zhǔn)綏５牟僮骼鐅oidInitStack(Stackif(!S.top)exit(OVERFLOW);//分派失敗S.top->next=NULL;

}

intStackEmpty(StackS){

if(S.top->next==NULL)return(TRUE);elsereturn(FALSE);}

voidPush(Stack

p=(NODE*)malloc(sizeof(NODE));if(!p)exit(OVERFLOW);//分派失敗p->data=e;

p->next=S.top->next;S.top->next=p;}

voidPop(Stack

if(StackEmpty(S))return;//?？誩lse{p=S.top->next;e=p->data;

S.top->next=p->next;free(p);}}

//隊(duì)的操作

typedefstructQNode{QElemTypedata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;

voidInitQueue(LinkQueueif(!Q.front)exit(OVERFLOW);//存儲分派失敗Q.front->next=NULL;}

intEnQueue(LinkQueue

p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(OVERFLOW);p->data=e;

p->next=NULL;

Q.rear->next=p;Q.rear=p;returnOK;}

intDeQueue(LinkQueueQueuePtrp;p=Q.front->next;e=p->data;

Q.front->next=p->next;

if(Q.rear==p)Q.rear=Q.front;free(p);returnOK;}

2.主程序

#include#include#include\#include\

inth=0,max=0,flag=0;//全局變量voidCreateBiTree(BiTreescanf(\if(ch=='')T=NULL;else{

T=(BiTree)malloc(sizeof(BiTNode));T->data=ch;

CreateBiTree(T->lchild);CreateBiTree(T->rchild);}}

//2．中序遍歷二叉樹:遞歸算法。voidzhbianli(BiTreeT){

if(!T)return;

zhbianli(T->lchild);printf(\zhbianli(T->rchild);}

//先序非遞歸遍歷

voidxifbianli(BiTreeT){BiTreep;

StackS;

InitStack(S);if(T)Push(S,T);

while(!StackEmpty(S)){Pop(S,p);printf(\if(p->rchild)Push(S,p->rchild);if(p->lchild)Push(S,p->lchild);}}

//3．中序遍歷二叉樹:非遞歸算法。voidzhfbianli(BiTreeT){BiTreep;StackS;

InitStack(S);p=T;

while(p||!StackEmpty(S)){if(p){Push(S,p);p=p->lchild;}else{Pop(S,p);if(p)printf(\p=p->rchild;}}}

//后序非遞歸遍歷

voidhofbianli(BiTreeT){

BiTreep;StackS;

InitStack(S);p=T;

while(T||!StackEmpty(S)){

if(T){

Push(S,T);T=T->lchild;

}else{

T=S.top->next->data;

if(T->rchild==NULL||T->rchild==p){

printf(\Pop(S,T);p=T;

T=NULL;}else{

T=T->rchild;}}}}

//4.求二叉樹的高度。inthight(BiTreeT){

inth,hl,hr;if(T){if(!T->lchildelse{hl=hight(T->lchild);hr=hight(T->rchild);h=(hl>hr?hl:hr)+1;}}elseh=0;return(h);}

//5.求二叉樹的葉子個數(shù)intleaf(BiTreeT){intn;

if(!T)n=0;else

if(!T->lchild

elsen=leaf(T->lchild)+leaf(T->rchild);

return(n);}

//8．借助隊(duì)列實(shí)現(xiàn)二叉樹的層次遍歷。voidduiliebianli(BiTreeT){

LinkQueueQ;InitQueue(Q);

if(T==NULL)return;BiTreep=T;

printf(\

if(p->lchild)EnQueue(Q,p->lchild);if(p->rchild)EnQueue(Q,p->rchild);while(Q.front!=Q.rear){DeQueue(Q,p);

printf(\

if(p->lchild)EnQueue(Q,p->lchild);if(p->rchild)EnQueue(Q,p->rchild);}

return;}

voidmain(){

BiTreeroot;intselect;

printf(\二叉樹試驗(yàn)\\n\

printf(\建立二叉樹，輸入字符序列:\\n\CreateBiTree(root);do{printf(\中序遞歸遍歷2中序非遞歸遍歷序列\(zhòng)\n\printf(\先序非遞歸遍歷序列4.后序非遞歸遍歷序列\(zhòng)\n\printf(\計(jì)算葉子6.計(jì)算高度\\n\printf(\隊(duì)列實(shí)現(xiàn)二叉樹的層次遍歷\\n\printf(\請輸入選擇：\scanf(\switch(select){case1:printf(\中序遞歸遍歷序列：\zhbianli(root);break;case2:printf(\中序非遞歸遍歷序列：\zhfbianli(root);break;case3:printf(\先序非遞歸遍歷序列：\

xifbianli(root);break;case4:printf(\后序非遞歸遍歷序列：\hofbianli(root);break;case5:printf(\二叉樹中葉子個數(shù)為：%d\\n\break;case6:hight(root);printf(\二叉樹中高度為：%d\\n\break;case7:printf(\隊(duì)列實(shí)現(xiàn)二叉樹的層次遍歷：\duiliebianli(root);break;case0:break;default:printf(\輸入選項(xiàng)錯誤！重新輸入！\\n\}

}while(select);}

程序運(yùn)行截圖

1.建立二叉樹

2.中序遞歸遍歷

3.中序非遞歸遍歷序列

4.先序非遞歸遍歷序列

5.后序非遞歸遍歷序列

6..計(jì)算葉子

7.計(jì)算高度

8．隊(duì)列實(shí)現(xiàn)二叉樹的層次遍歷

試驗(yàn)總結(jié)

這次的二叉樹試驗(yàn)，整體來說還是很有難度的，由于二叉樹的遍歷要用到遞歸，比較難理解，而且非遞歸算法更加繁雜，規(guī)律性更強(qiáng)。雖然說完成了本次的試驗(yàn)，但是還是感覺有不少地方理解的不是很透徹，現(xiàn)在想想真正有技術(shù)含量的東西大都不是我自