二叉树抽象数据类型.docx

数据结构实验报告题目：二叉树抽象数据类型学 院计算机学院专 业计算机科学与技术年级班别学 号学生姓名指导教师成 绩XXXXX一. 实验概要实验项目名称：二叉树抽象数据类型的实现实验项目性质：设计性实验所属课程名称：数据结构实验计划学时：6二. 实验目的1. 了解二叉树的定义以及各项基本操作。2. 实现二叉树存储、遍历及其他基本功能三. 实验仪器设备和材料硬件：PC机软件：Visual C+ 6.0四. 实验的内容1. 二叉树类型定义以及各基本操作的简要描述；ADT BinaryTree 数据对象D:D是具有相同特性的数据元素的集合.数据关系R:若D=0,则R=,称BinaryTree为空二叉树；若DK,则R=H, H是如下二元关系：(1) 在D中存在惟一的称为根的数据元素root，它在关系H下无前 驱；(2) 若 D-rootK0，则存在 D-root = D1,Dr, 且 D1ADr=0；(3) 若D1K0，贝。D1中存在惟一的元素x1, <root, x1>EH，且存在 Dr 上的关系 Hr EH； H=<root，x1>，<root，xr>，H1,Hr；(4) (D1，H1)是一棵符合本定义的二叉树，称为根的左子树， 是一棵符合本定义的二叉树，称为根的右子树。基本操作P:InitBiTree(&T);操作结果：构造空二叉树T。DestroyBiTree(&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);初始条件：二叉树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的非跟结点，则返回它的双亲，否则返回'、空。 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中的某个结点。操作结果：返回e的右兄弟。若e无右孩子或无右兄弟，则返回'、空。 ADT BinaryTree2. 存储结构：采用无头结点的链式存储结构实现3. 源代码：头文件及存储结构：#include<stdio.h>#include<stdlib.h>#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 QNode QElemType data;struct QNode *next;QNode, *QueuePtr;/结点结构体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 = (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->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)/f销毁二叉树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)exit(OVERFLOW); /分配存储空间失败T->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;else return FALSE; int BiTreeDepth(BiTree 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;else return (T->data); TElemType Value(BiTree T,BiTree e) /返回 e 结点的值return e->data;int Assign(BiTree T,BiTree &e,TElemType value) / 将 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) /找至0 ereturn a->data; /返回双亲的值else if(a->lchild)EnQueue(q,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);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;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,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=Point(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;return 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,visit);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)PostOrderTraverse(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->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("构造空二叉树失败！ 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);getchar();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=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: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,value);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);CreateBiTree(C);getchar();printf("n请输入您需要插入子树的结点：n");scanf("%c”,&a);getchar();p=Point(T,a);printf (-n输入0示插入C为°结点的左子树而该结点原来的左子树变 为c的右子树.”，a);printf("n输入1示插入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("删除成功！该新二叉树的先序遍历为：")；PreOrderTraverse(T, visit); DestroyTree(T);if (!T)printf（"n树已被成功销毁！程序执行完毕，请按回车键n"）;elseprintf（"n树销毁不成功！程序执行完毕，请按回车键n"）;getchar();for(i=1;i<=4;+i)printf("n");printf("*mmmn");printf("*mmmn");printf("*mmmn");printf("*mmmn");printf("*mmmn");printf("*mmmn");printf("*mmmn");printf("*mmmn");printf("*感谢使用*mmmmn");printf(" *mmmmn");printf("*计科四班*mmmmn");printf("*mmmmn");printf("* 制作人：罗志权*n")printf(*n")printf(*3111005843*mmmmprintf(*n")*printf(* 请按回车键退出程序n")*printf("* *n»printf("*n»printf("*n»printf("*n»printf("*n»printf("*n»getchar();return OK;4. 程序清单（计算机打印），输入的数据及各基本操作的测试结果;":第一步：手动创建二叉树:欢迎使用本二叉树程序，请按回车键继续-正在构造空二叉树，请稍候一构造空二叉树成功！请按先序遍历顺序输入二叉树各结点的值！空结点用表示!第二步：选择操作，这里选择查看深度:请选择接下来的操作:输入七”为查看二叉树深度，输入“2”为查看二叉树根节点 i匕二叉树的深度为：3第三步：选择遍历方法，这里选择中序遍历:请选建遍历该二叉树的顺序：输入七”为先序遍历，输入“2”为中序遍历，输入"3”为 启序商历，输入”为层序遍历dbeac第五步：替换某个结点:请输入需要替换的结点： 质输入需要代入的结点值: 豪值之后该结点的值为：f第六步：求该结点的邻近结点，这里选择右孩子:呕亲箜点，输入“2”求该笙点的左匿子，输入“3”求该结点的右 卓的走兄弟，输入求崔结点的若兄弟&结点的右孩子结点为：e第七步：插入子树C到e结点作为e结点的左子树:现在进行结点插入子树，请按照先序遍历的顺序输入二叉树c,注意该二叉树投有右子树!ghieejeee请输入您需要插入子树的结点：e擒入©示插入c为E结点的左子啊而该结点原毛的左子啊变为。的右子啊瑜入1示籍入C为e结点的右子剧而该结点原素的左子剧变为匚的右子也"请选择0插入成功！该新二叉树的先序遍历为：afdeghijc第八步：删除结点的左子树或者右子树:进行删除操作，请输入需要删除左子树或者右子树的结点：f输入0表示删除F结点的左子树，1表示删除结点的右子树，请选择 Sil除成功!.该新二叉树的先序遍历为:.afdc .程序执行完毕:树m被成功销毁！程序抗行完毕;请按回车键显示作者:六.实验总结和体会。抽象数据类型是模块化思想的发展，有助于我们从更抽象的高度去讨论算法 和数据结构的问题。通过这次实验，我对二叉树的抽象数据类型更加了解和熟悉， 我们只需关心它的逻辑特征而不需要了解它的存储方式。数据结构是每个程序员 的必修课，但是我们还要学的还有很多很多，因为在设计程序的时候会遇到很多 的BUG，这些BUG都是要靠自己慢慢去了解慢慢去调试才能解决的。而且现在计 算机技术发展迅速，我们要学的可以说是无穷无尽的。