二叉排序树的应用之——数据结构实验之查找三：树的种类统计

注意：中序遍历二叉树时，只能在树不为空的时候才能进行递归调用！

?

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

Time Limit:?400 ms Memory Limit:?65536 KiB

Submit Statistic

Problem Description

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

Input

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

Output

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

Sample Input

2

This is an Appletree

this is an appletree

Sample Output

this is an appletree 100.00%

Hint

Source

xam

#include

using namespace std;

struct node

{

char name[21];

int dp;

struct node *lchild,*rchild;

}*head;

struct node *buildtree(struct node *head,char w[])

{

if(!head)

{

head = new struct node;

head-> dp = 1;

strcpy(head-> name,w);

head-> lchild = head-> rchild = NULL;

}

else

{

if(strcmp(head-> name,w) > 0)

{

head-> lchild = buildtree(head-> lchild,w);

}

else if(strcmp(head-> name,w) < 0)

{

head-> rchild = buildtree(head-> rchild,w);

}

else

{

head-> dp++;

}

}

return head;

}

void inorder(struct node *head,int n)

{

if(head)

{

inorder(head-> lchild,n);

printf("%s %.2lf%%n",head-> name,(100 * (double) head-> dp) / n);

inorder(head-> rchild,n);

}

}

int main(void)

{

int n,i,j,m;

char w[21];

scanf("%d",&n);

getchar();

head = NULL;

for(j = 0; j < n; j++)

{

gets(w);

m = strlen(w);

for(i = 0; i < m; i++)

{

if(w[i] >= 'A' && w[i] <= 'Z')

{

w[i] += 32;

}

}

head = buildtree(head,w);

}

inorder(head,n);

return 0;

}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!