數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告題目：二叉樹(shù)抽象數(shù)據(jù)類(lèi)型學(xué)院計(jì)算機(jī)學(xué)院專(zhuān)業(yè)計(jì)算機(jī)科學(xué)與技術(shù)年級(jí)班別學(xué)號(hào)學(xué)生姓名指導(dǎo)教師成績(jī)____________________2013年6月一．實(shí)驗(yàn)概要實(shí)驗(yàn)項(xiàng)目名稱(chēng):二叉樹(shù)抽象數(shù)據(jù)類(lèi)型的實(shí)現(xiàn)實(shí)驗(yàn)項(xiàng)目性質(zhì):設(shè)計(jì)性實(shí)驗(yàn)所屬課程名稱(chēng):數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)計(jì)劃學(xué)時(shí):6二.實(shí)驗(yàn)?zāi)康牧私舛鏄?shù)的定義以及各項(xiàng)基本操作。實(shí)現(xiàn)二叉樹(shù)存儲(chǔ)、遍歷及其他基本功能三.實(shí)驗(yàn)儀器設(shè)備和材料硬件：PC機(jī)軟件：VisualC++6.0四．實(shí)驗(yàn)的內(nèi)容1.二叉樹(shù)類(lèi)型定義以及各基本操作的簡(jiǎn)要描述；ADTBinaryTree{數(shù)據(jù)對(duì)象D:D是具有相同特性的數(shù)據(jù)元素的集合.數(shù)據(jù)關(guān)系R:若D=?，則R=,稱(chēng)BinaryTree為空二叉樹(shù)；若D≠，則R={H}，H是如下二元關(guān)系：在D中存在惟一的稱(chēng)為根的數(shù)據(jù)元素root，它在關(guān)系H下無(wú)前驅(qū)；若D-{root}≠?，則存在D-{root}={D1,Dr}，且D1∩Dr=?；若D1≠?，則D1中存在惟一的元素x1，<root，x1>∈H，且存在Dr上的關(guān)系Hr∈H；H={<root，x1>，<root，xr>，H1,Hr}；（D1，{H1}）是一棵符合本定義的二叉樹(shù)，稱(chēng)為根的左子樹(shù)，是一棵符合本定義的二叉樹(shù)，稱(chēng)為根的右子樹(shù)?；静僮鱌:InitBiTree(&T);操作結(jié)果：構(gòu)造空二叉樹(shù)T。DestroyBiTree(&T);初始條件：二叉樹(shù)T存在。操作結(jié)果：銷(xiāo)毀二叉樹(shù)T。CreateBiTree(&T,definition);初始條件：definition給出二叉樹(shù)T的定義。操作結(jié)果：按definition構(gòu)造二叉樹(shù)T。ClearBiTree(&T);初始條件：二叉樹(shù)T存在。操作結(jié)果：將二叉樹(shù)T清為空樹(shù)。BiTreeEmpty(T);初始條件：二叉樹(shù)T存在。操作結(jié)果：若T為空二叉樹(shù)，則返回TURE,否則FALSE。BiTreeDepth(T);初始條件：二叉樹(shù)T存在。操作結(jié)果：返回T的深度。Root(T);初始條件：二叉樹(shù)T存在。操作結(jié)果：返回T的根。Value(T,e);初始條件：二叉樹(shù)T存在，e是T中的某個(gè)結(jié)點(diǎn)。操作結(jié)果：返回e的值。Assign(T,&e,value);初始條件：二叉樹(shù)T存在，e是T中的某個(gè)結(jié)點(diǎn)。操作結(jié)果：結(jié)點(diǎn)e賦值為value。Parent(T,e);初始條件：二叉樹(shù)T存在，e是T中的某個(gè)結(jié)點(diǎn)。操作結(jié)果：若e是T的非跟結(jié)點(diǎn)，則返回它的雙親，否則返回“空”。LeftChild(T,e);初始條件：二叉樹(shù)T存在，e是T中的某個(gè)結(jié)點(diǎn)。操作結(jié)果：返回e的左孩子。若e無(wú)左孩子，則返回“空”。RightChild(T,e);初始條件：二叉樹(shù)T存在，e是T中的某個(gè)結(jié)點(diǎn)。操作結(jié)果：返回e的右孩子。若e無(wú)右孩子，則返回“空”。LeftSibling(T,e);初始條件：二叉樹(shù)T存在，e是T中的某個(gè)結(jié)點(diǎn)。操作結(jié)果：返回e的左兄弟。若e無(wú)左孩子或無(wú)左兄弟，則返回“空”。RightSibling(T,e);初始條件：二叉樹(shù)T存在，e是T中的某個(gè)結(jié)點(diǎn)。操作結(jié)果：返回e的右兄弟。若e無(wú)右孩子或無(wú)右兄弟，則返回“空”。}ADTBinaryTree2.存儲(chǔ)結(jié)構(gòu)：采用無(wú)頭結(jié)點(diǎn)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)3.源代碼：頭文件及存儲(chǔ)結(jié)構(gòu):#include<stdio.h>#include<stdlib.h>#defineTURE1#defineFALSE0#defineOK1#defineERROR0#defineOVERFLOW0#defineMAXQSIZE100//最大隊(duì)列長(zhǎng)度typedefcharTElemType;typedefstructBiTNode//二叉樹(shù)結(jié)構(gòu)體{ TElemTypedata; structBiTNode*lchild,*rchild;}BiTNode,*BiTree;typedefBiTreeQElemType;typedefstructQNode{ QElemTypedata; structQNode*next;}QNode,*QueuePtr;//結(jié)點(diǎn)結(jié)構(gòu)體typedefstruct{ QueuePtrfront; QueuePtrrear;}LinkQueue; //鏈隊(duì)列結(jié)構(gòu)體算法設(shè)計(jì)：intInitQueue(LinkQueue&Q)//構(gòu)造空隊(duì)列{ Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); if(!Q.front)//存儲(chǔ)分配失敗 exit(OVERFLOW); Q.front->next=NULL; returnOK;}intEnQueue(LinkQueue&Q,QElemTypee)//新元素入隊(duì)尾{ QueuePtrp; p=(QueuePtr)malloc(sizeof(QNode)); if(!p)//存儲(chǔ)分配失敗 exit(OVERFLOW); p->data=e; p->next=NULL; Q.rear->next=p; Q.rear=p; returnOK;}intDeQueue(LinkQueue&Q,QElemType&e)//刪除隊(duì)頭元素{ QueuePtrp; if(Q.front==Q.rear)//隊(duì)列為空隊(duì) returnERROR; p=Q.front->next; e=p->data; Q.front->next=p->next; if(Q.rear==p)//判斷刪除隊(duì)頭元素后，隊(duì)列是否為空隊(duì) Q.rear=Q.front; free(p); returnOK;}intQueueEmpty(LinkQueueQ)//判斷隊(duì)列是否為空隊(duì){ if(Q.front==Q.rear) returnTURE; else returnFALSE;}intInitBiTree(BiTree&T)//構(gòu)造空二叉樹(shù){ T=NULL; returnOK;}intDestroyTree(BiTree&T)//銷(xiāo)毀二叉樹(shù){ if(!T) returnERROR; else DestroyTree(T->lchild); DestroyTree(T->rchild); free(T); T=NULL; returnOK;}voidCreateBiTree(BiTree&T)//用先序遍歷的方式構(gòu)建二叉樹(shù),以‘@’表示空結(jié)點(diǎn)。{ TElemTypech; scanf("%c",&ch); if(ch=='@') T=NULL; else { if(!(T=(BiTree)malloc(sizeof(BiTNode)))) exit(OVERFLOW);//分配存儲(chǔ)空間失敗 T->data=ch; CreateBiTree(T->lchild);//構(gòu)造左子樹(shù) CreateBiTree(T->rchild);//構(gòu)造右子樹(shù) }}intClearBiTree(BiTree&T)//清空二叉樹(shù)函數(shù){ if(!T) returnERROR; else { ClearBiTree(T->lchild); ClearBiTree(T->rchild); free(T); T=NULL; returnOK; }}intBiTreeEmpty(BiTreeT)//判斷二叉樹(shù)是否為空{(diào) if(!T) returnTURE; else returnFALSE;}intBiTreeDepth(BiTreeT)//計(jì)算二叉樹(shù)深度{ intlcd,rcd; if(!T) return0; lcd=BiTreeDepth(T->lchild); rcd=BiTreeDepth(T->rchild); return((lcd>rcd?lcd:rcd)+1);}TElemTypeRoot(BiTreeT)//判斷二叉樹(shù)是否空，若非空返回其根{ if(BiTreeEmpty(T)) returnNULL; else return(T->data);}TElemTypeValue(BiTreeT,BiTreee)//返回e結(jié)點(diǎn)的值{ returne->data;}intAssign(BiTreeT,BiTree&e,TElemTypevalue)//將value的值給結(jié)點(diǎn)e{ e->data=value; returnOK;}TElemTypeParent(BiTreeT,TElemTypee){//返回雙親 LinkQueueq; QElemTypea; if(T) { InitQueue(q); EnQueue(q,T);//樹(shù)根入隊(duì)列 while(!QueueEmpty(q))//隊(duì)不空 { DeQueue(q,a);//出隊(duì)，隊(duì)列元素賦給a if(a->lchild&&a->lchild->data==e||a->rchild&&a->rchild->data==e)//找到e returna->data;//返回雙親的值 else { if(a->lchild) EnQueue(q,a->lchild);//入隊(duì)列左孩子 if(a->rchild) EnQueue(q,a->rchild);//入隊(duì)列右孩子 } } } returnNULL;}BiTreePoint(BiTreeT,TElemTypes)//返回二叉樹(shù)T中指向元素值為S的結(jié)點(diǎn)指針{ LinkQueueq; QElemTypea; if(T) { InitQueue(q); EnQueue(q,T); while(!QueueEmpty(q)) { DeQueue(q,a); if(a->data==s) { returna; } if(a->lchild) { EnQueue(q,a->lchild); } if(a->rchild) { EnQueue(q,a->rchild); } } } returnNULL;}TElemTypeLeftChild(BiTreeT,TElemTypee){//返回e的左孩子BiTreea;if(T){ a=Point(T,e);//a是指向結(jié)點(diǎn)e的指針if(a&&a->lchild) returna->lchild->data; } returnNULL;}TElemTypeRightChild(BiTreeT,TElemTypee)//返回e的右孩子{ BiTreea; if(T) { if((a=Point(T,e))&&a->rchild) returna->rchild->data; }returnNULL;}TElemTypeLeftSibling(BiTreeT,TElemTypee){//返回左兄弟 TElemTypea; BiTreep; if(T) { a=Parent(T,e);//a為e的雙親 if(a!=NULL) { p=Point(T,a);//p指向結(jié)點(diǎn)a的指針 if(p->lchild&&p->rchild&&p->rchild->data==e)//p存在左右孩子而且右孩子是e returnp->lchild->data; } } returnNULL;}TElemTypeRightSibling(BiTreeT,TElemTypee){//返回右兄弟 TElemTypea; BiTreep; if(T) { a=Parent(T,e);//a為e的雙親 if(a!=NULL) { p=Point(T,a);//p指向結(jié)點(diǎn)a的指針 if(p->lchild&&p->rchild&&p->lchild->data==e)//p存在左右孩子而且左孩子是e returnp->rchild->data; } } returnNULL;}intInsertChild(BiTreeT,BiTreep,intLR,BiTreec)//根據(jù)LR為0或者1，插入C為T(mén)中P所指結(jié)點(diǎn)的左或者右子樹(shù)， //P所指的結(jié)點(diǎn)原有左或右子樹(shù)則成為C的右子樹(shù){ if(p) { if(LR==0)//把二叉樹(shù)C插入p所指結(jié)點(diǎn)的左子樹(shù) { c->rchild=p->lchild; p->lchild=c; } else { c->rchild=p->rchild; p->rchild=c; } returnOK; } returnERROR;}intDeleteChild(BiTreeT,BiTreep,intLR){ if(p) { if(LR==0) { ClearBiTree(p->lchild); } else { ClearBiTree(p->rchild); } returnOK; } returnERROR;}voidvisit(TElemTypee)//二叉樹(shù)結(jié)點(diǎn)訪(fǎng)問(wèn)函數(shù){ printf("%c",e);}intPreOrderTraverse(BiTreeT,void(*visit)(TElemType))//先序遍歷二叉樹(shù){ if(T) { visit(T->data); PreOrderTraverse(T->lchild,visit); PreOrderTraverse(T->rchild,visit); returnOK; } returnERROR;}intInOrderTraverse(BiTreeT,void(*visit)(TElemType)){//中序遍歷二叉樹(shù) if(T) { InOrderTraverse(T->lchild,visit); visit(T->data); InOrderTraverse(T->rchild,visit); returnOK; } returnERROR;}intPostOrderTraverse(BiTreeT,void(*visit)(TElemType)){//后序遍歷二叉樹(shù) if(T) { PostOrderTraverse(T->lchild,visit); PostOrderTraverse(T->rchild,visit); visit(T->data); returnOK;} returnERROR;}intLevelOrderTraverse(BiTreeT,void(*visit)(TElemType)){//層序遍歷二叉樹(shù) LinkQueueq; QElemTypea; if(T) { InitQueue(q);//初始化隊(duì)列 EnQueue(q,T);//根指針入隊(duì) while(!QueueEmpty(q)) { DeQueue(q,a);//出隊(duì)元素，賦給a visit(a->data);//訪(fǎng)問(wèn)a所指結(jié)點(diǎn) if(a->lchild!=NULL) EnQueue(q,a->lchild); if(a->rchild!=NULL) EnQueue(q,a->rchild); } returnOK; } returnERROR;}主函數(shù)：intmain(){ inti,j,LR; TElemTypevalue,a,temp; BiTreep,C; printf("歡迎使用本二叉樹(shù)程序，請(qǐng)按回車(chē)鍵繼續(xù)...\n"); getchar(); printf("正在構(gòu)造空二叉樹(shù)，請(qǐng)稍候..."); printf("\n"); BiTreeT; InitBiTree(T); if(BiTreeEmpty(T)) printf("構(gòu)造空二叉樹(shù)成功！\n"); else printf("構(gòu)造空二叉樹(shù)失敗！\n"); printf("請(qǐng)按先序遍歷順序輸入二叉樹(shù)各結(jié)點(diǎn)的值！空結(jié)點(diǎn)用@表示！\n"); CreateBiTree(T); printf("\n"); getchar(); printf("請(qǐng)選擇接下來(lái)的操作:輸入“1”為查看二叉樹(shù)深度，輸入“2”為查看二叉樹(shù)根節(jié)點(diǎn)...\n"); scanf("%d",&i); if(i==1) printf("此二叉樹(shù)的深度為：%d\n\n",BiTreeDepth(T)); if(i==2) printf("此二叉樹(shù)的根節(jié)點(diǎn)為：%c\n\n",Root(T)); printf("請(qǐng)選擇遍歷該二叉樹(shù)的順序：輸入“1”為先序遍歷，輸入“2”為中序遍歷，輸入“3”為后序遍歷，輸入“4”為層序遍歷...\n"); scanf("%d",&i); getchar(); printf("\n"); if(i==1) { j=PreOrderTraverse(T,visit); printf("\n"); if(j==0) printf("該二叉樹(shù)為空樹(shù)，請(qǐng)重新運(yùn)行程序！\n"); } if(i==2) { j=InOrderTraverse(T,visit); printf("\n"); if(j==0) printf("該二叉樹(shù)為空樹(shù)，請(qǐng)重新運(yùn)行程序！\n"); } if(i==3) { j=PostOrderTraverse(T,visit); printf("\n"); if(j==0) printf("該二叉樹(shù)為空樹(shù)，請(qǐng)重新運(yùn)行程序！\n"); } if(i==4) { j=LevelOrderTraverse(T,visit); printf("\n"); if(j==0) printf("該二叉樹(shù)為空樹(shù)，請(qǐng)重新運(yùn)行程序！\n"); } printf("\n請(qǐng)輸入需要替換的結(jié)點(diǎn)：\n"); scanf("%c",&a); getchar(); p=Point(T,a); printf("請(qǐng)輸入需要代入的結(jié)點(diǎn)值：\n"); scanf("%c",&value); getchar(); Assign(T,p,value); printf("賦值之后該結(jié)點(diǎn)的值為：%c\n\n",p->data); printf("請(qǐng)輸入“1”求該結(jié)點(diǎn)的雙親結(jié)點(diǎn)，輸入“2”求該結(jié)點(diǎn)的左孩子，輸入“3”求該結(jié)點(diǎn)的右孩子，輸入“4”求該結(jié)點(diǎn)的左兄弟，輸入“5”求該結(jié)點(diǎn)的右兄弟..\n\n"); scanf("%d",&i); getchar(); switch(i) { case1: { if(Parent(T,value)==NULL) printf("該結(jié)點(diǎn)沒(méi)有雙親結(jié)點(diǎn)。\n"); else printf("該結(jié)點(diǎn)的雙親結(jié)點(diǎn)為：%c\n\n",Parent(T,value));break; } case2: { if(LeftChild(T,value)==NULL) printf("該結(jié)點(diǎn)沒(méi)有左孩子結(jié)點(diǎn)。\n"); else printf("該結(jié)點(diǎn)的左孩子結(jié)點(diǎn)為：%c\n\n",LeftChild(T,value));break; } case3: { if(RightChild(T,value)==NULL) printf("該結(jié)點(diǎn)沒(méi)有右孩子結(jié)點(diǎn)。\n"); else printf("該結(jié)點(diǎn)的右孩子結(jié)點(diǎn)為：%c\n\n",RightChild(T,value));break; } case4: { if(LeftSibling(T,value)==NULL) printf("該結(jié)點(diǎn)沒(méi)有左兄弟。\n"); else printf("該結(jié)點(diǎn)的左兄弟為：%c\n\n",LeftSibling(T,value)); break; } case5: { if(RightSibling(T,value)==NULL) printf("該結(jié)點(diǎn)沒(méi)有右兄弟。\n"); else printf("該結(jié)點(diǎn)的右兄弟為：%c\n\n",RightSibling(T,value)); break; } } printf("\n現(xiàn)在進(jìn)行結(jié)點(diǎn)插入子樹(shù)，請(qǐng)按照先序遍歷的順序輸入二叉樹(shù)C，注意該二叉樹(shù)沒(méi)有右子樹(shù)！\n"); InitBiTree(C); CreateBiTree(C); getchar(); printf("\n請(qǐng)輸入您需要插入子樹(shù)的結(jié)點(diǎn)：\n"); scanf("%c",&a); getchar(); p=Point(T,a); printf("\n輸入0示插入C為%c結(jié)點(diǎn)的左子樹(shù)而該結(jié)點(diǎn)原來(lái)的左子樹(shù)變?yōu)閏的右子樹(shù)...",a); printf("\n輸入1示插入C為%c結(jié)點(diǎn)的右子樹(shù)而該結(jié)點(diǎn)原來(lái)的左子樹(shù)變?yōu)閏的右子樹(shù),請(qǐng)選擇...\n",a); scanf("%d",&LR); getchar(); j=InsertChild(T,p,LR,C); if(j==0) { printf("插入失?。n"); } else { printf("插入成功！該新二叉樹(shù)的先序遍歷為："); PreOrderTraverse(T,visit); } printf("\n\n進(jìn)行刪除操作，請(qǐng)輸入需要?jiǎng)h除左子樹(shù)或者右子樹(shù)的結(jié)點(diǎn)："); scanf("%c",&a); getchar(); p=Point(T,a); printf("\n輸入0表示刪除%c結(jié)點(diǎn)的左子樹(shù)，1表示刪除%c結(jié)點(diǎn)的右子樹(shù)，請(qǐng)選擇...\n",a); scanf("%d",&LR); getchar(); j=DeleteChild(T,p,LR); if(j==0) { printf("刪除失??！\n"); } else { printf("刪除成功！該新二叉樹(shù)的先序遍歷為："); PreOrderTraverse(T,visit); } DestroyTree(T); if(!T) printf("\n樹(shù)已被成功銷(xiāo)毀！程序執(zhí)行完畢，請(qǐng)按回車(chē)鍵\n"); else printf("\n樹(shù)銷(xiāo)毀不成功！程序執(zhí)行完畢，請(qǐng)按回車(chē)鍵\n"); getchar(); for(i=1;i<=4;++i) printf("\n"); printf("***************************************************************************\n"); printf("***************************************************************************\n"); printf("***************************************************************************\n"); printf("***************************************************************************\n"); printf("***************************************************************************\n"); printf("***************************************************************************\n"); printf("***************************************************************************\n"); printf("***************************************************************************\n"); printf("******************************感謝使用*****************************\n"); printf("*************************************************************\n"); printf("******************************計(jì)科四班*****************************\n"); printf("***********************************************************\n"); printf("******************************制作人：羅志權(quán)*****************************\n"); printf("***********************************************************\n"); printf("******************************