广东工业大学数据结构二叉树课程设计

1、数据结构实验报告题目：二叉树抽象数据类型学院计算机学院专业计算机科学与技术年级班别学号学生姓名指导教师成绩2013年6月 一.实验概要实验项目名称：二义树抽象数据类型的实现实验项目性质：设计性实验所属课程名称：数据结构实验计划学时：62 .实验目的1 . 了解二义树的定义以及各项基本操作。2 .实现二义树存储、遍历及其他基本功能3 .实验仪器设备和材料硬件：PC机软件：Visual C+ 6.04 .实验的内容1 .二义树类型定义以及各基本操作的简要描述； ADT BinaryTree 数据对象D ： D是具有相同特性的数据元素的集合.数据关系R：若D=0,则R=,称BinaryTree为空二

2、义树；若DR,则R=H, H是如下二元关系：(1) 在D中存在惟一的称为根的数据元素root,它在关系H下无前 驱；(2) 若 D- root 壬0,则存在 D-root = D1, Dr,且 DlDDr=0；(3) 若D1于0,则D1中存在惟一的元素xl, <root, xl>GH,且存在 Dr 上的关系 HrH； H= <root, xl>, <root, xr>, Hl, Hr)；(4) (DI, Hl)是一棵符合本定义的二义树，称为根的左子树， 是一棵符合本定义的二义树，称为根的右子树。基本操作P：InitBiTree(&T);操作结果：构造

3、空二义树T。DestroyBiTree(&T);初始条件：二义树T存在。操作结果：销毁二义树T。CreateBiTree(&T,definition);初始条件：definition给出二叉树T的定义。操作结果：按def inition构造二义树T。 ClearBiTree(&T);初始条件：二义树T存在。操作结果：将二义树T清为空树。BiTreeEmpty(T);初始条件：二义树T存在。操作结果：若T为空二义树，则返回TURE,否则FALSEo BiTreeDepth(T);初始条件：二义树T存在。操作结果：返回T的深度。Root (T);初始条件：二义树T存在。操作

4、结果：返回T的根。Value(T,e);初始条件：二义树T存在，e是T中的某个结点。操作结果：返回e的值。Assign(T,value);初始条件：二叉树T存在，e是T中的某个结点。操作结果：结点e赋值为value。Parent(T,e);初始条件：二叉树T存在，e是T中的某个结点。操作结果：若e是T的非跟结点，则返回它的双亲，否则返回'、空。 Leftchild(T,e);初始条件：二义树T存在，e是T中的某个结点。操作结果：返回e的左孩子。若e无左孩子，则返回'、空。RightChild(T,e);初始条件：二义树T存在，e是T中的某个结点。操作结果：返回e的右孩子。若e无

5、右孩子，则返回'、空。Leftsibling (T,e);初始条件：二叉树T存在，e是T中的某个结点。操作结果：返回e的左兄弟。若e无左孩子或无左兄弟，则返回''空。 Rightsibling (T,e);初始条件：二义树T存在，e是T中的某个结点。操作结果：返回e的右兄弟。若e无右孩子或无右兄弟，则返回''空。 ADT BinaryTree2 .存储结构：采用无头结点的链式存储结构实现3 .源代码：头文件及存储结构：#include<stdio.h>#include<stdlib.h>#define#define#define#

6、define#defineTURE 1FALSE 0OK 1ERROR 0OVERFLOW 0 #define MAXQSIZE 100 /最大队歹lj长度typedef char TElemType; typedef struct BiTNode /.义树结构体 ( TElemType data;struct BiTNode *lchildz *rchild;BiTNode,*BiTree;typedef BiTree QElemType;typedef struct QNode (QElemType data; struct QNode *next; QNode, *QueuePtr;结点

7、结构体typedef struct (QueuePtr front;QueuePtr rear;LinkQueue;/链队列结构体算法设计：int InitQueue (LinkQueue &Q) /构造空队列 (Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode);if (!Q. front) /存储分配失败exit(OVERFLOW);Q.front->next = NULL; return OK;)int EnQueue (LinkQueue &Q, QElemType e) /新元素入队尾( QueuePtr p; p

8、 = (QueuePtr)malloc(sizeof(QNode);if (!p) /存储分配失败 exit (OVERFLOW);p->data = e;p->next = NULL;Q.rear->next = p;Q.rear = p;return OK; )int DeQueue (LinkQueue &Q, QElemType &e) /删除队头元素 (QueuePtr p;if (Q. front = Q . rear) /队列为空队 return ERROR;p = Q.front->next;e = p->data;Q.front-

9、>next = p->next;if (Q. rear = p) /判断删除队头元素后，队列是否为空队Q.rear = Q.front;free (p);return OK; )int QueueEmpty (LinkQueue Q) /判断队列是否为空队 (if (Q.front = Q.rear) return TURE;else return FALSE; ) int InitBiTree (BiTree &T) / 构造空二义树T = NULL； return OK; )int DestroyTree (BiTree &T)/俏毁二叉树(if ( !T) r

10、eturn ERROR;elseDestroyTree(T->lchild);DestroyTree(T->rchild); free(T);T=NULL; return OK; )void CreateBiTree (BiTree &T)/用先序遍历的方式构建二叉树，以'r表示空结点。(TElemType ch;scanf (n%clf, &ch);if(ch=fl) T=NULL;else (if(!(T=(BiTree)malloc(sizeof(BiTNode)exit (OVERFLOW) ;/分配存储空间失败T->data=ch;Creat

