3375 数据结构实验之查找三：树的种类统计

古城微笑少年丶 2022-07-14 13:42 137阅读 0赞

[数据结构实验之查找三：树的种类统计][Link 1]

#include <bits/stdc++.h>  
    
    using namespace std;  
    
    struct node  
    {  
        char str[22];  
        int cnt;  
        node *l, *r;  
    };  
    int n;  
    node *Inster(node *Head, char *s)  
    {  
        if(!Head)  
        {  
            Head = new node;  
            Head->cnt = 1;  
            strcpy(Head->str, s);  
            Head->l = NULL, Head->r = NULL;  
        }  
        else  
        {  
            int cmp = strcmp(Head->str,s);  
            if(cmp > 0)  
                Head->l = Inster(Head->l, s);  
            else if(cmp < 0)  
                Head->r = Inster(Head->r, s);  
            else  
                Head->cnt++;  
        }  
        return Head;  
    }  
    void Mid(node *Head)  
    {  
        if(Head)  
        {  
            Mid(Head->l);  
            printf("%s %.2lf%c\n",Head->str,Head->cnt*100.0/n,'%');  
            Mid(Head->r);  
        }  
    }  
    
    int main()  
    {  
        node *Head = NULL;  
        char str[22];  
        scanf("%d\n",&n);  
        for(int j=0; j<n; j++)  
        {  
            gets(str);  
            for(int i=0; str[i]; i++)  
            {  
                if(str[i] >= 'A' && str[i] <= 'Z')  
                    str[i] += 32;  
            }  
            Head = Inster(Head,str);  
        }  
        Mid(Head);  
        return 0;  
    }

#include <iostream>  
    #include <cstdio>  
    #include <cstring>  
    #include <algorithm>  
    using namespace std;  
    struct node  
    {  
        char name[31];       //记录关键字字符串  
        node *l,*r;  
        int nheight,cnt;     //nheight是平衡因子，cnt记录该字符串出现的次数  
    };  
    int n;  
    int height(node* p)         
    {  
        if(p==NULL)  
            return -1;  
        return p->nheight;  
    }  
    node* LLRotate(node* p)   //对LL型直接在不平衡结点处进行左旋转  
    {  
        node* p1;  
        p1=p->l;  
        p->l=p1->r;  
        p1->r=p;  
        p->nheight=max(height(p->l),height(p->r))+1;  //结点的位置变了，要更新结点的高度值  
        p1->nheight=max(height(p1->l),p->nheight)+1;  
        return p1;  
    }  
    node* RRRotate(node* p)   //对RR型直接在不平衡结点处进行右旋转  
    {  
        node* p1;  
        p1=p->r;  
        p->r=p1->l;  
        p1->l=p;  
        p->nheight=max(height(p->l),height(p->r))+1;  
        p1->nheight=max(height(p1->r),p->nheight)+1;  
        return p1;  
    }  
    node* LRRotate(node* p)    
    {  
        p->l=RRRotate(p->l);  //先对不平衡结点p的左儿子进行右旋转  
        return LLRotate(p);   //再对不平衡结点处进行左旋转并返回新的根  
    }  
    node* RLRotate(node* p)  
    {  
        p->r=LLRotate(p->r);  //先对不平衡结点p的右儿子进行左旋转  
        return RRRotate(p);   //再对不平衡结点处进行右旋转并返回新的根  
    }  
    node* _Insert(char *s,node* p)  
    {  
        if(p==NULL)  
        {  
            p=new node;  
            strcpy(p->name,s);     //字符串复制给心开辟的结点  
            p->nheight=0;  
            p->l=p->r=NULL;  
            p->cnt=1;  
        }  
        else if(strcmp(p->name,s)==0)  
            p->cnt++;  
        else if(strcmp(s,p->name)<0)   //插入到左子树  
        {  
            p->l=_Insert(s,p->l);  
            if(height(p->l)-height(p->r)==2)  //AVL树不平衡  
            {      
                if(strcmp(s,p->l->name)<0)  //插入到左子树左边，做单旋转  
                    p=LLRotate(p);  
                else                        //插入到左子树右边，做双旋转  
                    p=LRRotate(p);  
            }  
        }  
        else if(strcmp(s,p->name)>0)    //插入到右子树  
        {  
            p->r=_Insert(s,p->r);  
            if(height(p->l)-height(p->r)==-2)  //AVL树不平衡  
            {  
                if(strcmp(s,p->r->name)>0)  // 插入到右子树右边，做单旋转  
                    p=RRRotate(p);  
                else                       //插入到右子树左边，做双旋转  
                    p=RLRotate(p);  
            }  
        }  
        p->nheight=max(height(p->l),height(p->r))+1;  
        return p;  
    }  
    void mid_cal(node* p)  
    {  
        if(p!=NULL)        //按照先序遍历模式计算输出就是字典序  
        {  
            mid_cal(p->l);  
            printf("%s %.2f%%\n",p->name,((double)(p->cnt)/(double)n)*100);  //输出字符串和所占百分比  
            mid_cal(p->r);  
        }  
    }  
    int main()  
    {  
    
        node *head=NULL;  
        char s[31];  
        scanf("%d",&n);  
        getchar();  
        for(int k=0;k<n;k++)  
        {  
            gets(s);  
            int len=strlen(s);  
            for(int i=0;i<len;i++)  
            {  
                if(s[i]>='A'&&s[i]<='Z')  
                    s[i]=s[i]-'A'+'a';  
            }  
            head=_Insert(s,head);   //将输入的字符串插入到二叉树中  
        }  
        mid_cal(head);  
        return 0;  
    }

[Link 1]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/1908/pid/3375.html