数据结构实验报告
题目：二叉排序树
学 院 计算机学院
专 业 计算机科学与技术
年级班别 级 班
学 号
编 号
学生姓名
指导教师
成 绩 _______________________________
2015 年 月
报告：
报告内容： □详细 □完整 □基本完整 □不完整
设计方案： □非常合理 □合理 □基本合理 □较差
算法实现： □全部实现 □基本实现 □部分实现 □实现较差
测试样例： □完备 □比较完备 □基本完备 □不完备
文档格式： □规范 □比较规范 □基本规范 □不规范
答辩：
□理解题目透彻，问题回答流利
□理解题目较透彻，回答问题基本正确
□部分理解题目，部分问题回答正确
□未能完全理解题目，答辩情况较差
总评成绩：
□优 □良 □中 □及格 □不及格
1. 题目
选择合适的存储结构，建立二叉排序树，完成插入、删除等基本操作。
ADT Binary Sort Tree{
数据对象：int RcdType data;
数据关系：BSTNode *lchild, *rchild;
基本操作：
InitBST(&T)
操作结果：构造一个空的二叉排序树T。
DestroyBST(&T)
初始条件：二叉排序树T已存在。
操作结果：销毁二叉排序树T。
SearchBST(&T, key)
初始条件：二叉排序树T已存在。
操作结果：若二叉排序树T中存在值为key的结点，则返回该结点指针，否则NULL。
InsertBST(&T, e)
初始条件：二叉排序树T已存在且T中不存在值为e.key的结点。
操作结果：将e插入到T。
DeleteBST(&T, key)
初始条件：二叉排序树T已存在在且T中存在值为key的结点。
操作结果：删除值为key的结点。
TraverseBST(&T, e))
初始条件：二叉排序树T已存在
操作结果：遍历二叉排序树T中的元素。
PrintRcdType(e)
初始条件：二叉排序树T已存在。
操作结果：依次输出T的每个元素。
}ADT Binary Sort Tree
2．存储结构定义
#include #include #include #define OVERFLOW -1 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 typedef int Status; typedef int KeyType; typedef struct { KeyType key; }RcdType; typedef struct BSTNode { RcdType data; struct BSTNode *lchild, *rchild; } BSTNode, * BSTree; 3. 算法设计 使用二叉链表存储结构 Status InitBST(BSTree &T) {//构造一个空的二叉排序树T T=NULL; return OK; } Status DestroyBST(BSTree &T) {//销毁二叉排序树 T if (T) { if( T->lchild ) DestroyBST( T->lchild ); if( T->rchild ) DestroyBST( T->rchild ); free(T); T = NULL; } return OK; } BSTree SearchBST(BSTree &T,KeyType key) {//二叉排序树查找的递归实现 if(NULL==T)return NULL; //查找失败 if(T->data.key==key)return T; //查找成功 if(T->data.key>key) return SearchBST(T->lchild,key); //在左子树上继续查找 return SearchBST(T->rchild,key); //在右子树上继续查找 } void DeleteNode(BSTree &T) {//二叉排序树中删除结点T，并重接它的左或右子树 BSTree q,s; if(NULL==T->rchild){ //右子树空则只需重接它的左子树 q=T; T=T->lchild; free(q); } else if(NULL==T->lchild){ //只需重接它的右子树 q=T; T=T->rchild; free(q); } else { //左右子树均不空 q=T; s=T->lchild; while(NULL==s->rchild){ q=s; s=s->rchild; //转左，然后向右到尽头 } T->data=s->data; //s指向被删结点的前驱 if(q!=T) q->rchild=s->lchild; //重接q的右子树 else q->lchild=s->lchild; // 重接q的左子树 free(s); } } Status DeleteBST(BSTree &T,KeyType key) { //二叉排序树的删除操作 //若二叉排序树T中存在值为key的结点，则删除该节点，并返回TRUE；否则FALSE if(NULL==T) return FALSE; //不存在值为key的结点 if(key==T->data.key){ //找到值为key的结点 DeleteNode(T); return TRUE; } if(key return DeleteBST(T->lchild,key); //返回在左子树删除的结果 return DeleteBST(T->rchild,key); //返回在右子树删除的结果 } Status InsertBST(BSTree &T,RcdType e) { //二叉排序树插入 //若二叉排序树T中不存在值为e.key的结点，则插入到T BSTree s; //若二叉排序树是空树，则创建新插入的结点并作为根节点 if(NULL==T) { s=(BSTNode*)malloc(sizeof(BSTNode)); if(NULL==s)return OVERFLOW; s->data=e; s->lchild=NULL; s->rchild=NULL; T=s; return TRUE; } if(e.key //插入结点的值小于根结点，在左子树递归插入 if(e.key>T->data.key) return InsertBST(T->rchild,e); //插入结点的值大于根结点，在右子树递归插入 return FALSE; } Status TraverseBST(BSTree &T,Status (*visit) (RcdType e)) { // 中序递归遍历输出T，visit是对数据元素的应用函数 if(T) { TraverseBST(T->lchild,visit); //递归遍历T的左子树 visit(T->data); //访问结点的数据域 TraverseBST(T->rchild,visit); //递归遍历T的右子树 } return OK; } Status PrintRcdType(RcdType e) { //依次输出二叉排序树结点的值 printf("[%d],",e.key); return OK; } void main() { //主函数 int i,j=0,k; int a; int menue=0; int status; KeyType temp; int (*visit)(RcdType e); int t[20]={0}; RcdType e; BSTNode *p; BSTree Tree; visit=PrintRcdType; for(;;) { for(;menue==0;) { //menue=0则循环开始菜单 printf("\\n*********** 开始菜单 ************\\n"); printf("* 1.创建二叉排序树 \*\\n"); printf("* 2.退出 \*\\n"); printf("********************************\\n"); printf("请输入选择的序号："); scanf("%d",&i); switch(i) { case 1: status=InitBST(Tree); if(status==TRUE){ printf("请输入初始数据（空格为间隔,以0为结束符号。"); printf("注意：二叉排序树结点的值不能重复。）："); j=0; do{ scanf("%d",&t[j++]); } while(t[j-1]!=0); for(k=0;k a=InsertBST(Tree,e); if(a==FALSE) break; } if(a==FALSE) { printf("创建失败！输入的数据不能构造一个二叉排序树。\\n"); printf("按任意键返回\\n"); getch(); InitBST(Tree); continue; } else { menue=1;//创建二叉排序树成功，跳出开始菜单循环 printf("创建二叉排序树成功!\\n"); printf("中序遍历："); TraverseBST(Tree,visit); printf("\\n"); printf("按任意键进入操作菜单\\n"); getch(); } } else { printf("创建失败！\\n"); printf("按任意键返回"); getch(); } break; case 2:exit(0); default :printf("输入错误，请重新选择！"); printf("按任意键返回"); getch(); break; } } //进入操作菜单 printf("\\n*************** 操作菜单 ******************\\n"); printf("* 1.插入数据 \*\\n"); printf("* 2.查找数据 \*\\n"); printf("* 3.删除数据 \*\\n"); printf("* 4.遍历二叉排序树 \*\\n"); printf("* 5.销毁二叉排序树 \*\\n"); printf("* 6.创建新的二叉排序树 \*\\n"); printf("* 7.退出 \*\\n"); printf("******************************************\\n"); printf("请输入选择的序号："); scanf("%d",&i); switch(i) { case 1: printf("请输入您要插入的数据：");//输入插入二叉排序树的值 scanf("%d",&temp); e.key=temp; status=InsertBST(Tree,e); if(status==TRUE) { printf("插入成功。"); printf("中序遍历："); TraverseBST(Tree,visit); printf("按任意键返回"); getch(); } else { printf("插入失败，该数据已存在，按任意键返回"); getch(); } break; case 2: TraverseBST(Tree,visit); printf("\\n"); printf("请输入您要查找的数据："); //输入查询的值 scanf("%d",&temp); p=SearchBST(Tree,temp); if(p==NULL){ printf("查找失败！该数据不存在\\n"); printf("按任意键返回"); getch(); } else { printf("您所查找的数据为："); visit(p->data); printf("\\n"); printf("按任意键返回"); getch(); } break; case 3: TraverseBST(Tree,visit); printf("\\n"); printf("请输入您要删除的数据："); //输入删除的值 scanf("%d",&temp); status=DeleteBST(Tree,temp); if(status) { printf("删除成功！\\n"); printf("中序遍历："); TraverseBST(Tree,visit); printf("\\n"); printf("按任意键返回"); getch(); } else { printf("删除失败！不存在要删除的值"); printf("按任意键返回"); getch(); } break; case 4: //遍历二叉排序树 printf("二叉排序树中序遍历为："); TraverseBST(Tree,visit); printf("\\n"); printf("按任意键返回"); getch(); break; case 5: //销毁二叉排序树 status =DestroyBST(Tree); if(status==TRUE) { printf("销毁成功！\\n"); printf("按任意键返回开始菜单"); getch(); menue=0; //销毁二叉树排序树成功后返回开始菜单 } else { printf("销毁失败！\\n"); printf("按任意键返回"); getch(); } break; case 6: //创建新的二叉排序树 DestroyBST(Tree); //先销毁原来的二叉排序树 InitBST(Tree); //再创建一个空的二叉排序树 menue=0; //进入开始菜单创建 break; case 7:exit(0); default :printf("输入错误，请重新选择！"); printf("按任意键返回"); getch(); break; } } } 4．测试 (1).创建二叉排序树 (2).插入数据 (3).查找数据 (4).删除数据 (5).遍历和销毁 5．各个操作的时间复杂度 我所写的程序和课本上的二叉排序树操作基本相同！但是在调试过程中遇到了一些问题。一开始存在的基本的语法错误，问题主要在于函数和变量的定义，关键字和函数名的书写。 通过这次试验让我进一步对树的应用有了进一步的了解，同时对查找这种基本数据操作有了较深刻的认识。对函数的构造以及调用有了更进一步的掌握，让我在调试程序是有了一定的经验。
6．心得体会基本操作 时间复杂度 InitBST(&T) O(1) DestroyBST(&T) O(n) SearchBST(&T, key) O(n) InsertBST(&T, e) O(n) DeleteBST(&T, key) O(n) TraverseBST(&T, e)) O(n) PrintRcdType(e) O(1)