11、eBiTree (T->lchild) ;/构造左子树CreateBiTree (T->rchild) ;/构造右子树) )int ClearBiTree (BiTree &T)/清空二又树函数(if ( !T) return ERROR;elseClearBiTree(T->lchild);ClearBiTree(T->rchild); free(T);T=NULL; return OK; ) )int BiTreeEmpty (BiTree T) /判断二叉树是否为空(if ( !T) return TURE;else return FALSE; )int

12、BiTreeDepth (BiTree T) /计算二义树深度 (int 工cd,red;if ( !T) return 0;lcd=BiTreeDepth(T->lchild);rcd=BiTreeDepth(T->rchild);return (lcd>rcd?lcd:red)+1); )TElemType Root (BiTree T) /判断二义树是否空，若非空返回其根 (if(BiTreeEmpty(T) return NULL;else return (T->data); )TElemType Value (BiTree T, BiTree e) /返回 e

13、 结点的值return e->data;int Assign(BiTree T,BiTree TElemType value) / 将 value的值给结点e(e->data=value;return OK;)TElemType Parent(BiTree T,TElemType e)/返回双亲LinkQueue q;QElemType a;if (T)(InitQueue(q);EnQueue (q, T); 树根入队列while ( ! QueueEmpty (q) ) /队不空(DeQueue (q, a);/出队，队列元素赋给aif(a->lchild&&am

14、p;a->lchild->data=e|a->rchild&&a->rchild->data=e) /找至 Uereturn a->data; /返回双亲的值else (if(a->lchild)EnQueue (q, a->lchild) ; /入队列左孩子if(a->rchild)EnQueue (q, a->rchild) ; /入队列右孩子)return NULL;BiTree Point (BiTree TzTElemType s)/返回二义树 T 中指向元素值为S的结点指针(LinkQueue q;QEle

15、mType 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);) return NULL;)TElemType Leftchild(BiTree Tz TElemType e)/返回e的左孩子BiTree a;if (T) (a=Point (Tz e) ; /a是指向

16、结点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 Tz TElemType e) /返回左兄弟TElemType a;

17、BiTree p;if (T) (a=Parent (T, e) ; /a 为 e 的双亲if (a!=NULL) (p=Point (T, a) ; /p指向结点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=P

18、arent (T, e) ; / /a 为 e 的双亲if (a!=NULL)p=Point (Tz a) ; /p指向结点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) /根据LR为。或者1,插入C为T中P所指结点的左或者右.子树,/P所指的结点原有左或右.子树

19、则成为C的右子树if(P)if (LR=O) /把二叉树C插入p所指结点的左子树c->rchild=p->lchild; p->lchild=c;)elsec->rchild=p->rchild; p->rchild=c;)return OK;)return ERROR;int DeleteChild(BiTree T,BiTree p,int LR) (if (P)(if (LR=O)( ClearBiTree(p->lchild);) else (ClearBiTree(p->rchild);) return OK;) return ERRO

20、R;)void visit (TElemType e) /二又树结点访问函数(printf (n%cn,e);) int PreOrderTraverse(BiTree T,void(*visit) (TElemType) / 先序遍历二叉树 (if (T) (visit(T->data);PreOrderTraverse(T->lchild,visit);PreOrderTraverse(T->rchild,visit); return OK; ) return ERROR; )int InOrderTraverse(BiTree T,void(*visit)(TElemT

21、ype) /中序遍历二义树if (T)InOrderTraverse(T->lchildz visit); visit(T->data);InOrderTraverse(T->rchildf visit); return OK; ) return ERROR; )int PostOrderTraverse(BiTree Tzvoid(*visit)(TElemType) /后序遍历二义树if (T) (PostOrderTraverse(T->lchild,visit); PostOrderTraverse(T->rchild,visit); visit(T-&g

22、t;data);return OK;) return ERROR; )int LevelOrderTraverse(BiTree Tzvoid(*visit)(TElemType) /层序遍历二义树LinkQueue q;QElemType a;if (T) (InitQueue (q); 初始化队列EnQueue (q, T); 根指针入队while(!QueueEmpty(q) (DeQueue (q, a) ;/出队元素，赋给avisit (a->data) ; /访问a所指结点if(a->lchild!=NULL) EnQueue(q,a->lchild);if(a-

23、>rchild!=NULL) EnQueue(q,a->rchild); ) return OK;return ERROR;主函数： int main() (intTElemType value,a,temp; BiTree p,C;printf (”欢迎使用本二义树程序，请按回车键继续.n");getchar ();printf ("正在构造空二义树，请稍候.”)；printf (Hn,f);BiTree T;InitBiTree(T);if(BiTreeEmpty(T)printf ("构造空二叉树成功! nn);elseprintf ("

24、;构造空二叉树失败! nn);printf ("请按先序遍历顺序输入二义树各结点的值！空结点用表示！nn)；CreateBiTree (T);printf (Hn,f); getchar ();printf (”请选择接下来的操作：输入''1为查看二叉树深度，输入''2为查看二又树根节点.n”);scanf("Sd",&i); if (i=l)printf ("止匕二义树的深度为：%dnnHzBiTreeDepth (T);if (i=2)printf (“此二叉树的根节点为:%cnnnzRoot(T);print

25、f ("请选择遍历该二叉树的顺序：输入''工为先序遍历，输入''2为 中序遍历，输入''3为后序遍历，输入''4为层序遍历.n”)；scanf , &i);getchar ();printf (unlf);if (i=l)(j =PreOrderTraverse(T,visit);printf (lfnn);if (j=0) printf (“该二义树为空树，请重新运行程序！ n“)；)if (i=2)(j=InOrderTraverse(Tf visit);printf(HnH);if(j=0)printf (

26、"该二又树为空树，请重新运行程序！ n”)；)if(i=3)(j=PostOrderTraverse(T,visit);printf("nu);if (j=0)printf ("该二叉树为空树,请重新运行程序！ n”);)if(i=4)(j =LevelOrderTraverse(T,visit);printf(HnH);if (j=0) printf （"该二义树为空树，请重新运行程序！ n”）；printf (nn请输入需要替换的结点：n'f);scanf (n%clf, &a);getchar ();p=Point(T,a);pri

27、ntf (”请输入需要代入的结点值:nn);scanf (, &value);getchar ();Assign(Tz p,value);printf ("赋值之后该结点的值为:%cnnn z p->data);prints ("请输入、'工求该结点的双亲结点，输入''2求该结点的左孩子，输入'、3求该结点的右孩子，输入'、4求该结点的左兄弟，输入''5求该结点的右兄弟.nn");scanf , &i);getchar ();switch(i)( case 1:(if(Parent(T,

28、value)=NULL)printf ("该结点没有双亲结点。n");elseprintf (n 该 结 点 的 双 亲 结 点为：%cnnn,Parent(T,value);break;) case 2:(if(Leftchild(T,value)=NULL)printf ("该结点没有左孩子结点。nH);elseprintf (n 该结点的左孩子结点为：%cnnnz Leftchild(Tz value);break;) case 3:(if(Rightchild(Tz value)=NULL)printf ("该结点没有右孩子结点。nH);else

29、printf (n 该结点的右孩子结点 为：%cnnf, Rightchild (Tf value) ) ;break;) case 4:(if(Leftsibling(T,value)=NULL) printf ("该结点没有左兄弟。n");elseprintf (n 该 结 点 的 左 兄 弟为：%cnnH,LeftSibling(Tzvalue);break;) case 5:(if(Rightsibling(T,value)=NULL) printf ("该结点没有右兄弟。nn);elseprintf (" 该 结 点 的 右 兄 弟为：%cnn

30、H,RightSibling(T,value);break;)printf (”n现在进行结点插入子树,请按照先序遍历的顺序输入二义树C,注意该二义树没有右子树！ n”)；InitBiTree (C);CreateBiTree (C);getchar ();printf ("n请输入您需要插入了树的结点：n");scanf (n%clf, &a);getchar ();p=Point(T,a);printf ("n输入0示插入C为轨结点的左子树而该结点原来的左子树变为c的右子树. ”，a);printf (-n输入1示插入C为宾结点的石子树而该结点原来的左

31、子树变为c的右子树，请选择a);scanf&LR);getchar ();j= InsertChild(T, p, LR, C); if(j=0) (printf ("插入失败! nn);) else (printf (”插入成功!该新二叉树的先序遍历为：;PreOrderTraverse(T, visit); )printf ("nn进行删除操作，请输入需要删除左子树或者右子树的结点: ”)；scanf('飞c”, &a);getchar (); p=Point(T,a);printf(”n输入0表示删除电c结点的左子树，1表示删除专c结点的右子树

32、,请选择. . . a);scanf(, &LR); getchar ();j = DeleteChild(T, p, LR); if(j=0) (printf ("删除失败! nn);) else (prints (”删除成功！该新二义树的先序遍历为：”)；PreOrderTraverse(T, visit); ) DestroyTree(T); if ( !T)printf （"n树已被成功销毁！程序执行完毕，请按回车键n”）；elseprintf （"n树销毁不成功！程序执行完毕，请按回车键M）；getchar ();for (i=l;i<=4;+i)printf (nprintf (nprintf (n*nnprintf (n*nHprintf (n*nnprintf (nprintf (n*nnprintf (n*nn)printf (n”）printf (n”）printf (n”）printf (n”）printf(” 制J 彳乍 人 n")printf