实验2二叉排序树查找.docx

1、实验2二叉排序树查找1. 建立一棵二叉排序树，存储学生信息，并实现查询功能#include#includeusing 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) if( ) Searc

2、hBST(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); re

3、turn t;void InserBST(BSTree *T,int grade,string name,int no) /此函数用来插入二叉排序树中的结点来建立二叉排序树 BSTNode *p,*q; if( (*T) =NULL) (*T)= ; /补充语句，创建一个新结点 (*T)-grade= ;(*T)-name= ;(*T)- = ; /以上三条语句补充完整，创建学号，姓名，成绩构成的学生信息 (*T)-lchild=(*T)-rchild= ; /补充语句，将被插入的新结点设置成叶结点标志 else p=(*T); while(p) q=p; if( ) /补充判断条件，若gra

4、de成绩值小于当前结点，向左子树前进搜索 p=q-lchild; else if( ) /补充判断条件，若grade成绩值大于当前结点，向右子树前进搜索 ; p=new BSTNode; p-grade=grade; p-name=name; p-no=no; p-lchild=p-rchild=NULL; if(q-gradegrade) q-lchild=p; else q-rchild=p; BSTree CreateBST(void) BSTree T=NULL; int grade,no; string name; cinno; cinname; cingrade; b=a=grad

5、e; while(grade) ; /补充语句，调用InserBST函数向二叉排序树插入结点 cinno; cin ; /补充语句 cin ; /补充语句 return T;void ListBinTree(BSTree T)/此函数用于按顺序输出二叉排序树（以中序遍历方式输出即可得到有序） if(T-lchild!=NULL) ; /补充语句，递归遍历左子树 coutno name gradeendl; /输出根（双亲）结点/补充一组语句，向右子树递归遍历void main() BSTree T; BSTNode *p; int no; cout请输入学生信息（输入0为结束标志）:n; co

6、ut学号 姓名 成绩n; T= ; /补充语句调用建立二叉排序函数 cout按成绩构建二叉排序树，存储学生数据成功！nn; cout 52 n; cout / n; cout 26 66 n; cout / n; cout 12 45 99 n; cout / / n; cout 33 50 89 n; cout / n; cout 87 n; coutn按成绩由低到高排序:; coutn 学号 姓名 成绩 n; ; /补充语句调用排序函数 printf(n); coutno; p= (T,no); /补充语句调用查询函数 if(p=NULL) cout没有找到” no”! n; else c

7、outn 学号 姓名 成绩n; coutno name gradeendl; #include#includeusing 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) if(T-lchi

8、ld!=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; SearchB

9、ST(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

10、 p=(*T); while(p) q=p; if(p-gradegrade) /补充判断条件，若grade成绩值小于当前结点，向左子树前进搜索 p=q-lchild; else if(p-graderchild;/补充判断条件，若grade成绩值大于当前结点，向右子树前进搜索 p=new BSTNode; p-grade=grade; p-name=name; p-no=no; p-lchild=p-rchild=NULL; if(q-gradegrade) q-lchild=p; else q-rchild=p; BSTree CreateBST(void) BSTree T=NULL;

11、int grade,no; string name; cinno; cinname; cingrade; b=a=grade; while(grade) InserBST(&T,grade,name,no); /补充语句，调用InserBST函数向二叉排序树插入结点 cinno; cinname; /补充语句 cingrade; /补充语句 return T;void ListBinTree(BSTree T)/此函数用于按顺序输出二叉排序树（以中序遍历方式输出即可得到有序） if(T-lchild!=NULL) ListBinTree(T-lchild); /补充语句，递归遍历左子树 cou

12、tno name graderchild!=NULL&T-grade!=a&T-rchild-lchild=NULL) coutrchild-no rchild-name rchild-graderchild!=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请输入学生信息（输入0为结束

13、标志）:n; cout学号 姓名 成绩n; T=CreateBST(); /补充语句调用建立二叉排序函数 cout按成绩构建二叉排序树，存储学生数据成功！nn; cout 52 n; cout / n; cout 26 66 n; cout / n; cout 12 45 99 n; cout / / n; cout 33 50 89 n; cout / n; cout 87 n; coutn按成绩由低到高排序:; coutn 学号 姓名 成绩 n; ListBinTree; /补充语句调用排序函数 printf(n); coutno; p=SearchBST(T,no); /补充语句调用查询函数 if(p=NULL) cout没有找到 no! n; else coutn 学号 姓名 成绩n; coutno name gradeendl;