实验报告-平衡二叉树.doc

《实验报告-平衡二叉树.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实习报告一、需求分析1、问题描述利用平衡二叉树实现一个动态查找表。（1）实现动态查找表的三种基本功能：查找、插入和删除。（2）初始时，平衡二叉树为空树，操作界面给出查找、插入和删除三种操作供选择。每种操作均要提示输入关键字。在查找时，如果查找的关键字不存在，则把其插入到平衡二叉树中。每次插入或删除一个结点后，应更新平衡二叉树的显示。（3）每次操作的关键字都要从文件中读取，并且关键字的集合限定为短整型数字{1，2，3······}，关键字出现的顺序没有限制，允许出现重复的关键字，并对其进行相应的提示。（4）平衡二叉树的显示采用图形界面画出图形。2、系统功能打开数据文件，用文件中的关键

2、字来演示平衡二叉树操作的过程。3、程序中执行的命令包括：（1）(L)oadfromdatafile//在平衡的二叉树中插入关键字；（2）(A)ppendnewrecord//在平衡的二叉树中查找关键字；（3）(U)patespecialrecord//显示调整过的平衡二叉树；（4）(D)eletespecialrecord//删除平衡二叉树中的关键字；（5）(Q)uit//结束。4、测试数据：平衡二叉树为：图1插入关键字10之前的平衡二叉树插入关键字：10；调整后：图2插入关键字10之后的平衡二叉树删除关键字：14；调整后：图3删除关键字14后的平衡二叉树查找关键字：11；输出：T

3、hedataishere!图3查找关键字11后的平衡二叉树二、概要设计本次实验目的是为了实现动态查找表的三种基本功能：查找、插入和删除。动态查找表可有不同的表示方法，在此次实验中主要是以平衡二叉树的结构来表示实现的，所以需要两个抽象数据类型：动态查找表和二叉树。1、动态查找表的抽象数据类型定义为：ADTDynamicSearchTable{数据对象D：D是具有相同特性的数据元素的集合。各个数据元素均含有类型相同，可唯一标识数据元素的关键字。数据关系R：数据元素同属于一个集合。基本操作P：InitDSTable(&ST);操作结果：构造一个空的动态查找表DT。DestroyDSTab

4、le(&DT);初始条件：动态查找表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中存在其

5、关键字等于key的数据元素，则删除之。}ADTDynamicSearchTable2、二叉树抽象数据类型的定义为：ADTBinaryTree{数据对象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，∈H，且存在D1上的关系H1∈H；若Dr≠￠，则Dr中存在唯一的元素x

6、r，∈H，且存在Dr上的关系Hr∈H；H={，，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存

7、在。操作结果：若T为空二叉树，则返回TRUE，否则FALSE。LeftChild(T,e);初始条件：二叉树T存在，e是T中某个结点。操作结果：返回e的左孩子。若e无左孩子，则返回“空”。RightChild(T,e);初始条件：二叉树T存在，e是T中某个结点。操作结果：返回e的右孩子。若e无右孩子，则返回“空”。InsertAVL(T,e,taller);初始条件：二叉树T存在，e为要插入的结点，taller反映T长高与否。操作结果：若在平衡二叉树中不存在和e相同关