二叉排序树的查找 实验2_二叉排序树查找
1. 建立一棵二叉排序树，存储学生信息，并实现查询功能
#include
#include
using namespace std;
static int a,b;
typedef struct node
{
int grade;
string name;
int no;
struct node *lchild,*rchild;
}BSTNode; //代表二叉排序树的结点定义
typedef BSTNode *BSTree; //定义二叉排序树
static BSTNode *t; //定义一个临时结点
BSTNode * SearchBST(BSTree T, int no)
{
)
SearchBST(T->lchild, //补充语句，根据学号向左子树搜索
//补充语句，学号相等，查询成功，获得当前的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) { } return t; a=T->rchild->grade; SearchBST(T->rchild,no);
void InserBST(BSTree *T,int grade,string name,int no)
{ //此函数用来插入二叉排序树中的结点来建立二叉排序树
BSTNode *p,*q;
if( (*T) ==NULL)
{
(*T)= //补充语句，创建一个新结点 ;
;
; //以上三条语句补充完整，创建学号，姓名，成绩构成的学生信息
; //补充语句，将被插入的新结点设置成叶结点标志
}
else
{
p=(*T); while(p) { q=p; //补充判断条件，若grade成绩值小于当前结点，向左子树前进搜索
p=q->lchild; //补充判断条件，若grade成绩值大于当前结点，向右子树前进搜索
}
} p=new BSTNode; 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;
}
BSTree CreateBST(void)
{
BSTree T=NULL;
int grade,no;
string name;
cin>>no;
cin>>name;
cin>>grade;
b=a=grade;
while(grade)
{
; //补充语句，调用
入结点
cin>>no;
; //补充语句
; //补充语句
}
return T;
}
void ListBinTree(BSTree T)
InserBST函数向二叉排序树插
{//此函数用于按顺序输出二叉排序树（以中序遍历方式输出即可得到有序） if(T->lchild!=NULL)
; //补充语句，递归遍历左子树
coutnonamegrade
//补充一组语句，向右子树递归遍历
}
void main()
{
BSTree T;
BSTNode *p;
int no;
cout
cout
T= //补充语句调用建立二叉排序函数
cout
cout
cout
cout
cout
cout
cout
cout
cout
cout
cout
cout
//补充语句调用排序函数
printf("\n");
cout
cin>>no;
//补充语句调用查询函数
if(p==NULL)
cout
else
}
#include
#include
using namespace std;
static int a,b;
typedef struct node
{
int grade;
{ coutnonamegrade
string name;
int no;
struct node *lchild,*rchild;
}BSTNode; //代表二叉排序树的结点定义
typedef BSTNode *BSTree; //定义二叉排序树
static BSTNode *t; //定义一个临时结点
BSTNode * SearchBST(BSTree T, int no)
{
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);
}
return t;
}
void InserBST(BSTree *T,int grade,string name,int no)
{ //此函数用来插入二叉排序树中的结点来建立二叉排序树
BSTNode *p,*q;
if( (*T) ==NULL)
{
(*T)=new BSTNode; //补充语句，创建一个新结点
(*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;
else if(p->grade
p=q->rchild;//补充判断条件，若grade成绩值大于当前结点，向右子树前进搜索
}
p=new BSTNode;
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;
}
}
BSTree CreateBST(void)
{
BSTree T=NULL;
int grade,no;
string name;
cin>>no;
cin>>name;
cin>>grade;
b=a=grade;
while(grade)
{InserBST(&T,grade,name,no);
//补充语句，调用InserBST函数向二叉排序树插入结点
cin>>no;
cin>>name; //补充语句
cin>>grade; //补充语句
}
return T;
}
void ListBinTree(BSTree T)
{//此函数用于按顺序输出二叉排序树（以中序遍历方式输出即可得到有序） if(T->lchild!=NULL)
ListBinTree(T->lchild); //补充语句，递归遍历左子树
coutnonamegrade
//输出根（双亲）结点
if(T->rchild!=NULL&&T->grade!=a&&T->rchild->lchild==NULL)
coutrchild->norchild->namerchild->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);//补充一组语句，向右子树递归遍历
}
}
void main()
{
BSTree T;
BSTNode *p;
int no;
cout
cout
T=CreateBST(); //补充语句调用建立二叉排序函数
cout
cout
cout
cout
cout
cout
cout
cout
cout
cout
cout
cout
ListBinTree; //补充语句调用排序函数
cout>no; p=SearchBST(T,no); //补充语句调用查询函数 if(p==NULL) coutnonamegrade
}