二叉排序树的创建、删除、插入等操作.doc

计算机科学与工程学院
武 汉 工 程 大 学
计算机科学与工程学院
《数据结构》实验报告
专业班级
09计算机工程01
实验地点
419
学生学号
0905080116
指导教师
蔡琼
学生姓名
沈亮
实验时间

实验项目
查找技术综合应用
实验类别
操作性（）验证性（ ）设计性（ ）综合性（Y ）其它（ ）
实验目的及要求
（1）熟练掌握查找的常用算法；
（2）熟练设计和应用查找算法解决比较简单的实际问题。

成 绩 评 定 表
类 别
评 分 标 准
分值
得分
合 计
上机表现
积极出勤、遵守纪律
认真完成实验任务
30分

报告质量
程序代码规范、功能正确
填写内容完整、体现收获
70分

说明：

评阅教师： 日 期： 年 月 日

实验内容：二叉排序树。
任意给定一组数据，设计一个算法，建立一棵二叉排序树，对它进行查找、插入、删除等操作。
实验说明：
二叉排序树存储结构如下：
typedef struct BiTNode { // 结点结构

struct BiTNode *lchild, *rchild;
// 左右孩子指针
} BiTNode, *BiTree;

二叉排序树插入算法伪代码如下：
1. 若root是空树，则将结点s作为根结点插入；否则
2. 若s->data＜root->data，则把结点s插入到root的左子树中；否则
3. 把结点s插入到root的右子树中。

二叉排序树中删除一个结点f的左孩子结点p算法伪代码如下：
1. 若结点p是叶子，则直接删除结点p；
2. 若结点p只有左子树，则只需重接p的左子树；
若结点p只有右子树，则只需重接p的右子树；
3. 若结点p的左右子树均不空，则
3.1 查找结点p的右子树上的最左下结点s以及结点s的双亲结点par；
3.2 将结点s数据域替换到被删结点p的数据域；
3.3 若结点p的右孩子无左子树，则将s的右子树接到par的右子树上；
否则，将s的右子树接到结点par的左子树上；
3.4 删除结点s；

1.实验分析：
程序的主要流程图：
否
是
开始
建树：
① 依次输入n个关键字
② 插入二叉排序树中
③ 中序输出创建过程

删除任意结点
插入一个结点
查找关键字

中序输出操作后二叉排序树
是否继续
结束

主要模块：
1）主函数模块
Main()
{
建立n个关键字的二叉排序树并输出；
从二叉树排序树T中删除任意结点,其关键字为key；
在二叉树排序树T中，插入一个结点t,其关键字为key；
在二叉排序树T中递归查找关键字等于 key2 的数据元素；
}
2）创建二叉排序树模块
BiTree CreatBST(int n)
{
建立n个关键字的二叉排序树；
从键盘输入调建立n个关键字依次用InsertBST1（插入函数）；
返回根结点T；
输出过程；
}
3）删除模块
DeleteNode(BiTree &T, int x)
{
从二叉树排序树T中删除任意结点,其关键字为x；
可以实现删除根结点、叶子结点以及其它任意结点的功能；
}
4）插入模块
void InsertBST1(BiTree &T,BiTNode *s)
{
在二叉树排序树T中，插入一个结点s(递归算法)；
被CreatBST函数调用；
}
5）查找模块
BiTree searchBST1(BiTree T,TElemType key)
{
在根指针T所指二叉排序树中递归查找关键字等于 key 的数据元素；
若成功，返回指向该数据元素结点的指针；
否则返回空指针；
}

2.源程序代码：
#include<iostream.>
using namespace std;
typedef int KeyType;
typedef struct tree//声明树的结构
{
struct tree *left; //存放左子树的指针
struct tree *right; //存放又子树的指针
KeyType key; //存放节点的内容
} BSTNode, * BSTree; //声明二叉树的链表

BSTree insertBST(BSTree tptr,KeyType key)// 在二叉排序树中插入结点
{ //若二叉排序树tptr中没有关键字为key的结点，则插入，否则直接返回
BSTree f,p=tptr; //p的初值指向根结点
while(p) //查找插入位置，循环结束时，p是空指针，f指向待插入结点的双亲
{
if(p->key==key) //树中已有key，无须插入
return tptr;
f=p; //f保存当前查找的结点，即f是p的双亲
p=(key<p->key)?p->left:p->right;
}
p=(BSTree )malloc(sizeof(BSTNode)); //生成新结点
p->key=key; p->left=p->right=NULL;
if(tptr==NULL) //原树为空，新插入的结点为新的根
tptr=p;
else
if(key<f->key)
f->left=p;
else
f->right=p;
return tptr;
}

