没有合适的资源?快使用搜索试试~ 我知道了~
实验报告平衡二叉树.pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 83 浏览量
2023-06-06
13:13:07
上传
评论
收藏 515KB PDF 举报
温馨提示
试读
18页
实验报告平衡二叉树.pdf
资源推荐
资源详情
资源评论
文档来源为:从网络收集整理.word 版本可编辑.欢迎下载支持.
实习报告
一、需求分析
1、问题描述
利用平衡二叉树实现一个动态查找表。
(1)实现动态查找表的三种基本功能:查找、插入和删除。
(2)初始时,平衡二叉树为空树,操作界面给出查找、插入和删除三种
操作供选择。每种操作均要提示输入关键字。在查找时,如果查找的关键字
不存在,则把其插入到平衡二叉树中。每次插入或删除一个结点后,应更新
平衡二叉树的显示。
(3)每次操作的关键字都要从文件中读取,并且关键字的集合限定为短
整型数字{1,2,3······},关键字出现的顺序没有限制,允许出现重复的
关键字,并对其进行相应的提示。
(4)平衡二叉树的显示采用图形界面画出图形。
2、系统功能
打开数据文件,用文件中的关键字来演示平衡二叉树操作的过程。
3、程序中执行的命令包括:
(1)(L)oad from data file //在平衡的二叉树中插入关键字;
(2)(A)ppend new record //在平衡的二叉树中查找关键字;
(3)(U)pate special record //显示调整过的平衡二叉树;
(4)(D)elete special record //删除平衡二叉树中的关键字;
(5)(Q)uit //结束。
4、测试数据:
平衡二叉树为:
图 1 插入关键字 10 之前的平衡二叉树
插入关键字:10;
调整后:
图 2 插入关键字 10 之后的平衡二叉树
删除关键字:14;
调整后:
文档来源为:从网络收集整理.word 版本可编辑.欢迎下载支持.
图 3 删除关键字 14 后的平衡二叉树
查找关键字:11;
输出: The data is here!
图 3 查找关键字 11 后的平衡二叉树
二、概要设计
本次实验目的是为了实现动态查找表的三种基本功能:查找、插入和删除。
动态查找表可有不同的表示方法,在此次实验中主要是以平衡二叉树的结构来表
示实现的,所以需要两个抽象数据类型:动态查找表和二叉树。
1、 动态查找表的抽象数据类型定义为:
ADT DynamicSearchTable
{数据对象 D :D 是具有相同特性的数据元素的集合。各个数据元素均含
有类型相同,可唯一标识数据元素的关键字。
数据关系 R :数据元素同属于一个集合。
基本操作 P :
InitDSTable(&ST);
操作结果:构造一个空的动态查找表 DT。
DestroyDSTable(&DT);
文档来源为:从网络收集整理.word 版本可编辑.欢迎下载支持.
初始条件:动态查找表 DT 存在。
操作结果:销毁动态查找表 DT。
SearchDSTable(DT,key);
初始条件:动态查找表 DT 存在,key 为和关键字类型相同的给丁值。
操作结果:若 DT 中存在其关键字等于 key 的数据元素,则函数值为
该元素的值或在表中的位置,否则为“空”。
InsertDSTable(&DT,e);
初始条件:动态查找表 DT 存在,e 为待插入的数据元素。
操作结果:若 DT 中不存在其关键字等于 e,key 的数据元素,则插入
e 到 DT;
DeleteDSTable(&DT,key);
初始条件:动态查找表 DT 存在,key 为和关键字类型相同的给定值。
操作结果:若 DT 中存在其关键字等于 key 的数据元素,则删除之。
}ADT DynamicSearchTable
2、二叉树抽象数据类型的定义为:
ADT BinaryTree
{数据对象 D :D 是具有相同特性的数据元素的集合。
数据关系 R :
若 D=¢,则 R=¢,称 BinaryTree 为空的二叉树;
若 D≠¢,则 R={H},H 是如下二元关系:
(1) 在 D 中存在唯一的称为根的数据元素 root,它在关系 H 下无前
驱;
(2) 若 D—{root}≠¢,则存在 D—{root}={D1,Dr},且 D1∩Dr=¢;
(3) 若 D1≠¢,则 D1 中存在唯一的元素 x1,<root,x1>∈H,且
存在 D1 上的关系 H1∈H;若 Dr≠¢,则 Dr 中存在唯一的元
素 xr,<root,xr>∈H,且存在 Dr 上的关系 Hr∈H;H={<root,
x1>,<root,xr>,H1,Hr};
(4) (D1,{H1})是一棵符合本定义的二叉树,称为根的左子树,
(Dr,{Hr})是符合本定义的二叉树,称为根的右子树。
基本操作 P:
InitBiTree(&T);
操作结果:构造空的二叉树 T;
DestroyBiTree(&T);
初始条件:二叉树 T 存在。
操作结果:销毁二叉树 T。
CreateBiTree(&T,definition);
初始条件:definition 给出 T 的定义。
操作结果:按 definition 构造二叉树 T。
BiTreeEmpty(T);
初始条件:二叉树 T 存在。
操作结果:若 T 为空二叉树,则返回 TRUE,否则 FALSE。
LeftChild(T,e);
初始条件:二叉树 T 存在,e 是 T 中某个结点。
操作结果:返回 e 的左孩子。若 e 无左孩子,则返回“空”。
文档来源为:从网络收集整理.word 版本可编辑.欢迎下载支持.
RightChild(T,e);
初始条件:二叉树 T 存在,e 是 T 中某个结点。
操作结果:返回 e 的右孩子。若 e 无右孩子,则返回“空”。
InsertAVL(T,e,taller);
初始条件:二叉树 T 存在,e 为要插入的结点,taller 反映 T 长高与否。
操作结果:若在平衡二叉树中不存在和 e 相同关键字的结点,则插入一个
数据元素为 e 的结点,并返回 1,否则返回 0。若因插入而使
二叉排序树失去平衡,则旋转处理。
RightProcess(T);
初始条件:二叉树 T 存在。
操作结果:对以 T 为根的二叉树做右旋转处理,处理之后 T 指向新的树根
结点。
LeftProcess(T);
初始条件:二叉树 T 存在。
操作结果:对以 T 为根的二叉树做左旋转处理,处理之后 T 指向新的树根
结点
}
3、本程序包括四个模块:
(1)主程序模块:
void main()
{ for(;;)
{ switch()
{
接受命令;
处理命令;
}
}
}
(2)二叉树单元模块:
实现二叉树的抽象数据类型。
(3)动态查找表单元模块:
实现动态查找表的抽象数据类型。
(4)结点结构模块:
实现平衡二叉树的查找、插入和删除操作。
各模块之间的关系:
图 4 各模块之间的关系
三、详细设计
主程序模块
1、元素类型、结点类型和指针类型;
typedef int InfoType
typedef struct node /*记录类型*/
动态查找表单元模块
{
InfoType data; /*其他数据域*/
二叉树单元模块:
剩余17页未读,继续阅读
资源评论
hhappy0123456789
- 粉丝: 64
- 资源: 5万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功