廣東工業(yè)大學(xué)數(shù)據(jù)結(jié)構(gòu)二叉樹課程設(shè)計(jì)報(bào)告

1、-. z數(shù)據(jù)構(gòu)造實(shí)驗(yàn)報(bào)告題目：二叉樹抽象數(shù)據(jù)類型學(xué) 院計(jì)算機(jī)學(xué)院專 業(yè)計(jì)算機(jī)科學(xué)與技術(shù) 年級班別學(xué) 號學(xué)生指導(dǎo)教師成 績 _2021年6月一實(shí)驗(yàn)概要實(shí)驗(yàn)工程名稱: 二叉樹抽象數(shù)據(jù)類型的實(shí)現(xiàn)實(shí)驗(yàn)工程性質(zhì): 設(shè)計(jì)性實(shí)驗(yàn)所屬課程名稱: 數(shù)據(jù)構(gòu)造實(shí)驗(yàn)方案學(xué)時: 6二.實(shí)驗(yàn)?zāi)康牧私舛鏄涞亩x以及各項(xiàng)根本操作。實(shí)現(xiàn)二叉樹存儲、遍歷及其他根本功能三. 實(shí)驗(yàn)儀器設(shè)備和材料 硬件：PC機(jī) 軟件：Visual C+ 6.0四實(shí)驗(yàn)的容1.二叉樹類型定義以及各根本操作的簡要描述；ADT BinaryTree 數(shù)據(jù)對象D:D是具有一樣特性的數(shù)據(jù)元素的集合.數(shù)據(jù)關(guān)系R:假設(shè)D=，則R=,稱BinaryTree為空二叉樹

2、；假設(shè)D，則R=H，H是如下二元關(guān)系：在D中存在惟一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H下無前驅(qū)；假設(shè)D-root，則存在D-root=D1,Dr，且D1Dr=；假設(shè)D1，則D1中存在惟一的元素*1，H，且存在Dr上的關(guān)系HrH；H=，H1,Hr；D1，H1是一棵符合本定義的二叉樹，稱為根的左子樹，是一棵符合本定義的二叉樹，稱為根的右子樹。根本操作P:InitBiTree(&T);操作結(jié)果：構(gòu)造空二叉樹T。DestroyBiTree(&T);初始條件：二叉樹T存在。操作結(jié)果：銷毀二叉樹T。CreateBiTree(&T,definition);初始條件：definition給出二叉樹T的定義

3、。操作結(jié)果：按definition構(gòu)造二叉樹T。ClearBiTree(&T);初始條件：二叉樹T存在。操作結(jié)果：將二叉樹T清為空樹。BiTreeEmpty(T);初始條件：二叉樹T存在。操作結(jié)果：假設(shè)T為空二叉樹，則返回TURE,否則FALSE。BiTreeDepth(T);初始條件：二叉樹T存在。操作結(jié)果：返回T的深度。Root(T);初始條件：二叉樹T存在。操作結(jié)果：返回T的根。Value(T,e);初始條件：二叉樹T存在，e是T中的*個結(jié)點(diǎn)。操作結(jié)果：返回e的值。Assign(T,&e,value); 初始條件：二叉樹T存在，e是T中的*個結(jié)點(diǎn)。 操作結(jié)果：結(jié)點(diǎn)e賦值為value。Pa

4、rent(T,e); 初始條件：二叉樹T存在，e是T中的*個結(jié)點(diǎn)。操作結(jié)果：假設(shè)e是T的非跟結(jié)點(diǎn)，則返回它的雙親，否則返回“空。LeftChild(T,e);初始條件：二叉樹T存在，e是T中的*個結(jié)點(diǎn)。操作結(jié)果：返回e的左孩子。假設(shè)e無左孩子，則返回“空。RightChild(T,e);初始條件：二叉樹T存在，e是T中的*個結(jié)點(diǎn)。操作結(jié)果：返回e的右孩子。假設(shè)e無右孩子，則返回“空。LeftSibling(T,e);初始條件：二叉樹T存在，e是T中的*個結(jié)點(diǎn)。操作結(jié)果：返回e的左兄弟。假設(shè)e無左孩子或無左兄弟，則返回“空。RightSibling(T,e); 初始條件：二叉樹T存在，e是T中的

