攻坚实验四 树种统计（注释）

攻坚实验四 树种统计

一、 实验目的

熟练掌握二叉搜索树的性质及在解决问题中的应用。

二、 实验内容

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

三、 实验要求

1. 输入说明：输入第一行给出一个正整数N(N<=105) ,为树的数量。随后N行，每行给出卫星观测到的一棵树的种类名称。种类名称是不超过30个英文字母和空格组成的字符串(大小写不区分)。

2．输出说明：按字典序递增输出各种树的种类名称及其所占总数的百分比，其间以空格分隔，精确到小数点后4位。 3．测试用例： 序号 输入 1 29 Red Alder Ash Aspen Basswood Ash Beech Yellow Birch Ash Cherry Cottonwood Ash Cypress Red Elm Gum Hackberry White Oak Hickory Pecan Hard Maple White Oak Soft Maple 输出 说明 Ash 13.7931% 一般情况Aspen 3.4483% 测试 Basswood 3.4483% Beech 3.4483% Black Walnut 3.4483% Cherry 3.4483% Cottonwood 3.4483% Cypress 3.4483% Gum 3.4483% Hackberry 3.4483% Hard Maple 3.4483% Hickory 3.4483% Pecan 3.4483% Poplan 3.4483% Red Alder 3.4483% Red Elm 3.4483% Red Oak 6.8966% Sassafras 3.4483% Soft Maple 3.4483% Sycamore 3.4483% White Oak 10.3448% Willow 3.4483% 2 3 4 Red Oak Yellow Birch 3.4483% Red Oak White Oak Poplan Sassafras Sycamore Black Walnut Willow 1 A test for the longest 边界测试：A test for the longest strings strings 100.00% 最小N,最长树种名 100000 百分比全部为0.0010% 边界测试：随机生成不重复的大数据 最大N的树 100000 略 边界测试：随机大数据 最大N 四、 实验分析

（1）问题分析

问题的关键在于需要反复查找某种输入树种并将其个数加1。如果简单的将最多N个宿儒树种存为数组，则每次查找最坏都需要线性时间复杂度O(N),于是总查找时间将达到O(N2)。

二分查找可以达到O(logN)的查找效率，但前提条件是数组里的数据有序。在学习高效排序算法之前，用如冒泡排序之类的简单算法并不是很好的选择，因为时间复杂度可能达到O(N2).

二叉搜索树可以比较有效地提高查找效率。如果树比较平衡，则单次插入和查找都可以达到O(logN)的复杂度，因此总体时间复杂度可能降低到O(NlogN)。当然最坏的情况下，可能形成单边倾斜的二叉搜索树，这时的效率只有O(N2)，与前两种算法持平。

用二叉搜索树的另一个好处是，对其进行中序遍历就可以得到按字典序递增的输出序列。

（2）实现要点

树形结构仍然用一般教材中介绍的链表结构存储，结点结构体除了存储该结点的树种名称及左右子树的指针外，还需要一个计数器来存储树种的数量。

五、 主要仪器及耗材

计算机及VC6软件

六、 实验参考代码

#include #include #include #include #define MAXN 100000 #define MAXS 30 #define NULL 0 typedef struct TreeNode *binTree; struct TreeNode { char Data[MAXS+1]; int cnt; binTree left; binTree right; }; binTree Insert(binTree T,char *Name) { int cmp; if(!T) { T=(binTree)malloc(sizeof(struct TreeNode)); strcpy(T->Data,Name); T-cnt=1; T->left=T->right=NULL; } else { cmp=strcmp(Name,T->Data); if(cmp<0) T->left=Insert(T->left,Name); else if(cmp>0) T->right=Insert(T->right,Name); else T->cnt++; } return T; } void output(binTree T,int N) { if(!T)return;//递归终止条件 output(T->left,N);//输出左子树 printf(\输出根结点的值 output(T->right,N);//输出右子树 } int main() { int N,i; char name[MAXS+1]; binTree T=NULL; scanf(\ for(i=0;i

七、 思考题

(1)在数据规模较大的时候，二叉排序树（搜索树）有时会显著不平衡，为什么会出现这种不平衡？二叉搜索树的不平衡会导致什么问题？

（2）为了应对二叉搜索树的不平衡，研究人员提出了AVL树和红黑树，请阅读相关资料，分析它们分别使用了怎样的平衡策略。