实验2二叉排序树查找.docx
《实验2二叉排序树查找.docx》由会员分享，可在线阅读，更多相关《实验2二叉排序树查找.docx（11页珍藏版）》请在冰点文库上搜索。
实验2二叉排序树查找
1.建立一棵二叉排序树，存储学生信息，并实现查询功能
#include
#include
usingnamespacestd;
staticinta,b;
typedefstructnode
{
intgrade;
stringname;
intno;
structnode*lchild,*rchild;
}BSTNode;//代表二叉排序树的结点定义
typedefBSTNode*BSTree;//定义二叉排序树
staticBSTNode*t;//定义一个临时结点
BSTNode*SearchBST（BSTreeT,intno）
{
if（）
SearchBST（T->lchild,）;//补充语句，根据学号向左子树搜索
if（T->==）//补充语句，学号相等，查询成功，获得当前的T结点
t=T;
if（T->rchild!
=NULL&&T->grade!
=a&&T->rchild==NULL&&T->rchild->no==no）
t=T->rchild;
if（T->rchild!
=NULL&&T->rchild->lchild!
=NULL）
SearchBST（T->rchild,）;//补充语句，根据学号向右子树搜索
if（T->rchild!
=NULL&&T->grade==b）
{
a=T->rchild->grade;
SearchBST（T->rchild,no）;
}
returnt;
}
voidInserBST（BSTree*T,intgrade,stringname,intno）
{//此函数用来插入二叉排序树中的结点来建立二叉排序树
BSTNode*p,*q;
if（（*T）==NULL）
{
（*T）=;//补充语句，创建一个新结点
（*T）->grade=;
（*T）->name=;
（*T）->=;//以上三条语句补充完整，创建学号，姓名，成绩构成的学生信息
（*T）->lchild=（*T）->rchild=;//补充语句，将被插入的新结点设置成叶结点标志
}
else
{
p=（*T）;
while（p）
{
q=p;
if（）//补充判断条件，若grade成绩值小于当前结点，向左子树前进搜索
p=q->lchild;
elseif（）//补充判断条件，若grade成绩值大于当前结点，向右子树前进搜索
;
}
p=newBSTNode;
p->grade=grade;
p->name=name;
p->no=no;
p->lchild=p->rchild=NULL;
if（q->grade>grade）
q->lchild=p;
else
q->rchild=p;
}
}
BSTreeCreateBST（void）
{
BSTreeT=NULL;
intgrade,no;
stringname;
cin>>no;
cin>>name;
cin>>grade;
b=a=grade;
while（grade）
{
;//补充语句，调用InserBST函数向二叉排序树插入结点
cin>>no;
cin>>;//补充语句
cin>>;//补充语句
}
returnT;
}
voidListBinTree（BSTreeT）
{//此函数用于按顺序输出二叉排序树（以中序遍历方式输出即可得到有序）
if（T->lchild!
=NULL）
;//补充语句，递归遍历左子树
cout<no<<""<name<<""<grade<//补充一组语句，向右子树递归遍历
}
voidmain（）
{
BSTreeT;
BSTNode*p;
intno;
cout<<"请输入学生信息（输入0为结束标志）:
\n";
cout<<"学号姓名成绩\n";
T=;//补充语句调用建立二叉排序函数
cout<<"按成绩构建二叉排序树，存储学生数据成功！
\n\n";
cout<<"52\n";
cout<<"/\\\n";
cout<<"2666\n";
cout<<"/\\\\\n";
cout<<"124599\n";
cout<<"/\\/\n";
cout<<"335089\n";
cout<<"/\n";
cout<<"87\n";
cout<<"\n按成绩由低到高排序:
";
cout<<"\n学号姓名成绩\n";
;//补充语句调用排序函数
printf（"\n"）;
cout<<"请输入所要查询学生的学号:
";
cin>>no;
p=（T,no）;//补充语句调用查询函数
if（p==NULL）
cout<<"没有找到”<\n";
else
{
cout<<"\n学号姓名成绩\n";
cout<no<<""<name<<""<grade<}
}
#include
#include
usingnamespacestd;
staticinta,b;
typedefstructnode
{
intgrade;
stringname;
intno;
structnode*lchild,*rchild;
}BSTNode;//代表二叉排序树的结点定义
typedefBSTNode*BSTree;//定义二叉排序树
staticBSTNode*t;//定义一个临时结点
BSTNode*SearchBST（BSTreeT,intno）
{
if（T->lchild!
=NULL）
SearchBST（T->lchild,no）;//补充语句，根据学号向左子树搜索
if（T->no==no）//补充语句，学号相等，查询成功，获得当前的T结点
t=T;
if（T->rchild!
=NULL&&T->grade!
=a&&T->rchild==NULL&&T->rchild->no==no）
t=T->rchild;
if（T->rchild!
=NULL&&T->rchild->lchild!
=NULL）
SearchBST（T->rchild,no）;//补充语句，根据学号向右子树搜索
if（T->rchild!
=NULL&&T->grade==b）
{
a=T->rchild->grade;
SearchBST（T->rchild,no）;
}
returnt;
}
voidInserBST（BSTree*T,intgrade,stringname,intno）
{//此函数用来插入二叉排序树中的结点来建立二叉排序树
BSTNode*p,*q;
if（（*T）==NULL）
{
（*T）=newBSTNode;//补充语句，创建一个新结点
（*T）->grade=grade;
（*T）->name=name;
（*T）->no=no;//以上三条语句补充完整，创建学号，姓名，成绩构成的学生信息
（*T）->lchild=（*T）->rchild=NULL;//补充语句，将被插入的新结点设置成叶结点标志
}
else
{
p=（*T）;
while（p）
{
q=p;
if（p->grade>grade）//补充判断条件，若grade成绩值小于当前结点，向左子树前进搜索
p=q->lchild;
elseif（p->gradep=q->rchild;//补充判断条件，若grade成绩值大于当前结点，向右子树前进搜索
}
p=newBSTNode;
p->grade=grade;
p->name=name;
p->no=no;
p->lchild=p->rchild=NULL;
if（q->grade>grade）
q->lchild=p;
else
q->rchild=p;
}
}
BSTreeCreateBST（void）
{
BSTreeT=NULL;
intgrade,no;
stringname;
cin>>no;
cin>>name;
cin>>grade;
b=a=grade;
while（grade）
{InserBST（&T,grade,name,no）;
//补充语句，调用InserBST函数向二叉排序树插入结点
cin>>no;
cin>>name;//补充语句
cin>>grade;//补充语句
}
returnT;
}
voidListBinTree（BSTreeT）
{//此函数用于按顺序输出二叉排序树（以中序遍历方式输出即可得到有序）
if（T->lchild!
=NULL）
ListBinTree（T->lchild）;//补充语句，递归遍历左子树
cout<no<<""<name<<""<grade<//输出根（双亲）结点
if（T->rchild!
=NULL&&T->grade!
=a&&T->rchild->lchild==NULL）
cout<rchild->no<<""<rchild->name<<""<rchild->grade<if（T->rchild!
=NULL&&T->rchild->lchild==NULL）
ListBinTree（T->rchild）;
if（T->rchild!
=NULL&&T->grade==b）
{
a=T->rchild->grade;
ListBinTree（T->rchild）;//补充一组语句，向右子树递归遍历
}
}
voidmain（）
{
BSTreeT;
BSTNode*p;
intno;
cout<<"请输入学生信息（输入0为结束标志）:
\n";
cout<<"学号姓名成绩\n";
T=CreateBST（）;//补充语句调用建立二叉排序函数
cout<<"按成绩构建二叉排序树，存储学生数据成功！
\n\n";
cout<<"52\n";
cout<<"/\\\n";
cout<<"2666\n";
cout<<"/\\\\\n";
cout<<"124599\n";
cout<<"/\\/\n";
cout<<"335089\n";
cout<<"/\n";
cout<<"87\n";
cout<<"\n按成绩由低到高排序:
";
cout<<"\n学号姓名成绩\n";
ListBinTree;//补充语句调用排序函数
printf（"\n"）;
cout<<"请输入所要查询学生的学号:
";
cin>>no;
p=SearchBST（T,no）;//补充语句调用查询函数
if（p==NULL）
cout<<"没有找到"<\n";
else
{
cout<<"\n学号姓名成绩\n";
cout<no<<""<name<<""<grade<}
}
升级会员 