(完整word版)广东工业大学数据结构二叉树课程设计

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

2、 ， H 是如下二元关系：(1)在 D 中存在惟一的称为根的数据元素root ,它在关系 H 下无前驱；(2)若 D-root M ?，贝存在 D-root=D1,Dr,且 Din Dr=?;(3)若DIM?，贝U D1中存在惟一的元素x1 , <root,x1> H,且存，xr> ，H1,Hr ；在 Dr 上的关系 Hr H；H=<root ，x1> ，<root （D1，H1 ）是一棵符合本定义的二叉树，称为根的左子树， 是一棵符合本定义的二叉树，称为根的右子树。基本操作P:InitBiTree(&T);操作结果：构造空二叉树 T。Destroy

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

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

5、T 中的某个结点。操作结果：返回 e的右孩子。若 e 无右孩子，则返回 “空”。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>

6、 #define TURE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW 0#define MAXQSIZE 100 /最大队列长度typedef char TElemType;typedef struct BiTNode /二叉树结构体TElemType data; struct BiTNode *lchild,*rchild;BiTNode,*BiTree;typedef BiTree QElemType;typedef struct QNodeQElemType data; struct QNode *next;Q

7、Node, *QueuePtr; /结点结构体typedef structQueuePtr 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) / Qu

8、euePtr p;p = (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.fro

9、nt->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;elsereturn FALSE;int InitBiTree(BiTree &T) /T = NULL; return OK;销毁二叉树int DestroyTree(BiTree &T) /if(!T)return ERROR;else

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

11、ee(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; elsereturn FALSE;int BiTreeDepth(BiTree

12、 T) /int lcd,rcd;if(!T)return 0;lcd=BiTreeDepth(T->lchild); rcd=BiTreeDepth(T->rchild); return (lcd>rcd?lcd:rcd)+1);TElemType Root(BiTree T) /判断二叉树是否空，若非空返回其根if(BiTreeEmpty(T) return NULL;elsereturn (T->data);TElemType Value(BiTree T,BiTree e)/返回 e 结点的值return e->data;BiTree Point(BiTr

13、ee T,TElemType s)/返回二叉树 T 中指向元素值为的值给结点 ee->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&&a->lchild->data=e|a->rchild&&a-

14、>rchild->data=e) / 找到 ereturn a->data; /返回双亲的值elseif(a->lchild)EnQueue(q,a->lchild);/入队列左孩子if(a->rchild)EnQueue(q,a->rchild);/入队列右孩子return NULL;S的结点指针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->lch

15、ild)EnQueue(q,a->lchild);if(a->rchild)EnQueue(q,a->rchild);return NULL;TElemType LeftChild(BiTree T,TElemType e) / 返回 e 的左孩子BiTree a; if(T) a=Point(T,e);/a是指向结点 e 的指针if(a&&a->lchild)return a->lchild->data;TElemType RightChild(BiTree T,TElemType e) /返回 e 的右孩子return NULL; BiT

16、ree a;if(T)if(a=Point(T,e)&&a->rchild) return a->rchild->data;return NULL; TElemType LeftSibling(BiTree T,TElemType e) / 返回左兄弟TElemType a; 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)

17、/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=Point(T,a);/p指向结点 a 的指针if(p->lchild&&p->rchild&&p->lchild->data=e)/p在左右孩子而且左孩子是 ereturn p->rchild->

18、;data;return NULL;根据int InsertChild(BiTree T,BiTree p,int LR,BiTree c) /LR为0或者1，插入C为T中P所指结点的左或者右子树,/P 所指的结点原有左或右子树则成为 C 的右子树 if(P)if(LR=0) /把二叉树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

