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

刚AC的新鲜代码，马上给安排过来
用的还是***二叉排序树***的知识，只不过比较的对象由数字变成了字符串，而每个节点有多加了一个记录对象也就是每一种树的数量data

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

typedef struct note{
    char s[55];
    int data;//树的数量
    struct note *l,*r;
}tree;

void creat(tree *&root,char *s){
    if(root==NULL){//当为NULL时，建立新tree
        root = new tree;
        strcpy(root->s,s);//字符串的copy函数
        root->data = 1;//此时此种树的数量为1
        root->l = NULL;
        root->r = NULL;
        return ;
    }
    else{
        if(strcmp(s,root->s)<0)//三种比较，如果相等的话，当前树的种类++
            creat(root->l,s);
        else if(strcmp(s,root->s)==0)
            root->data++;
        else
            creat(root->r,s);
    }
}

void zhongxu(tree *root,int n){//按照字典序输出，用到中序遍历
    if(root){
        zhongxu(root->l,n);//首先左
        double x = 100.0*root->data/n;//首先算出比例，然后输出当前的树的名字，然后按格式输出即可
        cout<<root->s<<" ";
        printf("%.2lf",x);
        printf("%c\n",'%');
        zhongxu(root->r,n);//莫忘右
    }
}

int main()
{
    int n;
    tree *root = NULL;
    cin>>n;
    getchar();
    for(int j=0; j<n; j++){
        char s[1010];
        gets(s);
        int len = strlen(s);
        for(int i=0; i<len; i++){
            if(s[i]<=90 && s[i]>=65){//如果是大写编程小写，也可用函数tolower
                s[i]=s[i]+32;
            }
        }
        creat(root,s);
    }
    zhongxu(root,n);
    return 0;
}