二叉树排序树的操作

桃扇骨 2022-05-20 00:38 230阅读 0赞

/************************************************* 五、查找、排序、文件 1、【二叉排序树与文件操作】 功能要求： （1）从键盘输入一组学生记录建立二叉排序树； （2）二叉排序树存盘； （3）由文件恢复内存的二叉排序树； （4）中序遍历二叉排序树； （5）求二叉排序树深度； （6）求二叉排序树的所有节点数和叶子节点数； （7）向二叉排序树插入一条学生记录； （8）从二叉排序树中删除一条学生记录； （9）从二叉排序树中查询一条学生记录； （10）以广义表的形式输出二叉排序树 等功能。 //定义学生记录类型 Struct student { Char num[6];//学号 Int grade;//成绩 }; //定义二叉排序树节点值的类型为学生记录类型 typedef student ElemType; //定义二叉排序树的节点类型 typedef Struct BSTNode { ElemType data; Struct BSTNode *left; Struct BSTNode *rchild; } BSTNode; *************************************************/
    #include <iostream>
    #include <string>
    #include <string.h>
    #include <queue>
    #include <deque>
    #include <stack>
    #include <stdlib.h>
    using namespace std;
    struct  student
    {
        int    num;//学号
        int    grade;//成绩
    }stu[20];
    
    typedef  struct BSTNode
    {
        student  data;
        BSTNode  *lchild;
        BSTNode  *rchild;
        int pos;
    } BSTNode,*Node;
    student s[100];
    int BSTInsert(Node &t,student key)
    {
        if(t)
        {
            if(key.grade == t->data.grade)
                return 0;
            else if(key.grade < t->data.grade)
                return BSTInsert(t->lchild,key);
            else
                return BSTInsert(t->rchild,key);
        }
        else
        {
            t = new BSTNode();
            t->lchild = t->rchild = NULL;
            t->data = key;
            return 1;
        }
        return 0;
    }
    
    void CreateBST(Node &t,student key[],int n)
    {
        t = NULL;
        for(int i=0;i<n;i++)
            BSTInsert(t,key[i]);
    }
    
    void preorder(Node bt)
    {
        if(bt)
        {
            cout<<"学号:"<<bt->data.num<<" 成绩："<<bt->data.grade<<endl;
            preorder(bt->lchild);
            preorder(bt->rchild);
        }
    }
    void inorder(Node bt)
    {
        if(bt)
        {
            inorder(bt->lchild);
            cout<<"学号:"<<bt->data.num<<" 成绩："<<bt->data.grade<<endl;
            inorder(bt->rchild);
        }
    }
    void disorder(Node bt)
    {
        if(bt)
        {
            disorder(bt->lchild);
            disorder(bt->rchild);
            cout<<"学号:"<<bt->data.num<<" 成绩："<<bt->data.grade<<endl;
        }
    }
    
    int getHeight(Node bt)
    {
        if(bt)
        {
            int l,r;
            l = getHeight(bt->lchild);
            r = getHeight(bt->rchild);
            return (l>r?l:r)+1;
        }
        return 0;
    }
    
    int CountLeaf(Node bt)
    {
        if(!bt)
            return 0;
        if(!bt->lchild && !bt->rchild)
            return 1;
        return CountLeaf(bt->lchild)+CountLeaf(bt->rchild);
    }
    
    int CountNode(Node bt)
    {
        if(!bt)
            return 0;
        else
            return 1+CountNode(bt->lchild)+CountNode(bt->rchild);
    }
    
    int flag;
    void Search(Node bt,int number)
    {
        if(!bt)
        {
            //puts("没有此人。");
            return ;
        }
        else
        {
            if(bt->data.num == number)
            {
                cout<<number<<"的成绩为"<<bt->data.grade<<endl;
                flag = 1;
                return ;
            }
            Search(bt->lchild,number);
            Search(bt->rchild,number);
        }
    }
    
    int Delete(Node &p)
    {
        Node q,s;
        if(!p->lchild && !p->rchild)//左右都空
        {
            p = NULL;
            return 1;
        }
        else if(!p->lchild)//左子树空，重接右子树
        {
            q = p;
            p = p->rchild;
            delete q;
        }
        else if(!p->rchild)//右空
        {
            q = p;
            p = p->lchild;
            delete q;
        }
        else//左右都不空
        {
            q = p;
            s = p->lchild;
            while(s->rchild)
            {
                q = s;
                s = s->rchild;
            }
            p->data = s->data;
            /* if(p!=q)//判断是否执行while q->rchild = s->lchild;//执行，重接右子树 else//否则，重接左子树 q->lchild = s->lchild; */
            delete s;
        }
        return 1;
    }
    
    int BSTDelete(Node &t,student key)
    {
        if(!t)
            return 0;
        else
        {
            if(key.num == t->data.num)
                Delete(t);
            else
            {
                if(key.grade<t->data.grade)
                    BSTDelete(t->lchild,key);
                else
                    BSTDelete(t->rchild,key);
            }
        }
        return 0;
    }
    
    void get_pos(Node &bt)
    {
        Node p = bt;
        if(p)
        {
            queue<Node>Q;
            Q.push(p);
            p->pos = 1;
            while(!Q.empty())
            {
                p = Q.front();
                Q.pop();
                if(p->lchild)
                {
                    Q.push(p->lchild);
                    p->lchild->pos = 2*p->pos;
                }
                if(p->rchild)
                {
                    Q.push(p->rchild);
                    p->rchild->pos = p->pos;
                }
            }
        }
    }
    
    void get_saved(Node &t)
    {
        Node p = t;
        if(p==NULL) return ;
        else if(p)
        {
            s[p->pos].grade = p->data.grade;
            s[p->pos].num = p->data.num;
            get_saved(p->lchild);
            get_saved(p->rchild);
        }
    }
    
    void check(Node t)
    {
        Node p = t;
        if(p)
        {
            check(p->lchild);
            cout<<"操作的学号："<<p->data.num<<"操作的成绩："<<p->data.grade<<endl;
            check(p->rchild);
        }
    }
    FILE *fp;
    void File_W(Node &t)
    {
        get_pos(t);
        check(t);
        for(int i=0;i<100;i++)
        {
            s[i].grade = s[i].num = 0;
        }
        get_saved(t);
    
        if((fp=fopen("/Users/liyixin/Desktop/LYX_SY5_ErChaShu/a.txt.rtf","ab+"))==NULL)
        {
            cout<<"不能打开文件。"<<endl;
            getchar();
        }
    
        fwrite(s,sizeof(student),100,fp);
        rewind(fp);//将文件中的位置指针重新定位到文件开头
    }
    
    student ss[100];
    void File_R(Node &t)
    {
        fread(ss,sizeof(student),100,fp);
        check(t);
        //for(int i=0;i<100;i++)
        // cout<<s[i].num<<' '<<s[i].grade<<endl;
    }
    
    void Display(Node t)
    {
        if(t)
        {
            cout<<"(";
            Display(t->lchild);
            Display(t->rchild);
            cout<<"学号"<<t->data.num<<",成绩"<<t->data.grade;
            cout<<")";
        }
    }
    
    void error()
    {
        puts("请输入正确的选项.");
    }
    
    int main()
    {
        /* 11 2015135 50 2015136 60 2015246 45 2015223 47 2015109 90 2015177 76 2015001 78 2015009 88 2015006 99 2015000 67 2015005 79 */
    
        cout<<"******************二叉排序树与文件操作***********************"<<endl;
        Node t = NULL;
        while(1)
        {
            puts("1.创建排序二叉树");
            puts("2.先序遍历排序二叉树");
            puts("3.中序遍历排序二叉树");
            puts("4.后序遍历排序二叉树");
            puts("5.查找排序二叉树的深度");
            puts("6.查找排序二叉树的节点个数");
            puts("7.查找排序二叉树的叶子个数");
            puts("8.向排序二叉树中插入一条记录");
            puts("9.向排序二叉树中删除一条记录");
            puts("10.查找二叉排序树的一条记录");
            puts("11.保存排序二叉树");
            puts("12.恢复排序二叉树");
            puts("13.广义表形式输出二叉排序树");
            puts("0.退出");
            puts("请输入您要进行的操作：");
            int  n;
            cin>>n;
            if(n==0)
            {
                break;
            }
            if(n==1)
            {
                cout<<"请输入整数n（代表要排序的学生）"<<endl;
                cin>>n;
                puts("请输入n个学生的学号和成绩");
                for(int i=0;i<n;i++)
                    cin>>stu[i].num>>stu[i].grade;
                CreateBST(t, stu , n);
                continue;
            }
            if(n==2)
            {
                preorder(t);
                continue;
            }
            if(n==3)
            {
                inorder(t);
                continue;
            }
            if(n==4)
            {
                disorder(t);
                continue;
            }
            if(n==5)
            {
                cout<<"树的深度为："<<getHeight(t)<<endl;
                continue;
            }
            if(n==6)
            {
                cout<<"所有节点个数为："<<CountNode(t)<<endl;
                continue;
            }
            if(n==7)
            {
                cout<<"叶子个数为："<<CountLeaf(t)<<endl;
                continue;
            }
            if(n==8)
            {
                puts("请输入要插入学生的学号和成绩：");
                student tmp;
                cin>>tmp.num>>tmp.grade;
                BSTInsert(t,tmp);
                cout<<"插入成功！"<<endl;
                continue;
            }
            if(n==9)
            {
                puts("请输入要删除记录的学号和成绩:");
                student tmp;
                cin>>tmp.num>>tmp.grade;
                BSTDelete(t,tmp);
                cout<<" 删除成功！"<<endl;
                continue;
            }
            if(n==10)
            {
                flag = 0;
                int number;
                cout<<"请输入要查找的学号："<<endl;
                cin>>number;
                Search(t,number);
                if(!flag) cout<<"没有此人，请输入正确的学号。"<<endl;
                continue;
            }
            if(n==11)
            {
                File_W(t);
                continue;
            }
            if(n==12)
            {
                File_R(t);
                continue;
            }
            if(n==13)
            {
                Display(t);
                cout<<endl;
                continue;
            }
            if(n>13)
            {
                error();
                continue;
            }
        }
        return 0;
    }