19、,int LR) if(p)if(LR=0)ClearBiTree(p->lchild); elseClearBiTree(p->rchild); return OK;return ERROR;二叉树结点访问函数void visit(TElemType e) /printf("%c",e);int PreOrderTraverse(BiTree T,void(*visit)(TElemType) / 先序遍历二叉树if(T)visit(T->data);PreOrderTraverse(T->lchild,visit);PreOrderTravers

20、e(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)PostOrd

21、erTraverse(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);/初始化队列EnQueue(q,T);/根指针入队while(!QueueEmpty(q)DeQueue(q,a);/出队元素，赋给 avisit(a->da

22、ta);/访问 a 所指结点if(a->lchild!=NULL)EnQueue(q,a->lchild);if(a->rchild!=NULL)EnQueue(q,a->rchild); return OK;return ERROR; 主函数：int main()int i,j,LR;TElemType value,a,temp;BiTree p,C;printf(" 欢迎使用本二叉树程序，请按回车键继续 .n");getchar();printf(" 正在构造空二叉树，请稍候 .");printf("n")

23、;BiTree T;InitBiTree(T); if(BiTreeEmpty(T)printf("构造空二叉树成功！ n");printf("请选择遍历该二叉树的顺序：输入 “1”为先序遍历，输入 “2”为elseprintf("构造空二叉树失败！ n");printf("请按先序遍历顺序输入二叉树各结点的值！空结点用n");CreateBiTree(T); printf("n"); getchar();printf(" 请选择接下来的操作 : 输入 “1”为查看二叉树深度， 输入 “2”为查

24、 看二叉树根节点 .n");scanf("%d",&i);if(i=1)printf("此二叉树的深度为： %dnn",BiTreeDepth(T);if(i=2)printf("此二叉树的根节点为： %cnn",Root(T);中序遍历，输入 “3”为后序遍历，输入 “4”为层序遍历 .n");scanf("%d",&i);getchar();printf("n");if(i=1)j=PreOrderTraverse(T,visit);printf(&quo

25、t;n");if(j=0)printf(" 该二叉树为空树，请重新运行程序！n");if(i=2)j=InOrderTraverse(T,visit);printf("n");if(j=0)printf(" 该二叉树为空树，请重新运行程序！n");if(i=3)j=PostOrderTraverse(T,visit);printf("n");if(j=0)printf(" 该二叉树为空树，请重新运行程序！n");if(i=4)j=LevelOrderTraverse(T,visit);

26、printf("n");if(j=0)printf(" 该二叉树为空树，请重新运行程序！n");printf("n请输入需要替换的结点： n");scanf("%c",&a); getchar(); p=Point(T,a);scanf("%c",&value);getchar();printf(" 请输入需要代入的结点值： n");Assign(T,p,value);printf(" 赋值之后该结点的值为： %cnn",p->dat

27、a);5”求该结点的printf("请输入 “1”求该结点的双亲结点，输入 “2”求该结点的左孩子， 输入 “3”求该结点的右孩子，输入 “4”求该结点的左兄弟，输入 右兄弟 .nn");scanf("%d",&i); getchar(); switch(i)case 1:if(Parent(T,value)=NULL)printf("该结点没有双亲结点。 n");printf("该结点没有右孩子结点。n");elseprintf("该结点的双点八、为： %cnn",Parent(T,v

28、alue);break;case 2:if(LeftChild(T,value)=NULL)printf("该结点没有左孩子结点。n");elseprintf("该结点的左孩为： %cnn",LeftChild(T,value);break;case 3:if(RightChild(T,value)=NULL)elseprintf("该结点的右孩点八、为：%cnn",RightChild(T,value);break;case 4:if(LeftSibling(T,value)=NULL)printf("该结点没有左兄弟。

29、n");为：为：elseprintf("该结点的%cnn",LeftSibling(T,value);case 5:break;if(RightSibling(T,value)=NULL)printf("elseprintf("该结点没有右兄弟。 n");该结点的%cnn",RightSibling(T,value);break;printf("n现在进行结点插入子树， 请按照先序遍历的顺序输入二叉树C，注意该二叉树没有右子树！ n");InitBiTree(C);CreateBiTree(C); get

30、char();printf("n请输入您需要插入子树的结点： n");scanf("%c",&a); getchar(); p=Point(T,a);为 c 的右子树 .",a);printf("n输入0示插入C为%c结点的左子树而该结点原来的左子树变printf("n输入1示插入C为%c结点的右子树而该结点原来的左子树变为 c 的右子树 , 请选择 .n",a);scanf("%d", &LR);getchar();j= InsertChild(T, p, LR, C); if

31、(j=0)printf("插入失败！ n"); elseprintf("插入成功！该新二叉树的先序遍历为： ");PreOrderTraverse(T, visit); printf("nn进行删除操作，请输入需要删除左子树或者右子树的结点：");scanf("%c",&a); getchar(); p=Point(T,a);printf("n输入0表示删除%c结点的左子树，1表示删除%c结点的右 子树，请选择 .n",a);scanf("%d", &LR);

32、 getchar();j = DeleteChild(T, p, LR); if(j=0)printf("删除失败！ n"); elseprintf("删除成功！该新二叉树的先序遍历为： ");PreOrderTraverse(T, visit);DestroyTree(T);if (!T)printf("n树已被成功销毁！程序执行完毕，请按回车键n");elseprintf("n树销毁不成功！程序执行完毕，请按回车键n");getchar();for(i=1;i<=4;+i)printf("n&q

33、uot;);printf("*IIprintf("*IIprintf("*printf("*printf("*IIprintf("*printf("*printf("*IIprintf("*感谢使用*n");printf("* *n");printf("*科四班*n");printf("*n");printf("*制作人罗志权*n");printf("*n");printf("*3111

34、005843*printf("*n");printf(" *请按回车键退出程序*IIprintf("*IIprintf("*printf("*printf("*IIprintf("*IIprintf("*getchar();return OK;4. 程序清单（计算机打印）输入的数据及各基本操作的测试结果；開始：|1四此唏译文件'拍曲焉峑2曲門拦鑫盤踌里心亡正在构造空二昊树，谙稍棋. 构造空二叉树成功！谙按先序覆历顺序输入二叉树各结点的!空结点用表示!ahd(?Pe<?(?cl?(?请选捋接下来的操作:输入y"为查看二叉树深度，输入“2"为査看二叉树根节