实验7-查找排序的应用

实验报告书

课程名： 数据结构

题 目： 查找、排序的应用实验（1） 班 级： 学 号： 姓 名：

评语： 成绩： 指导教师： 批阅时间： 年 月 日

《 数据结构 》实验报告 - 1 -

一、目的与要求

1）完整理解二叉排序树的基本概念;

2) 掌握二叉排序树的建立、查找、插入和删除算法实现思想和基本应用方法； 3）掌握二叉排序树的建立、查找、插入和删除算法实现的c语言编程技巧；

4）按照实验题目要求独立正确地完成实验内容（提交程序清单及相关实验数据与运行结果）； 5）认真书写实验报告,并按时提交。

二、实验内容或题目

用C或C++语言设计实现二叉排序树的基本操作应用程序，功能包括：二叉排序树的建立，二叉排序树的查找，二叉排序树的插入，二叉排序树的删除。程序实现后，用记录关键字序列：{98，47，55，70，22，8，32，69}进行正确性验证（在建立、删除、插入操作后要给出相应二叉排序树遍历结果）。

三、实验步骤与源程序

#include \

#include #include #include

#define MAX_Node_NUM 20 #define ElemType int #define KeyType int #define InforType char #define TRUE 1 #define FALSE 0

#define EQ(a,b) ((a)==(b)) #define LT(a,b) ((a)<(b)) #define LQ(a,b) ((a)<=(b))

typedef struct data{

KeyType key; //记录的关键字

InforType *infor; //记录的其它信息指针 }Data,*DT;

typedef struct BiTNode{ Data data;

struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; BiTree p,f,s,q;

int SearchBST(BiTree T,KeyType key,BiTree f,BiTree &p){

//根指针T所指的二插排序数递归查找关键字等于key的数据元素， //查找成功时，p指向该结点，并返回TRUE，否则p指向查找路径

//上访问的最后一个结点，并返回FALSE，指针f指向T的双亲，其初始值为NULL； if(!T){p=f;return FALSE;} //查找不成功 else if(EQ(key,T->data.key)){p=T;return TRUE;} //查找成功

《 数据结构 》实验报告 - 2 -

else if(LT(key,T->data.key))return SearchBST(T->lchild,key,T,p); //在左子树中继续查找 else return SearchBST(T->rchild,key,T,p); //在右子树中继续查找

}//SearchBST

int InsertBST(BiTree &T,DT e){

//若二插排序树中不存在关键字等于e.key的数据元素时， //插入e并返回TRUE,否则返回FALSE if(!SearchBST(T,e->key,NULL,p)){

s=(BiTree)malloc(sizeof(BiTNode)); s->data=*e;s->lchild=s->rchild=NULL;

if(!p)T=s; //头记录 else if(LT(e->key,p->data.key))p->lchild=s; else p->rchild=s; return TRUE; }

else return FALSE; }//InsertBST

int Delete(BiTree &p){

//从二插排序树中删除结点p,并重接它的左右子树 if(!p->rchild){

//右子树空则只需重接它的左子树 q=p;p=p->lchild;delete q; }

else if(!p->lchild){

//左子树空则只需重接它的右子树 q=p;p=p->rchild;delete q; }

else {

//左右子树均不空 q=p;s=p->lchild;

while(s->rchild){q=s;s=s->rchild;} //找到中序遍历时p的直接前驱s p->data=s->data; //s指向被删结点的前驱

if(q!=p) q->rchild=s->lchild; //重接*q的右子树 else q->lchild=s->lchild; //重接*q的左子树 delete s; }

return TRUE; }//Delete

int DeleteBST(BiTree &T,KeyType key){

《 数据结构 》实验报告 - 3 -

//若二插排序树中存在关键字等于key的数据元素时， //则删除该数据元素结点，并返回TRUE，否则返回FALSE

if(!T)return FALSE; //不存在关键字等于key的数据元素结点 else {

if(EQ(key,T->data.key)) return Delete(T); //找到关键字等于key的数据元素结点 else if(LT(key,T->data.key))return DeleteBST(T->lchild,key); else return DeleteBST(T->rchild,key); }

}//DeleteBST

void InOrderTraverse(BiTree T){ if(!T) return ; else {

InOrderTraverse(T->lchild); cout<data.key<<\ InOrderTraverse(T->rchild); }

return; }//中序遍历

void main() {

BiTree T=NULL; DT e,c;

int i,j=0,n;

KeyType key1,key2,key3;

cout<<\在二叉排序树T上的操作\

cout<<\;

cout<<\<

cout<<\建立二叉排序树\二叉排序树中关键字的查找\ cout<<\二叉排序树中关键字的插入\二叉排序树中关键字的删除\

cout<<\中序遍历打印二叉排序树\将表置空\退出操作\ while(j!=7) {

cout<<\选择上面的数字操作项:\ cin>>j;

if(j!=1&&j!=2&&j!=3&&j!=4&&j!=5&&j!=6&&j!=7) {