实验报告平衡二叉树

实习报告 一、需求分析 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； 调整后： 图 3 删除关键字14 后的平衡二叉树 查找关键字：11； 输出： The data is here! 图 3 查找关键字11 后的平衡二叉树 二、概要设计 本次实验目的是为了实现动态查找表的三种基本功能：查找、插入和删除。动态查找表可有不同的表示方法，在此次实验中主要是以平衡二叉树的结构来表示实现的，所以需要两个抽象数据类型：动态查找表和二叉树。 1、 动态查找表的抽象数据类型定义为： ADT DynamicSearchTable {数据对象 D ：D 是具有相同特性的数据元素的集合。各个数据元素均含有类型相同，可唯一标识数据元素的关键字。 数据关系 R ：数据元素同属于一个集合。 基本操作 P ： InitDSTable(&ST); 操作结果：构造一个空的动态查找表DT。 DestroyDSTable(&DT); 初始条件：动态查找表DT 存在。 操作结果：销毁动态查找表DT。 SearchDSTable(DT,key); 初始条件：动态查找表DT 存在，key 为和关键字类型相同的给丁值。 操作结果：若DT 中存在其关键字等于key 的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”。 InsertDSTable(&DT...