二叉樹的基本操作實(shí)驗(yàn)報(bào)告

學(xué)號(hào)姓名實(shí)驗(yàn)日期2012-12-26實(shí)驗(yàn)室計(jì)算機(jī)軟件技術(shù)實(shí)驗(yàn)指導(dǎo)教師設(shè)備編號(hào)401實(shí)驗(yàn)內(nèi)容二叉樹的基本操作一實(shí)驗(yàn)題目實(shí)現(xiàn)二叉樹的基本操作的代碼實(shí)現(xiàn)二實(shí)驗(yàn)?zāi)康?、掌握二叉樹的基本特性2、掌握二叉樹的先序、中序、后序的遞歸遍歷算法3、通過求二叉樹的深度、度為2的結(jié)點(diǎn)數(shù)和葉子結(jié)點(diǎn)數(shù)等算法三實(shí)習(xí)要求（1）認(rèn)真閱讀書上給出的算法（2）編寫程序并獨(dú)立調(diào)試四、給出二叉樹的抽象數(shù)據(jù)類型ADTBinaryTree{//數(shù)據(jù)對(duì)象D：D是具有相同特性的數(shù)據(jù)元素的集合。

//數(shù)據(jù)關(guān)系R：

//若D=Φ，則R=Φ，稱BinaryTree為空二叉樹；

//若D≠Φ，則R={H}，H是如下二元關(guān)系；

//（1）在D中存在惟一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H下無前驅(qū)；

//（2）若D-{root}≠Φ，則存在D-{root}={D1,Dr}，且D1∩Dr=Φ；

//（3）若D1≠Φ，則D1中存在惟一的元素x1，<root,x1>∈H，且存在D1上的關(guān)系H1?H；若Dr≠Φ，則Dr中存在惟一的元素xr，<root,xr>∈H，且存在上的關(guān)系Hr?H；H={<root,x1>,<root,xr>,H1,Hr}；

//（4）(D1,{H1})是一棵符合本定義的二叉樹，稱為根的左子樹；(Dr,{Hr})是一棵符合本定義的二叉樹，稱為根的右子樹。//基本操作：

CreateBiTree(&T,definition)

//初始條件：definition給出二叉樹T的定義。

//操作結(jié)果：按definiton構(gòu)造二叉樹T。BiTreeDepth(T)

//初始條件：二叉樹T存在。

//操作結(jié)果：返回T的深度。PreOrderTraverse(T,visit())

//初始條件：二叉樹T存在，Visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。

//操作結(jié)果：先序遍歷T，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。一旦visit()失敗，則操作失敗。InOrderTraverse(T,visit())

//初始條件：二叉樹T存在，Visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。

//操作結(jié)果：中序遍歷T，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。一旦visit()失敗，則操作失敗。PostOrderTraverse(T,visit())

//初始條件：二叉樹T存在，Visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。

//操作結(jié)果：后序遍歷T，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。一旦visit()失敗，則操作失敗。LeafNodes(p)

//初始條件：二叉樹T存在。

//操作結(jié)果：返回T的葉子結(jié)點(diǎn)數(shù)。BothNodes(p)

//初始條件：二叉樹T存在。//操作結(jié)果：返回T的度為2的結(jié)點(diǎn)數(shù)。五、詳細(xì)設(shè)計(jì)1、給出本數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)定義#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineNULL0#defineOVERFLOW-22、實(shí)現(xiàn)二叉樹的抽象數(shù)據(jù)類型如下:typedef int Status;typedef char TElemType;定義二叉樹的數(shù)據(jù)元素類型為chr3、存儲(chǔ)實(shí)現(xiàn)的抽象數(shù)據(jù)類型如下：typedef struct BiTNode0120{ TElemType data; struct BiTNode0120 *lchild;//左孩子指針 struct BiTNode0120 *rchild;//右孩子指針}BiTNode0120,*BiTree;4、運(yùn)算的函數(shù)聲明：StatusCreateBiTree0120(BiTreeT,definition)//構(gòu)建二叉樹StatusPreOrder0120(BiTreep)//先序遍歷StatusInOrder0120(BiTreep)//中序遍歷StatusPostOrder0120(BiTreep)//后序遍歷StatusBTNodeDepth0120(BiTreep)//求二叉樹的深度StatusLeafNodes0120(BiTreep,int*i)//求二叉樹葉子結(jié)點(diǎn)的個(gè)數(shù)voidgetDataFromFile0120(charfileName[],BiTree&root);StatusBothNodes0120(BiTreep,int*i)//求度為2的結(jié)點(diǎn)數(shù)5、給出操作實(shí)現(xiàn)的偽碼StatuscreateBiTree0120(BiTree&root,charin[],intbegin1,intend1,charpost[],intbegin2,intend2){//根據(jù)給定的中序序列in,后序序列post,構(gòu)造二叉樹root //其中：begin1，end1分別為叉樹的中序序列在in[]中的開始位置（序號(hào)，數(shù)組下標(biāo)+1）、結(jié)束位置；//其中：begin2，end2分別為叉樹的后序序列在post[]中的開始位置（序號(hào)，數(shù)組下標(biāo)+1）、結(jié)束位置； charr; inti;intm1;//中序序列中，左子樹根位置 intm2;//后序序列中，左子樹最后一個(gè)結(jié)點(diǎn)位置if(begin1-end1!=begin2-end2)returnERROR; if(end1-begin1>=0){ root=(BiTree)malloc(sizeof(BiTNode)); r=post[end2]; root->data=r;//根 for(i=begin1;i<=end1;i++) if(in[i]==r)break; m1=i-1; m2=begin2+i-begin1-1; root->lchild=NULL; root->rchild=NULL; if(createBiTree0120(root->lchild,in,begin1,m1,post,begin2,m2)==ERROR)//構(gòu)造左子樹 printf("初始化二叉樹出錯(cuò)！\n\n請(qǐng)檢查初始數(shù)據(jù)！\n\n"); if(createBiTree0120(root->rchild,in,m1+2,end1,post,m2+1,end2-1)==ERROR)//構(gòu)造右子樹 printf("初始化二叉樹出錯(cuò)！\n\n請(qǐng)檢查初始數(shù)據(jù)！\n\n");}else{ root=NULL;} returnOK;}voidgetDataFromFile0120(charfileName[],BiTree&root){//從文件fileName中讀取數(shù)據(jù)構(gòu)造二叉樹root FILE*fp; charinOrder0120[100]; charpostOrder0120[100]; inta1,a2,b1,b2; fp=fopen(fileName,"r"); fscanf(fp,"%s\n",inOrder0120);fscanf(fp,"%s\n",postOrder0120); fclose(fp);a1=strlen("inOrder0120:");//中序序列第一個(gè)字符位置 a2=strlen(inOrder0120)-1;;//中序序列最后一個(gè)字符位置b1=strlen("postOrder0120:");//后序序列第一個(gè)字符位置 b2=strlen(postOrder0120)-1;//后序序列最后一個(gè)字符位置 if(createBiTree0120(root,inOrder0120,a1,a2,postOrder0120,b1,b2)==ERROR) printf("初始化二叉樹出錯(cuò)！\n\n請(qǐng)檢查初始數(shù)據(jù)！\n\n"); else printf("初始化二叉樹成功！");}StatusPreOrder0120(BiTreep){//先序遍歷二叉樹if(p!=NULL){ printf("%c",p->data); PreOrder0120(p->lchild); PreOrder0120(p->rchild);} returnOK;}StatusInOrder0120(BiTreep){//中序遍歷二叉樹if(p!=NULL){ InOrder0120(p->lchild); printf("%c",p->data); InOrder0120(p->rchild);} returnOK;}StatusPostOrder0120(BiTreep){//后序遍歷二叉樹if(p!=NULL){ PostOrder0120(p->lchild); PostOrder0120(p->rchild); printf("%c",p->data);}returnOK;}StatusBTNodeDepth0120(BiTreep){//求二叉樹的深度 intlchilddep,rchilddep; if(p==NULL) return0; else{lchilddep=BTNodeDepth0120(p->lchild);rchilddep=BTNodeDepth0120(p->rchild); return(lchilddep>rchilddep)?(lchilddep+1):(rchilddep+1); } returnOK;}StatusLeafNodes0120(BiTreep,int*i){//求二叉樹的葉子結(jié)點(diǎn) intj; if(p!=NULL) { if(p->lchild!=NULL||p->rchild!=NULL) { j=*i; j++; *i=j; } LeafNodes0120(p->lchild,i); LeafNodes0120(p->rchild,i); returnOK; }}StatusBothNodes0120(BiTreep,int*i){//求度為2的結(jié)點(diǎn)數(shù) intj; if(p!=NULL) { if(p->lchild!=NULL&&p->rchild!=NULL) { j=*i; j++; *i=j; } BothNodes0120(p->lchild,i); BothNodes0120(p->rchild,i); returnOK; }}六、實(shí)驗(yàn)環(huán)境1.環(huán)境：宿舍。2.硬件：2048M內(nèi)存，500G硬盤。 3.系統(tǒng)：Windows764位操作系統(tǒng)4.軟件平臺(tái)：MicrosoftVisualC++6.0簡(jiǎn)體中文版七、相關(guān)文件列表如下demo.cpp:主程序文件bitree.cpp:操作實(shí)現(xiàn)的算法bitree.h：函數(shù)聲明Mydef.h：存儲(chǔ)結(jié)構(gòu)的定義八、程序的運(yùn)行測(cè)試及結(jié)果測(cè)試用例1：構(gòu)造二叉樹測(cè)試用例2：先序遍歷測(cè)試用例3：中序遍歷測(cè)試用例4：后序遍歷測(cè)試用例