二叉树之树的种类统计

绝地灬酷狼 2022-07-19 11:53 196阅读 0赞

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

####  ####

#### Time Limit: 400MS Memory limit: 65536K ####

## 题目描述 ##

随着卫星成像技术的应用，自然资源研究机构可以识别每一个棵树的种类。请编写程序帮助研究人员统计每种树的数量，计算每种树占总数的百分比。

## 输入 ##

输入一组测试数据。数据的第1行给出一个正整数N (n <= 100000)，N表示树的数量；随后N行，每行给出卫星观测到的一棵树的种类名称，树的名称是一个不超过20个字符的字符串，字符串由英文字母和空格组成，不区分大小写。

## 输出 ##

按字典序输出各种树的种类名称和它占的百分比，中间以空格间隔，小数点后保留两位小数。

## 示例输入 ##

2
    This is an Appletree
    this is an appletree

## 示例输出 ##

this is an appletree 100.00%

## 提示 ##

这个题目主要方法是建立二叉排序树，与之前不同的是，节点中保存的是字符串而非单个字符，然后按照字典序一边比较一边创建树！最后输出时要注意百分号的控制，注意在主函数中输入的N是变的，要另设一变量保存！

## `#include<stdio.h> #include<string.h> #include<stdlib.h> int n; double x; struct node { char data[22]; struct node *lc,*rc; int count; }; //边建树边比较 struct node *CAC(struct node *root,char *e) { if(root==NULL) { root=(struct node *)malloc(sizeof(struct node)); root->count=1; strcpy(root->data,e); root->lc=NULL; root->rc=NULL; } else { int cmp=strcmp(root->data,e); if(cmp>0) { root->lc=CAC(root->lc,e); } else if(cmp<0) { root->rc=CAC(root->rc,e); } else { root->count++; } } return root; }; //中序遍历输出百分比 void mid(struct node *root) { if(root) { mid(root->lc); printf("%s %.2lf%%\n",root->data,(root->count)/(x)*100);//注意整形和浮点型的转化 mid(root->rc); } } int main() { char e[25]; scanf("%d",&n); x=n;//保存变量 struct node *root; root=NULL; getchar();//接受回车键 while(n--) { gets(e); for(int j=0;e[j]!='\0'; j++)//大小写转换 { if(e[j]>='A'&&e[j] <= 'Z') {e[j]+= 32;} } root=CAC(root,e); } mid(root); return 0; }`         ##