数据结构课程设计 - (四)二叉排序树(删除，插入，建立，查询)

一时失言乱红尘 2022-12-28 11:29 179阅读 0赞

1、二叉排序树与文件操作  
功能要求：  
（1）从键盘输入一组学生记录建立二叉排序树；  
（2）中序遍历二叉排序树；  
（3）求二叉排序树深度；  
（4）求二叉排序树的所有节点数和叶子节点数；  
（5）向二叉排序树插入一条学生记录；  
（6）从二叉排序树中删除一条学生记录；  
（7）从二叉排序树中查询一条学生记录；  
（8）以广义表的形式输出二叉排序树  
//定义学生记录类型  
Struct student  
\{  
Char num\[6\]; //学号  
Int grade; //成绩  
\};  
//定义二叉排序树节点值的类型为学生记录类型  
typedef student ElemType;  
//定义二叉排序树的节点类型  
typedef Struct BSTNode  
\{  
ElemType data;  
Struct BSTNode \*left;  
Struct BSTNode \*rchild;  
\} BSTNode;

删除特殊情况一：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FieXNzd2F0Y2hlcjE_size_16_color_FFFFFF_t_70]  
特殊情况二：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FieXNzd2F0Y2hlcjE_size_16_color_FFFFFF_t_70 1]

#include <bits/stdc++.h>
    using namespace std;
    typedef struct node1
    {
        
        int grade;//成绩
        char num[10];//学号
    }student;
    typedef struct node2
    {
        
        student data;
        struct node2 *left;
        struct node2 *right;
    }bstnode,*bsttree;
    void insertbst(bsttree &T,student e)
    {
        
        if(T==NULL)
        {
        
            bsttree s=new bstnode;
            s->data=e;
            s->left=s->right=NULL;
            T=s;
        }
        else if(e.grade<T->data.grade)//递归插入其子树
            {
        insertbst(T->left,e);}
        else if(e.grade>T->data.grade)
            {
        insertbst(T->right,e);}
    }
    void createbst(bsttree &T)
    {
        
        T=NULL;
        int n;
        cout<<"输入节点的个数"<<endl;
        cin>>n;
        cout<<"依次输入"<<n<<"个学生的成绩和学号"<<endl;
        while(n--)
        {
        
            student e;
            cin>>e.grade;
            cin>>e.num;
            insertbst(T,e);//调用insert函数
        }
        cout<<"建立完成"<<endl;
    }
    void bianli(bsttree T)
    {
        
        if(T!=NULL)//中序遍历
        {
        
            bianli(T->left);
            cout<<"学号:"<<T->data.num<<"  "<<"成绩:"<<T->data.grade<<endl;
            bianli(T->right);
        }
    }
    int depth(bsttree T)
    {
        
      int leftdepth,rightdepth;
      if(T==NULL)return 0;
      else{
        
        leftdepth=depth(T->left);
        rightdepth=depth(T->right);
        if(leftdepth>rightdepth)return (leftdepth+1);//返回左和右中较大的
        else return(rightdepth+1);
    }
    }
    int countleave(bsttree T)
    {
        
        int num=0;
        if(T==NULL){
        return 0;}
        else if(T->left==NULL&&T->right==NULL){
        return 1;}
        else{
        
            return countleave(T->left)+countleave(T->right);
            }//左子树加右子树
    }
    char* ask(bsttree T,int num)//根据成绩查学号
    {
        
        if(T==NULL||T->data.grade==num)
        {
        
            return T->data.num;
        }
        else if(T->data.grade>num)
        {
        
            return ask(T->left,num);
        }
        else if(T->data.grade<num)
        {
        
            return ask(T->right,num);
        }
    }
    void deletebst(bsttree &T,int key)//删除节点
    {
        
        bsttree p,f,q,s;
        p=T,f=NULL;
        while(p)//通过循环找到要删除的节点。
        {
        
            if(p->data.grade==key)break;
            f=p;//f先指向p的位置
            if(p->data.grade>key)
            {
        
                p=p->left;
            }
            else
            {
        
                p=p->right;
            }
        }
        if(!p)return;
        q=p;
        if((p->left)&&(p->right))//被删的左右都不为空
        {
        
            s=p->left;
            while(s->right)
            {
        
                q=s;
                s=s->right;//左子树中的最右节点（左子树中最大的）
            }//q为s的前驱
            p->data=s->data;
            if(q!=p)q->right=s->left;//对应上图1的情况
            else q->left=s->left;//对应上图2的情况
            delete s;
            return;
        }
        else if(p->right==NULL)//被删的右子树为空
        {
        
            p=p->left;
        }
        else if(p->right==NULL)//被删的左子树为空的情况
        {
        
            p=p->right;
        }
        if(f==NULL)T=p;
        else if(q==f->left) f->left=p;
        else f->right=p;
        delete q;
        cout<<"删除完成"<<endl;
    }
    
    void printbst(bsttree T)//广义表形式输出树
    {
        
    		cout<<T->data.num;
    		if(T->left!=NULL)
            {
        
    			cout<<"(";
    			printbst(T->left);
    			if(T->right==NULL)
    			{
        
    				cout<<")";
    			}
    		}
    		if(T->right!=NULL)
    		{
        
    			if(T->left==NULL)
    			{
        
    				cout<<"(";
                }
    			cout<<",";
    			printbst(T->right);
    			cout<<")";
    		}
    }
    
    void menu()
    {
        
        cout<<"       二叉排序树      "<<endl;
        cout<<"输入数字，执行相应操作"<<endl;
        cout<<endl;
        cout<<"1.建立二叉排序树"<<endl;
        cout<<"2.查看二叉排序树"<<endl;
        cout<<"3.根据成绩查询节点信息"<<endl;
        cout<<"4.删除节点"<<endl;
        cout<<"5.查看叶子节点个数"<<endl;
        cout<<"6.查看树的高度"<<endl;
        cout<<"7.退出程序"<<endl;
    }
    int main()
    {
        
        bsttree T;
        int q=0,flag=1;
        while(flag)
        {
        
            menu();
            cin>>q;
            switch(q)
            {
        
                case(1):createbst(T);break;
                case(2):cout<<"树的广义表形式如下:"<<endl;printbst(T);break;
                case(3):int num;cout<<"输入成绩"<<endl;cin>>num;cout<<"该同学的学号为"<<ask(T,num)<<endl;break;
                case(4):int key;cout<<"输入要删除的学生的成绩"<<endl;cin>>key;deletebst(T,key);break;
                case(5):cout<<"叶子个数为"<<countleave(T)<<endl;break;
                case(6):cout<<"树的高度为"<<depth(T)<<endl;break;
                case(7):flag=0;
            }
            getchar();
            getchar();
            system("cls");
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FieXNzd2F0Y2hlcjE_size_16_color_FFFFFF_t_70]: /images/20221120/b864466e3a784e92b9102ca84211ca3c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FieXNzd2F0Y2hlcjE_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20201218083600295.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FieXNzd2F0Y2hlcjE=,size_16,color_FFFFFF,t_70