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

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

2、；假设D，则R=H，H是如下二元关系：在D中存在惟一的称为根的数据元素root，它在关系H下无前驱；假设D-root，则存在D-root=D1,Dr，且D1Dr=；假设D1，则D1中存在惟一的元素*1，H，且存在Dr上的关系HrH；H=，H1,Hr；D1，H1是一棵符合本定义的二叉树，称为根的左子树，是一棵符合本定义的二叉树，称为根的右子树。根本操作P:InitBiTree(&T);操作结果：构造空二叉树T。DestroyBiTree(&T);初始条件：二叉树T存在。操作结果：销毁二叉树T。CreateBiTree(&T,definition);初始条件：definition给出二叉树T的定义

3、。操作结果：按definition构造二叉树T。ClearBiTree(&T);初始条件：二叉树T存在。操作结果：将二叉树T清为空树。BiTreeEmpty(T);初始条件：二叉树T存在。操作结果：假设T为空二叉树，则返回TURE,否则FALSE。BiTreeDepth(T);初始条件：二叉树T存在。操作结果：返回T的深度。Root(T);初始条件：二叉树T存在。操作结果：返回T的根。Value(T,e);初始条件：二叉树T存在，e是T中的*个结点。操作结果：返回e的值。Assign(T,&e,value); 初始条件：二叉树T存在，e是T中的*个结点。 操作结果：结点e赋值为value。Pa

4、rent(T,e); 初始条件：二叉树T存在，e是T中的*个结点。操作结果：假设e是T的非跟结点，则返回它的双亲，否则返回“空。LeftChild(T,e);初始条件：二叉树T存在，e是T中的*个结点。操作结果：返回e的左孩子。假设e无左孩子，则返回“空。RightChild(T,e);初始条件：二叉树T存在，e是T中的*个结点。操作结果：返回e的右孩子。假设e无右孩子，则返回“空。LeftSibling(T,e);初始条件：二叉树T存在，e是T中的*个结点。操作结果：返回e的左兄弟。假设e无左孩子或无左兄弟，则返回“空。RightSibling(T,e); 初始条件：二叉树T存在，e是T中的

5、*个结点。操作结果：返回e的右兄弟。假设e无右孩子或无右兄弟，则返回“空。ADT BinaryTree2.存储构造：采用无头结点的链式存储构造实现3.源代码：头文件及存储构造:*include*include*define TURE 1*define FALSE 0*define OK 1*define ERROR 0*define OVERFLOW 0*define MA*QSIZE 100 /最大队列长度typedef char TElemType; typedef struct BiTNode /二叉树构造体TElemType data;struct BiTNode *lchild,*r

6、child;BiTNode,*BiTree;typedef BiTree QElemType;typedef struct QNode QElemType data; struct QNode *ne*t; QNode, *QueuePtr; /结点构造体typedef struct QueuePtr front; QueuePtr rear; LinkQueue; /链队列构造体 算法设计：int InitQueue(LinkQueue &Q) /构造空队列 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) /新元素入队尾 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) /删除队头元素 QueuePt

8、r p; if(Q.front = Q.rear) /队列为空队 return ERROR; p = Q.front-ne*t; e = p-data; Q.front-ne*t = p-ne*t; 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 =

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) /用先序遍历的方式构建二叉树,以表示空结点。 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); /构造左子树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 T) /计算二叉树深

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) /判断二叉树是否空，假设非空返回其根if(BiTreeEmpty(T)return NULL;elsereturn (T-data);TElemType Value(BiTree T,BiTree e) /返回e结点的值return e-data;int Assign(BiTree T,BiTree &e,TElemType valu

12、e) / 将value的值给结点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-rchild-data=e) /找到ereturn a-data; /返回双亲的值elseif(a-lchild)EnQueue(q,

13、a-lchild);/入队列左孩子if(a-rchild)EnQueue(q,a-rchild);/入队列右孩子return NULL;BiTree Point(BiTree T,TElemType s)/返回二叉树T中指向元素值为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-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是指向结点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指向结点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指向结点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为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;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) /二叉树结点函数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);/初始化队列EnQueue(q,T);/根指针入队while(!QueueEmpty(q)DeQueue(q,a);/出队元素，赋给avisit(a-data);/a所指结点if(a-

20、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);BiTree T;InitBiTree(T);if(BiTreeEmpty(T)printf(构造空二叉树成功！n);elseprintf(构造空二叉树

21、失败！n);printf(请按先序遍历顺序输入二叉树各结点的值！空结点用表示！n);CreateBiTree(T);printf(n);getchar();printf(请选择接下来的操作:输入“1为查看二叉树深度，输入“2为查看二叉树根节点.n);scanf(%d,&i);if(i=1)printf(此二叉树的深度为：%dnn,BiTreeDepth(T);if(i=2)printf(此二叉树的根节点为：%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(该二叉树为空树，请重新运行程序！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);printf(n);if(j=

23、0)printf(该二叉树为空树，请重新运行程序！n);printf(n请输入需要替换的结点：n);scanf(%c,&a);getchar();p=Point(T,a);printf(请输入需要代入的结点值：n);scanf(%c,&value);getchar();Assign(T,p,value);printf(赋值之后该结点的值为：%cnn,p-data);printf(请输入“1求该结点的双亲结点，输入“2求该结点的左孩子，输入“3求该结点的右孩子，输入“4求该结点的左兄弟，输入“5求该结点的右兄弟.nn);scanf(%d,&i);getchar();switch(i)case 1

24、:if(Parent(T,value)=NULL)printf(该结点没有双亲结点。n);elseprintf(该结点的双亲结点为：%cnn,Parent(T,value);break;case 2:if(LeftChild(T,value)=NULL)printf(该结点没有左孩子结点。n);elseprintf(该结点的左孩子结点为：%cnn,LeftChild(T,value);break;case 3:if(RightChild(T,value)=NULL)printf(该结点没有右孩子结点。n);elseprintf(该结点的右孩子结点为：%cnn,RightChild(T,valu

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

26、ee(C);getchar();printf(n请输入您需要插入子树的结点：n);scanf(%c,&a);getchar();p=Point(T,a);printf(n输入0示插入C为%c结点的左子树而该结点原来的左子树变为c的右子树.,a);printf(n输入1示插入C为%c结点的右子树而该结点原来的左子树变为c的右子树,请选择.n,a);scanf(%d, &LR);getchar();j= InsertChild(T, p, LR, C);if(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);getchar();j = DeleteChild(T, p, LR);if(j=0)printf(删除失败！n);elseprintf(删除成功！该