BSTree createBST()//建立二叉树
{
BSTree t=NULL; //根结点
KeyType key;
cin>>key;
while(key!=-1)
{
t=insertBST(t,key);
cin>>key;
}
return t;
}
void inorder_btree(BSTree root)// 中序遍历打印二叉排序树
{
BSTree p=root;
if(p!=NULL){
inorder_btree(p->left );
cout<<" "<<p->key<<" ";
inorder_btree(p->right );
}
}
int searchBST(BSTree t,KeyType key)//查找
{
if(key==t->key)
return 1;
if(t==NULL)
return 0;
if(key<t->key)
return searchBST(t->left,key);
else
return searchBST(t->right,key);
}
BSTree deleteBST(BSTree tptr,KeyType key)//删除
{
BSTree p,tmp,parent=NULL;
p=tptr;
while(p)
{
if(p->key==key)
break;
parent=p;
p=(key<p->key)?p->left:p->right;
}
if(!p) return NULL;
tmp=p;
if(!p->right&&!p->left) /*p的左右子树都为空*/
{
if(!parent) //要删根，须修改根指针
tptr=NULL;
else if(p==parent->right)
parent->right=NULL;
else
parent->left=NULL;
free(p);
}
else if(!p->right) //p的右子树为空，则重接p的左子树
{
p=p->left;
if(!parent) //要删根，须修改根指针
tptr=p;
else if(tmp==parent->left)
parent->left=p;
else
parent->right=p;
free(tmp);
}
else if(!p->left) //的左子树为空，则重接p的左子树
{
p=p->right;
if(!parent) //要删根，须修改根指针
tptr=p;
else if(tmp==parent->left)
parent->left=p;
else
parent->right=p;
free(tmp);
}
else if(p->right&&p->left) //p有左子树和右子树，用p的后继覆盖p然后删去后继
{ //另有方法：用p的前驱覆盖p然后删去前驱||合并p的左右子树
parent=p; //由于用覆盖法删根，则不必特殊考虑删根
p=p->right;
while(p->left)
{
parent=p;
p=p->left;
}
tmp->key=p->key;
if(p==parent->left)
parent->left=NULL;
else
parent->right=NULL;
free(p);
}
return tptr;
}
int main()
{
KeyType key;
int flag,test;
char cmd;
BSTree root;
do
{
cout<<"\n\n"<<endl;
cout<<"\t\t*******请选择你要执行的操作:********"<<endl;
cout<<"\n"<<endl;
cout<<"\t\t C.创建一棵二叉排序树\n";
cout<<"\t\t E.结束本程序\n";
cout<<"\n\n\t\t************************************"<<endl;
flag=0;
do
{
if(flag!=0)
cout<<"选择操作错误！请重新选择！\n";
fflush(stdin);
cin>>cmd;
flag++;
}while(cmd!='c'&&cmd!='C'&&cmd!='a'&&cmd!='A');
if(cmd=='c'||cmd=='C')
{
cout<<"请输入你所要创建的二叉树的结点的值，以-1结束：\n";
root=createBST();
do
{
flag=0;
cout<<"\n\n中序遍历二叉树："<<endl;
inorder_btree(root);
cout<<"\n"<<endl;
cout<<"\t\t************请选择你要对这棵二叉树所做的操作:**************"<<endl;
cout<<"\t\t** **"<<endl;
cout<<"\t\t** S......查找你想要寻找的结点 **"<<endl;
cout<<"\t\t** I......插入你想要插入的结点 **"<<endl;
cout<<"\t\t** D......删除你想要删除的结点 **"<<endl;
cout<<"\t\t** Q......结束对这棵二叉树的操作 **"<<endl;
cout<<"\t\t** **"<<endl;
cout<<"\t\t***********************************************************"<<endl;
do{
if(flag!=0)
cout<<"选择操作错误！请重新选择！\n";
fflush(stdin);
scanf("%c",&cmd);
flag++;
}while(cmd!='s'&&cmd!='S'&&cmd!='i'&&cmd!='I'&&cmd!='d'&&cmd!='D'&&cmd!='q'&&cmd!='Q');
switch(cmd)
{

case 's':
case 'S':
cout<<"请输入你要查找结点的关键字：\n";
cin>>key;
test=searchBST(root,key);
if(test==0)
cout<<"\n对不起，你所查找的结点 "<<key<<"不存在!";
else
cout<<"\n成功找到结点\n"<<key<<" ";
break;
case 'i':
case 'I':
cout<<"请输入你要插入结点的关键字：\n";
cin>>key;
root=insertBST(root,key); //注意必须将值传回根
break;
case 'd':
case 'D':
cout<<"请输入你要删除结点的关键字：\n";
cin>>key;
root=deleteBST(root,key); //注意必须将值传回根
if(root==NULL)
cout<<"\n对不起，你所删除的结点 "<<key<<" 不存在!\n";
else
cout<<"\n成功删除结点 "<<key<<" ";
break;
}
}while(cmd!='q'&&cmd!='Q');
}
}while(cmd!='e'&&cmd!='E');
return 0;
}

实 验 内 容
3.测试用例：
1,程序运行时菜单显示如下：

当输入的二叉树序列为：{2,6,9,8,4}时，创建二叉排序树，并输出结果如下：

1.查找9结点时，运行结果如下：

2.删除结点6时运行结果如下：

3.插入结点7时运行结果如下：

实 验 内 容
4.实验总结：
通过这次的实验，我认识到：仅仅掌握课本上的知识是不够的，在实际操作时，常常遇到一些问题，自己看不懂，更无法解决。不过，经过自己不断的思考，尝试着去更改代码中出现的问题。虽然开始很困难，但在老师和同学的帮助下，我逐渐的熟悉了许多操作，为后继工作的顺利进行做了准备。
个人的力量是薄弱的，我学会了咨询别人，不再胆怯，不再保守。 在过程中和同学相互讨论，询问老师，不断进步。
也许，我们可以说，编一个程仅仅是开始，调试和运行相比之下更难。实践中收获的远比想象的多。
看到自己完成了所要求的任务，有一种无法用言语来形容的欣慰之感，这也是无法从学习书本知识中得到的。

13
数据结构上机实验