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

1. 建立一棵二叉排序树，存储学生信息，并实现查询功能#includeiostream#includestringusing 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()SearchBST(T-lchild,);//补充语句，根据学号向左子树搜索if(T-==) //补充语句，学号相等，查询成功，获得当前的T结点t=T;if(T-rchild!=NULLT-grade!=aT-rchild==NULLT-rchild-no==no)t=T-rchild;if(T-rchild!=NULLT-rchild-lchild!=NULL)SearchBST(T-rchild,); //补充语句，根据学号向右子树搜索if(T-rchild!=NULLT-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)=;//补充语句，创建一个新结点(*T)-grade=;(*T)-name=;(*T)-=;//以上三条语句补充完整，创建学号，姓名，成绩构成的学生信息(*T)-lchild=(*T)-rchild=;//补充语句，将被插入的新结点设置成叶结点标志}else{p=(*T);while(p){q=p;if()//补充判断条件，若grade成绩值小于当前结点，向左子树前进搜索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;elseq-rchild=p;}}BSTree CreateBST(void){BSTree T=NULL;int grade,no;string name;cinno;cinname;cingrade;b=a=grade;while(grade){;//补充语句，调用InserBST函数向二叉排序树插入结点cinno;cin;//补充语句cin;//补充语句}return T;}void ListBinTree(BSTree T){//此函数用于按顺序输出二叉排序树（以中序遍历方式输出即可得到有序）if(T-lchild!=NULL);//补充语句，递归遍历左子树coutT-no T-name T-gradeendl;//输出根（双亲）结点//补充一组语句，向右子树递归遍历}void main(){BSTree T;BSTNode *p;int no;cout请输入学生信息（输入0为结束标志）:\n;cout学号姓名成绩\n;T=;//补充语句调用建立二叉排序函数cout按成绩构建二叉排序树，存储学生数据成功！\n\n;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;cout\n按成绩由低到高排序:;cout\n 学号姓名成绩 \n;;//补充语句调用排序函数printf(\n);cout请输入所要查询学生的学号:;cinno;p=(T,no);//补充语句调用查询函数if(p==NULL)cout没有找到”no”! \n;else{cout\n 学号姓名成绩\n;coutp-no p-name p-gradeendl;}}#includeiostream#includestringusing namespace std;