5、*個結(jié)點(diǎn)。操作結(jié)果：返回e的右兄弟。假設(shè)e無右孩子或無右兄弟，則返回“空。ADT BinaryTree2.存儲構(gòu)造：采用無頭結(jié)點(diǎn)的鏈?zhǔn)酱鎯?gòu)造實(shí)現(xiàn)3.源代碼：頭文件及存儲構(gòu)造:*include*include*define TURE 1*define FALSE 0*define OK 1*define ERROR 0*define OVERFLOW 0*define MA*QSIZE 100 /最大隊(duì)列長度typedef char TElemType; typedef struct BiTNode /二叉樹構(gòu)造體TElemType data;struct BiTNode *lchild,*r

6、child;BiTNode,*BiTree;typedef BiTree QElemType;typedef struct QNode QElemType data; struct QNode *ne*t; QNode, *QueuePtr; /結(jié)點(diǎn)構(gòu)造體typedef struct QueuePtr front; QueuePtr rear; LinkQueue; /鏈隊(duì)列構(gòu)造體 算法設(shè)計(jì)：int InitQueue(LinkQueue &Q) /構(gòu)造空隊(duì)列 Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode);if(!Q.front) /存儲分

7、配失敗 e*it(OVERFLOW); Q.front-ne*t = NULL;return OK; int EnQueue(LinkQueue &Q, QElemType e) /新元素入隊(duì)尾 QueuePtr p; p = (QueuePtr)malloc(sizeof(QNode); if(!p) /存儲分配失敗 e*it (OVERFLOW); p-data = e; p-ne*t = NULL; Q.rear-ne*t = p; Q.rear = p; return OK; int DeQueue(LinkQueue &Q, QElemType &e) /刪除隊(duì)頭元素 QueuePt

8、r p; if(Q.front = Q.rear) /隊(duì)列為空隊(duì) return ERROR; p = Q.front-ne*t; e = p-data; Q.front-ne*t = p-ne*t; if(Q.rear = p) /判斷刪除隊(duì)頭元素后，隊(duì)列是否為空隊(duì) Q.rear = Q.front; free(p); return OK; int QueueEmpty(LinkQueue Q) /判斷隊(duì)列是否為空隊(duì) if (Q.front = Q.rear)return TURE;elsereturn FALSE;int InitBiTree(BiTree &T) / 構(gòu)造空二叉樹 T =

9、NULL;return OK;int DestroyTree(BiTree &T) /銷毀二叉樹if(!T)return ERROR;elseDestroyTree(T-lchild);DestroyTree(T-rchild);free(T);T=NULL;return OK;void CreateBiTree(BiTree &T) /用先序遍歷的方式構(gòu)建二叉樹,以表示空結(jié)點(diǎn)。 TElemType ch;scanf(%c,&ch);if(ch=)T=NULL;elseif(!(T=(BiTree)malloc(sizeof(BiTNode)e*it(OVERFLOW); /分配存儲空間失敗T

10、-data=ch;CreateBiTree(T-lchild); /構(gòu)造左子樹CreateBiTree(T-rchild); /構(gòu)造右子樹int ClearBiTree(BiTree &T) /清空二叉樹函數(shù)if(!T)return ERROR;elseClearBiTree(T-lchild);ClearBiTree(T-rchild);free(T);T=NULL;return OK;int BiTreeEmpty(BiTree T) /判斷二叉樹是否為空if(!T)return TURE;elsereturn FALSE;int BiTreeDepth(BiTree T) /計(jì)算二叉樹深

11、度int lcd,rcd;if(!T)return 0;lcd=BiTreeDepth(T-lchild);rcd=BiTreeDepth(T-rchild);return (lcdrcd?lcd:rcd)+1);TElemType Root(BiTree T) /判斷二叉樹是否空，假設(shè)非空返回其根if(BiTreeEmpty(T)return NULL;elsereturn (T-data);TElemType Value(BiTree T,BiTree e) /返回e結(jié)點(diǎn)的值return e-data;int Assign(BiTree T,BiTree &e,TElemType valu

12、e) / 將value的值給結(jié)點(diǎn)ee-data=value;return OK;TElemType Parent(BiTree T,TElemType e)/返回雙親LinkQueue q;QElemType a;if(T)InitQueue(q);EnQueue(q,T);/樹根入隊(duì)列while(!QueueEmpty(q)/隊(duì)不空DeQueue (q, a);/出隊(duì)，隊(duì)列元素賦給aif(a-lchild&a-lchild-data=e|a-rchild&a-rchild-data=e) /找到ereturn a-data; /返回雙親的值elseif(a-lchild)EnQueue(q,

13、a-lchild);/入隊(duì)列左孩子if(a-rchild)EnQueue(q,a-rchild);/入隊(duì)列右孩子return NULL;BiTree Point(BiTree T,TElemType s)/返回二叉樹T中指向元素值為S的結(jié)點(diǎn)指針LinkQueue q;QElemType a;if(T)InitQueue(q);EnQueue(q,T);while(!QueueEmpty(q)DeQueue(q,a);if(a-data=s)return a;if(a-lchild)EnQueue(q,a-lchild);if(a-rchild)EnQueue(q,a-rchild);retur

14、n NULL;TElemType LeftChild(BiTree T,TElemType e)/返回e的左孩子 BiTree a; if(T) a=Point(T,e);/a是指向結(jié)點(diǎn)e的指針 if(a&a-lchild)return a-lchild-data;return NULL;TElemType RightChild(BiTree T,TElemType e) /返回e的右孩子BiTree a;if(T)if(a=Point(T,e)&a-rchild)return a-rchild-data; return NULL;TElemType LeftSibling(BiTree T,

15、TElemType e) /返回左兄弟TElemType a;BiTree p;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存在左右孩子而且右孩子是ereturn p-lchild-data;return NULL;TElemType RightSibling(BiTree T,TElemType e) /返回右兄弟TElemType a;BiTree p;if(T)a=Parent(T,e);/a為e的雙親if(a!=NULL)p=Poin

16、t(T,a);/p指向結(jié)點(diǎn)a的指針if(p-lchild&p-rchild&p-lchild-data=e)/p存在左右孩子而且左孩子是ereturn p-rchild-data;return NULL;int InsertChild(BiTree T,BiTree p,int LR,BiTree c) /根據(jù)LR為0或者1，插入C為T中P所指結(jié)點(diǎn)的左或者右子樹，/P所指的結(jié)點(diǎn)原有左或右子樹則成為C的右子樹if(p)if(LR=0) /把二叉樹C插入p所指結(jié)點(diǎn)的左子樹c-rchild=p-lchild;p-lchild=c;elsec-rchild=p-rchild;p-rchild=c;re

17、turn OK;return ERROR;int DeleteChild(BiTree T,BiTree p,int LR)if(p)if(LR=0)ClearBiTree(p-lchild);elseClearBiTree(p-rchild);return OK;return ERROR;void visit(TElemType e) /二叉樹結(jié)點(diǎn)函數(shù)printf(%c,e);int PreOrderTraverse(BiTree T,void(*visit)(TElemType) /先序遍歷二叉樹if(T)visit(T-data);PreOrderTraverse(T-lchild,vi

18、sit);PreOrderTraverse(T-rchild,visit);return OK;return ERROR;int InOrderTraverse(BiTree T,void(*visit)(TElemType) /中序遍歷二叉樹if(T)InOrderTraverse(T-lchild,visit);visit(T-data);InOrderTraverse(T-rchild,visit);return OK;return ERROR;int PostOrderTraverse(BiTree T,void(*visit)(TElemType) /后序遍歷二叉樹if(T) Pos

19、tOrderTraverse(T-lchild,visit);PostOrderTraverse(T-rchild,visit);visit(T-data);return OK; return ERROR;int LevelOrderTraverse(BiTree T,void(*visit)(TElemType)/層序遍歷二叉樹LinkQueue q;QElemType a;if(T)InitQueue(q);/初始化隊(duì)列EnQueue(q,T);/根指針入隊(duì)while(!QueueEmpty(q)DeQueue(q,a);/出隊(duì)元素，賦給avisit(a-data);/a所指結(jié)點(diǎn)if(a-

20、lchild!=NULL)EnQueue(q,a-lchild);if(a-rchild!=NULL)EnQueue(q,a-rchild);return OK;return ERROR;主函數(shù)：int main()int i,j,LR;TElemType value,a,temp;BiTree p,C;printf(歡送使用本二叉樹程序，請按回車鍵繼續(xù).n);getchar();printf(正在構(gòu)造空二叉樹，請稍候.);printf(n);BiTree T;InitBiTree(T);if(BiTreeEmpty(T)printf(構(gòu)造空二叉樹成功！n);elseprintf(構(gòu)造空二叉樹

21、失??！n);printf(請按先序遍歷順序輸入二叉樹各結(jié)點(diǎn)的值！空結(jié)點(diǎn)用表示！n);CreateBiTree(T);printf(n);getchar();printf(請選擇接下來的操作:輸入“1為查看二叉樹深度，輸入“2為查看二叉樹根節(jié)點(diǎn).n);scanf(%d,&i);if(i=1)printf(此二叉樹的深度為：%dnn,BiTreeDepth(T);if(i=2)printf(此二叉樹的根節(jié)點(diǎn)為：%cnn,Root(T);printf(請選擇遍歷該二叉樹的順序：輸入“1為先序遍歷，輸入“2為中序遍歷，輸入“3為后序遍歷，輸入“4為層序遍歷.n);scanf(%d,&i);getcha

22、r();printf(n);if(i=1)j=PreOrderTraverse(T,visit);printf(n);if(j=0)printf(該二叉樹為空樹，請重新運(yùn)行程序！n);if(i=2)j=InOrderTraverse(T,visit);printf(n);if(j=0)printf(該二叉樹為空樹，請重新運(yùn)行程序！n);if(i=3)j=PostOrderTraverse(T,visit);printf(n);if(j=0)printf(該二叉樹為空樹，請重新運(yùn)行程序！n);if(i=4)j=LevelOrderTraverse(T,visit);printf(n);if(j=

23、0)printf(該二叉樹為空樹，請重新運(yùn)行程序！n);printf(n請輸入需要替換的結(jié)點(diǎn)：n);scanf(%c,&a);getchar();p=Point(T,a);printf(請輸入需要代入的結(jié)點(diǎn)值：n);scanf(%c,&value);getchar();Assign(T,p,value);printf(賦值之后該結(jié)點(diǎn)的值為：%cnn,p-data);printf(請輸入“1求該結(jié)點(diǎn)的雙親結(jié)點(diǎn)，輸入“2求該結(jié)點(diǎn)的左孩子，輸入“3求該結(jié)點(diǎn)的右孩子，輸入“4求該結(jié)點(diǎn)的左兄弟，輸入“5求該結(jié)點(diǎn)的右兄弟.nn);scanf(%d,&i);getchar();switch(i)case 1

24、:if(Parent(T,value)=NULL)printf(該結(jié)點(diǎn)沒有雙親結(jié)點(diǎn)。n);elseprintf(該結(jié)點(diǎn)的雙親結(jié)點(diǎn)為：%cnn,Parent(T,value);break;case 2:if(LeftChild(T,value)=NULL)printf(該結(jié)點(diǎn)沒有左孩子結(jié)點(diǎn)。n);elseprintf(該結(jié)點(diǎn)的左孩子結(jié)點(diǎn)為：%cnn,LeftChild(T,value);break;case 3:if(RightChild(T,value)=NULL)printf(該結(jié)點(diǎn)沒有右孩子結(jié)點(diǎn)。n);elseprintf(該結(jié)點(diǎn)的右孩子結(jié)點(diǎn)為：%cnn,RightChild(T,valu

25、e);break;case 4:if(LeftSibling(T,value)=NULL)printf(該結(jié)點(diǎn)沒有左兄弟。n);elseprintf(該結(jié)點(diǎn)的左兄弟為：%cnn,LeftSibling(T,value);break;case 5:if(RightSibling(T,value)=NULL)printf(該結(jié)點(diǎn)沒有右兄弟。n);elseprintf(該結(jié)點(diǎn)的右兄弟為：%cnn,RightSibling(T,value);break;printf(n現(xiàn)在進(jìn)展結(jié)點(diǎn)插入子樹，請按照先序遍歷的順序輸入二叉樹C，注意該二叉樹沒有右子樹！n);InitBiTree(C);CreateBiTr

26、ee(C);getchar();printf(n請輸入您需要插入子樹的結(jié)點(diǎn)：n);scanf(%c,&a);getchar();p=Point(T,a);printf(n輸入0示插入C為%c結(jié)點(diǎn)的左子樹而該結(jié)點(diǎn)原來的左子樹變?yōu)閏的右子樹.,a);printf(n輸入1示插入C為%c結(jié)點(diǎn)的右子樹而該結(jié)點(diǎn)原來的左子樹變?yōu)閏的右子樹,請選擇.n,a);scanf(%d, &LR);getchar();j= InsertChild(T, p, LR, C);if(j=0)printf(插入失??！n);elseprintf(插入成功！該新二叉樹的先序遍歷為：);PreOrderTraverse(T, visit);printf(nn進(jìn)展刪除操作，請輸入需要刪除左子樹或者右子樹的結(jié)點(diǎn)：);scanf(%c,&a);getchar();p=Point(T,a);printf(n輸入 0 表示刪除%c結(jié)點(diǎn)的左子樹， 1 表示刪除%c結(jié)點(diǎn)的右子樹，請選擇.n,a);scanf(%d, &LR);getchar();j = DeleteChild(T, p, LR);if(j=0)printf(刪除失敗！n);elseprintf(刪除成功！該