void BSTree::inst(Sstudent el) {
BTreeNode *p;
p = sear(el.number); if (p != NULL )
cout<<\已找到 \ else {
p=new BTreeNode(el,NULL,NULL); inst(p,root); } }○1
5、删除学生信息 /* 思想：
首先查找该元素所在的节点p,同时记录父节点； 一、若p为空，则发出错误信号； 二、若p不为空：
分三种情况讨论：
若*p结点为叶子结点，即左子树和右子树均为空树。由于删去叶子结点不破坏整棵树的结构，则只需修改其双亲结点的指针即可。
若*p结点只有左子树或右子树，此时只要令左子树或右子树直接成为其双亲结点*f的左子树（当*p是左子树）或右子树（当*p是右子树）即可， 作此修改也不破坏二叉排序树的特性。
若*p结点的左子树和右子树均不空。在删去*p之后，为保持其它元素之间的相对位置不变，可按中序遍历保持有序进行调整，做法：
用p的右子树的最左端的节点tmp的数据域刷新p的数据域，然后递归调用删除tmp. */
BTreeNode * BSTree::deleteNode(BTreeNode *&p, char num[]) {
BTreeNode *pfather=root,*qfather=NULL,*q=NULL;; int k;
//搜索该元素所在的节点,同时记录父节点 while (p != NULL) {
k=strcmp(num,p->data.number); if(k == -1) {
pfather=p; p=p->lchild; }
5
else if(k == 1) {
pfather=p; p=p->rchild; } else
break; }
if (p == NULL ) {
cout<<\找不到该同学信息，删除失败!\ return NULL; }
else if (p->lchild!=NULL && p->rchild!=NULL) //结点左右儿子都存在 {
BTreeNode *tmp = p->rchild; while(tmp->lchild) {
tmp = tmp->lchild; }
p->data = tmp->data;
p->rchild = deleteNode(p->rchild,tmp->data.number); } else
{ //只有一个儿子或没有儿子的情况 if(p->lchild == NULL) {
if(p == pfather->lchild) //p是左子节点 pfather->lchild = p->rchild; else
pfather->rchild = p->rchild; }
else if(p->rchild == NULL) {
if(p == pfather->lchild) //p是左子节点 pfather->lchild = p->lchild; else
pfather->rchild = p->lchild; } }
p->data.output(); return p; }
//实例函数
6
BTreeNode * BSTree::deleteNode(char num[]) {
BTreeNode *p=root;
return deleteNode(p,num); }
6、在屏幕中输出全部学生信息
//采用中序遍历的思想输出节点信息，则在屏幕上根据学生学号的升序输出。 void BTree::prnt(BTreeNode *p) //递归函数 {
if (p!=NULL ) {
prnt(p->lchild); p->data.output(); prnt(p->rchild); } }
//实例函数
void BTree::prnt() {
prnt(root); }
7、用户界面 主函数文件： int main() {
BSTree t; //新建一个二叉树:t
int choice=10; //将choice初始化,使其不为0~4 Sstudent s;
BTreeNode *p=NULL; char num[12]; while(choice) {
cout<<\请输入您要进行的操作：\
cout<<\向学生健康表插入学生信息\
<<\在健康表删除学生信息\
<<\在健康表中查询学生信息（按学生学号来进行查找）\
<<\在屏幕中输出全部学生信息\ <<\退出\
cin>>choice;
7
switch(choice) {
case 1:
s.input(); //输入学生信息 t.inst(s);
break; case 2:
cout<<\请输入要删除学生的学号: \ cin>>num;
p=t.deleteNode(num); if (p!=NULL) {
cout<<\删除成功！删除学生的信息为：\ p->getdata().output(); }
break; case 3:
cout<<\请输入要查询学生的学号: \ cin>>num;
p=t.sear(num); if (p!=NULL)
p->getdata().output(); else
cout<<\找不到该学生信息!\ break; case 4:
t.prnt(); break;
case 0: break;
default: cout<<\输入错误!请重新输入。\ }
cout< return 0; } 【结果及结果分析】 1、插入学生信息： 8 插入后的二叉树为： 9