《二叉树抽象数据类型数据结构实验报告》由会员分享，可在线阅读，更多相关《二叉树抽象数据类型数据结构实验报告（24页珍藏版）》请在金锄头文库上搜索。
1、数据结构实验报告题目：二叉树抽象数据类型的实现 学 院 *学院 专 业 * 年级班别 * 学 号 * 学生姓名 * 指导教师 成 绩 _2012年6月 报告：内容：详细完整不完整设计方案：非常合理合理较差实现：全部实现部分实现未实现文档格式：规范基本规范不规范答辩：理解题目透彻，问题回答流利理解题目较透彻，回答问题基本正确部分理解题目，部分问题回答正确未能完全理解题目，答辩情况较差总评成绩：优良中及格不及格差距大，市场体系不完善，缺乏集聚效应等问题，同时充分考虑到该地周围已形成成熟建材商圈的商业价值，因地制宜的进行家居建材广场的建设。通过合理布局、优化环境、提升服务，该项目必将切实发挥商业区在
2、引导消费、拉动经济增长方面的作用，促进该县经济和社会又好又快发展。一实验概要二叉树抽象数据类型的实现二.实验目的1. 了解二叉树的定义以及各项基本操作。2. 实现二叉树存储、遍历及其他基本功能三. 实验仪器设备和材料 Visual studio 2010四实验的内容1.二叉树类型定义以及各基本操作的简要描述；ADT BinaryTree 数据对象D:D是具有相同特性的数据元素的集合.数据关系R:若D=，则R=,称BinaryTree为空二叉树；若D，则R=H，H是如下二元关系：(1) 在D中存在惟一的称为根的数据元素root，它在关系H下无前驱；(2) 若D-root，则存在D-root=D1
3、,Dr，且D1Dr=；(3) 若D1，则D1中存在惟一的元素x1，H，且存在Dr上的关系HrH；H=，H1,Hr；(4) （D1，H1）是一棵符合本定义的二叉树，称为根的左子树，是一棵符合本定义的二叉树，称为根的右子树。基本操作P:InitBiTree(&T);操作结果：构造空二叉树T。DestroyBiTree(&T);初始条件：二叉树T存在。操作结果：销毁二叉树T。CreateBiTree(&T,definition);初始条件：definition给出二叉树T的定义。操作结果：按definition构造二叉树T。ClearBiTree(&T);初始条件：二叉树T存在。操作结果：将二叉树T
4、清为空树。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的非跟结点，则返回它的双亲，否则返回“空”
5、。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.所选择的存储结构描述
6、及在此存储结构上各基本操作的实现；3.源代码主文件:main.ccp:#includebase.h/ 公用头文件、公共常量及公共函数等#includebitree.h/ 二叉树二叉链表基本操作voidMenu();/ 菜单函数voidProduce(char *str);/ 随机产生二叉树先序序列函数intmain()/ 主函数BiTreeT,bt,insert_bt;charcmd,strMAXSIZE,elem;intloc,temp;InitBiTree(T);/ 初始化二叉链表二叉树Menu();/ 显示菜单while(1)ClearLine();/ 清空结果显示区printf(请选择
7、操作：(按Q退出);cmd = getch();ClearLine();fflush(stdin);switch(cmd)case 0:/ 随机创建一棵二叉树while(cmd != y & cmd != Y)Produce(str);/ 随机产生二叉树先序序列CreateBiTree(T,str);/ 用此序列建树ShowBiTree(T);/ 广义表形式显示printf( 使用创建的这个二叉树?);cmd = getch();ClearLine();break;case 2:/ 手动创建一棵二叉树printf( 请按二叉树先序序列输入二叉树：(空结点用空格 表示)n );CreateBiT
8、ree(T);ClearLine();printf( 二叉树创建成功!n);ShowBiTree(T);getch();break;case 4:/ 销毁二叉树DestroyBiTree(T);printf( 二叉树已被销毁!);getch();break;case 6:/ 判空if(BiTreeEmpty(T) printf(二叉树是空二叉树。);elseprintf(二叉树非空);getch();break;case 8:/ 求深度printf(深度是 %d,BiTreeDepth(T);getch();break;case a:/ 求左孩子ShowBiTree(T);printf(你想求
9、哪个字符的左孩子？);doelem = getchar();ClearLine();bt = SearchBiTree(T,elem);/ 查找指定的结点值elemif(!bt) printf( 你输入的结点不存在!请重新输入：);while(!bt);ClearLine();bt = LeftChild(T,bt);/ 求左孩子if(bt) printf( %c的左孩子是%c,elem,bt-data);elseprintf( %c没有左孩子,elem);printf(n参照二叉树:);ShowBiTree(T);getch();break;case c:/ 求右孩子ShowBiTree(T
10、);printf( 你想求哪个字符的右孩子？);doelem = getchar();ClearLine();bt = SearchBiTree(T,elem);if(!bt) printf( 你输入的结点不存在!请重新输入：);while(!bt);ClearLine();bt = RightChild(T,bt);if(bt) printf( %c的右孩子是%c,elem,bt-data);elseprintf( %c没有右孩子,elem);printf(n参照二叉树:);ShowBiTree(T);getch();break;case 1:/ 先序遍历if(!BiTreeEmpty(T)
11、printf(先序遍历序列为：);PreOrderTraverse(T,Visit);else printf(二叉树空，请先建树!);getch();break;case 3:/ 中序遍历if(!BiTreeEmpty(T)printf(中序遍历序列为：);InOrderTraverse(T,Visit);else printf(二叉树空，请先建树!);getch();break;case 5:/ 后序遍历if(!BiTreeEmpty(T)printf(后序遍历序列为：);PostOrderTraverse(T,Visit);else printf( 二叉树空，请先建树!);getch();
12、break;case 7:/ 层次遍历if(!BiTreeEmpty(T)printf(层次遍历序列为：);LevelOrderTraverse(T,Visit);else printf(二叉树空，请先建树!);getch();break;case 9:/ 插入一棵二叉树为另一棵二叉树的子树do/ 随机创建一棵右孩子为空Produce(str);/ 且层数小于4的树CreateBiTree(insert_bt,str);while(insert_bt-rchild|BiTreeDepth(insert_bt) 3);printf( 先随机创建一棵右子树空的二叉树如图n);ShowBiTree(insert_bt);/ 新创建的树getch();printf(
