《二叉树抽象数据类型.docx》由会员分享，可在线阅读，更多相关《二叉树抽象数据类型.docx（28页珍藏版）》请在三一办公上搜索。
1、数据结构实验报告题目：二叉树抽象数据类型学 院计算机学院专 业计算机科学与技术年级班别学 号学生姓名指导教师成 绩XXXXX一. 实验概要实验项目名称：二叉树抽象数据类型的实现实验项目性质：设计性实验所属课程名称：数据结构实验计划学时：6二. 实验目的1. 了解二叉树的定义以及各项基本操作。2. 实现二叉树存储、遍历及其他基本功能三. 实验仪器设备和材料硬件：PC机软件：Visual C+ 6.0四. 实验的内容1. 二叉树类型定义以及各基本操作的简要描述；ADT BinaryTree 数据对象D:D是具有相同特性的数据元素的集合.数据关系R:若D=0,则R=,称BinaryTree为空二叉树
2、；若DK,则R=H, H是如下二元关系：(1) 在D中存在惟一的称为根的数据元素root，它在关系H下无前 驱；(2) 若 D-rootK0，则存在 D-root = D1,Dr, 且 D1ADr=0；(3) 若D1K0，贝。D1中存在惟一的元素x1, EH，且存在 Dr 上的关系 Hr EH； H=，H1,Hr；(4) (D1，H1)是一棵符合本定义的二叉树，称为根的左子树， 是一棵符合本定义的二叉树，称为根的右子树。基本操作P:InitBiTree(&T);操作结果：构造空二叉树T。DestroyBiTree(&T);初始条件：二叉树T存在。操作结果：销毁二叉树T。CreateBiTree
3、(&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);初始条
4、件：二叉树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无左孩子或无左兄弟，则返回、空。 R
5、ightSibling(T,e);初始条件：二叉树T存在，e是T中的某个结点。操作结果：返回e的右兄弟。若e无右孩子或无右兄弟，则返回、空。 ADT BinaryTree2. 存储结构：采用无头结点的链式存储结构实现3. 源代码：头文件及存储结构：#include#include#define TURE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW 0#define MAXQSIZE 100/最大队列长度 typedef char TElemType; typedef struct BiTNode /二叉树结构体 TEl
6、emType 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(s
7、izeof(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, QElemT
8、ype &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
9、 &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(OVER
10、FLOW); /分配存储空间失败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 BiTreeDep
11、th(BiTree T) /计算二叉树深度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;else return (T-data); TElemType Value(BiTree T,BiTree e) /返回 e 结点的值return e-data;int Assign(BiTree
12、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; /返
13、回双亲的值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);i
14、f(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
15、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)
16、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-
17、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) / 先序遍历二叉
18、树 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(
19、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
20、)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);i
21、f(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为
22、先序遍历，输入“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(该二叉树为空树，请重新
23、运行程序！ 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求该结点
24、的左兄弟，输入“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,valu
25、e)=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
26、(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= Ins
27、ertChild(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);els
28、eprintf(删除成功！该新二叉树的先序遍历为：)；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(*感谢使
29、用*mmmmn);printf( *mmmmn);printf(*计科四班*mmmmn);printf(*mmmmn);printf(* 制作人：罗志权*n)printf(*n)printf(*3111005843*mmmmprintf(*n)*printf(* 请按回车键退出程序n)*printf(* *nprintf(*nprintf(*nprintf(*nprintf(*nprintf(*ngetchar();return OK;4. 程序清单（计算机打印），输入的数据及各基本操作的测试结果;:第一步：手动创建二叉树:欢迎使用本二叉树程序，请按回车键继续-正在构造空二叉树，请稍候一构造空
30、二叉树成功！请按先序遍历顺序输入二叉树各结点的值！空结点用表示!第二步：选择操作，这里选择查看深度:请选择接下来的操作:输入七”为查看二叉树深度，输入“2”为查看二叉树根节点 i匕二叉树的深度为：3第三步：选择遍历方法，这里选择中序遍历:请选建遍历该二叉树的顺序：输入七”为先序遍历，输入“2”为中序遍历，输入3”为 启序商历，输入”为层序遍历dbeac第五步：替换某个结点:请输入需要替换的结点： 质输入需要代入的结点值: 豪值之后该结点的值为：f第六步：求该结点的邻近结点，这里选择右孩子:呕亲箜点，输入“2”求该笙点的左匿子，输入“3”求该结点的右 卓的走兄弟，输入求崔结点的若兄弟&结点的右孩
31、子结点为：e第七步：插入子树C到e结点作为e结点的左子树:现在进行结点插入子树，请按照先序遍历的顺序输入二叉树c,注意该二叉树投有右子树!ghieejeee请输入您需要插入子树的结点：e擒入示插入c为E结点的左子啊而该结点原毛的左子啊变为。的右子啊瑜入1示籍入C为e结点的右子剧而该结点原素的左子剧变为匚的右子也请选择0插入成功！该新二叉树的先序遍历为：afdeghijc第八步：删除结点的左子树或者右子树:进行删除操作，请输入需要删除左子树或者右子树的结点：f输入0表示删除F结点的左子树，1表示删除结点的右子树，请选择 Sil除成功!.该新二叉树的先序遍历为:.afdc .程序执行完毕:树m被成功销毁！程序抗行完毕;请按回车键显示作者:六.实验总结和体会。抽象数据类型是模块化思想的发展，有助于我们从更抽象的高度去讨论算法 和数据结构的问题。通过这次实验，我对二叉树的抽象数据类型更加了解和熟悉， 我们只需关心它的逻辑特征而不需要了解它的存储方式。数据结构是每个程序员 的必修课，但是我们还要学的还有很多很多，因为在设计程序的时候会遇到很多 的BUG，这些BUG都是要靠自己慢慢去了解慢慢去调试才能解决的。而且现在计 算机技术发展迅速，我们要学的可以说是无穷无尽的。
