数据结构
百香果的功效与作用及食用方法实验报告
实验题目： 二叉排序树
班 级：
姓 名：
古罗马神话学 号：
完成日期：
一、需求分析(说明实验的任务，包括输入、输出、功能、测试数据等)
输入数据的第一行为一个正整数T, 表示测试数据的组数。然后是T组测试数据。每组测试数据的第一行输入正整数n(5≤n≤20)，第二行输入n个整数，要求依次完成以下工作：
(1) 以这n个整数生成(建立)一棵用链式存储结构存储的二叉排序树；
(2) 按递增顺序输出该二叉排序树中的整数(关键字)；
(3) 输入一个整数key，对该二叉排序树进行查找，若在该二叉排序树中存在这个整数key，则输出find，否则输出not find。
(4) 输入一个整数key，若该二叉排序树中不存在这个整数key启明大学，则将key插入到该二叉排序树中，使插入后仍为原性质的二叉排序树；否则不必插入；
(5) 在莺字组词(4)的基础上，按递减顺序输出该二叉排序树中的整数(关键字)
二、概要设计
1、算法思路
(1) 首先要建立二叉排序树。我们要建立的二叉排序树，其关键字要求是各不相同的，则对于输入的关键字(整数)序列中的每一个整数，要在正在建立的二叉排序树中去查找是否已经存在该整数，不存在时，由查找模块(其算法思路后述)返回要增加(插入)结点位置的双亲结点，根据要建立的二叉排序树的性质(左小右大)，当要增加的整数比双亲结点的整数小的话就插(挂)到其左孩子的位置，否则插(挂)到其右孩子的位置。这样重复，直到输入结束(输入的整数为-1)，这样，二叉排序树就建好了。
(2) 查找算法是从二叉排序树的根结点开始，根据要查找的整数，若比其当前二叉排序树结点中的整数小就进入其左孩子所在的左子树中继续搜索，否则进入其右左孩子所在的右子树中继续搜索，这过程中，每进入子树前，保存当前结点(指针)，以便带回要增加(插入)结点的双亲结点。搜索直至找到要查找的整数，用一指针带回；或搜索直至叶子结点的下方，找不到要查找的整数而使空指针带回，以便判断要查找的整数是否找到。
(3) 按递增顺序输出该二叉排序树中的整数(关键字)，可直接用某种二叉树的遍历算法实现；按递减顺序输出该二叉排序树中的整数(关键字)，只要对某种二叉树的遍历算法稍作修改即可。
(4) 插入算法思路和建立二叉排序树时增加一个整数的思路是一样的。
2、数据结构
typedef struct node // 二叉排序树中的结点结构
{int data; // 整数(关键字)数据域
struct node *lchild,*rchild; // 指向左右孩子的指针
}nodeb,*bitree;
3、基本操作
(1) 查找算法
void archbst(bitree t,bitree *f,bitree *p,int key)
{ // 在二叉排序树t中查找整数为key的结点，若找到，则p指向该结点，否则p为空。f 为
//指向双亲结点的
while(t不空且t中的整数不是要找的整数key)
{ 用f记录当前结点；
if(要找的整数key小于t中的整数)
t进入其左孩子所在的左子树；
el t进入其右孩子所在的右子树；
}
}
(2) 建立二叉排序树算法
bitree createbintree(int n) /* 建立有n个整数的二叉排序树，其二叉排序树t，用函数值返回树根*/
{ 置t为空树；
while(n次)
{ 输入整数；
查找该整数；
if(该整数在当前的二叉排序树中不存在)
{ 我在天上人间的日子申请结点；
对该结点赋以该整数；
该结点的左右指针赋空值；
根据查找的结果，把该结点挂到某结点的左孩子或右孩子位置
// 注意当二叉排序树还是空树时情况的处理
}
}
返回建好的二叉排序树t；
}
(3) 插入(增加)整数算法
孔子舞剧int inrtbst(bitree *t,int key) /* 在二叉排序树t中插入整数key的结点，是否插入成功用函数值返回 */
{ 在二叉排序树t中查找整数key；
if(整数key在二叉排序树t中不存在)
{ 申请结点；
16字口号对该结点赋以该整数；
该结点的左右指针赋空值；
根据查找的结果，把该结点挂到某结点的左孩子或右孩子位置
// 注意当二叉排序树还是空树时情况的处理
}
el 插入不成功；
}
4、主程序
int main()
{
重复m组：
调用createbintree()算法建立二叉排序树t；
调用某种二叉树遍历算法按递增顺序输出该二叉排序树中的整数(关键字)；
输入要查找的整数，调用archbst()算法查找要查找的整数；
根据查找的结果输出相应的信息；
输入要插入的整数，调用inrtbst()算法将整数插入到二叉排序树中；
根据插入的结果输出相应的信息；
调用稍作修改的某种二叉树遍历算法按递减顺序输出该二叉排序树中的整数(关键字)；
}
bitree createbintree(int n)
{
bitree p,q,f,t;
int i,d;
t=NULL;
for(i=0;i<n;i++)
{
p=NULL;
cin>>d;
archbst(t,&f,&p,d);
if(!p)
{
q=new nodeb;
q->data=d;
q->lchild=q->rchild=NULL;
if(f==NULL) t=q;
el if(d<f->data) f->lchild=q;
el f->rchild=q;
}
}
return t;
}
#include<iostream>
using namespace std;
typedef struct node
{int data;
struct node *lchild,*rchild;
}nodeb,*bitree;
void archbst(bitree t,bitree *f,bitree *p,int key)
{
*p=t;*f=NULL;
while(*p!=NULL&&((*p)->data!=key))
{
*f=*p;
if(key<(*p)->data) *p=(*p)->lchild;
el (*p)=(*p)->rchild;
}
}
三、详细设计int main()
{
神医扁鹊 bitree t,p,f;
int d,j,n,key,i;
cin>>d;
for(j=0;j<d;j++)
{
cin>>n;
t=createbintree(n);
i=0;inordertraver(t,&i);printf("\n");
cin>>key;
archbst(t,&f,&p,key);
if(p) printf("find\n");
el printf("not find\n");
cin>>key;
inrtbst(&t,key);
i=0;postordertraver(t,&i);printf("\n");
}
return 1;
}
int inrtbst(bitree *t,int key)
{
bitree p,f,s;
archbst(*t,&f,&p,key);
if(!p)
{
s=new nodeb;
s->data=key;
s->lchild=s->rchild=NULL;
if(!f) *t=s;
el if(key<f->data) f->lchild=s;
el f->rchild=s;
return 1;
}
el return 0;
}
void inordertraver(bitree t,int *i)
{
if(t)
{
inordertraver(t->lchild,i);
(*i)++;
if(*i==1) printf("%d",t->data);
el printf(" %d",t->data);
inordertraver(t->rchild,i);
}
}
void postordertraver(bitree t,int *i)
{
if(t)
{
postordertraver(t->rchild,i);
(*i)++;
if(*i==1) printf("%d",t->data);
el printf(" %d",t->data);
postordertraver(t->lchild,i);
}
}
