编写程序统计一个英文文本文件中每个单词的出现次数（词频统计），并将统计结果按单词字典序输出到屏幕上。
要求：程序应用二叉排序树（BST）来存储和统计读入的单词。
注：在此单词为仅由字母组成的字符序列。包含大写字母的单词应将大写字母转换为小写字母后统计。在生成二叉排序树不做平衡处理。
【输入形式】
打开当前目录下文件article.txt，从中读取英文单词进行词频统计。
【输出形式】
程序应首先输出二叉排序树中根节点、根节点的右节点及根节点的右节点的右节点上的单词（即root、root->right、root->right->right节点上的单词），单词中间有一个空格分隔，最后一个单词后没有空格，直接为回车（若单词个数不足三个，则按实际数目输出）。
程序将单词统计结果按单词字典序输出到屏幕上，每行输出一个单词及其出现次数，单词和其出现次数间由一个空格分隔，出现次数后无空格，直接为回车。
【样例输入】
当前目录下文件article.txt内容如下：
"Do not take to heart every thing you hear."
"Do not spend all that you have."
"Do not sleep as long as you want;"
【样例输出】
do not take
all 1
as 2
do 3
every 1
have 1
hear 1
heart 1
long 1
not 3
sleep 1
spend 1
take 1
that 1
thing 1
to 1
want 1
you 3
【样例说明】
程序首先在屏幕上输出程序中二叉排序树上根节点、根节点的右子节点及根节点的右子节点的右子节点上的单词，分别为do not take，然后按单词字典序依次输出单词及其出现次数。
二叉树比用数组做词频统计的优势在于，不用事先分配空间，造成浪费或者溢出。以下为带详细注释的源代码:
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<ctype.h> #define M 5000 typedef struct node{ int count; char word[26]; struct node *lchild, *rchild; //建立节点的时候 每个节点有左孩子和右孩子 }BTNode, *BTREE; int times = 0; int get_word(char *temp_word, FILE *in); BTREE insert(BTREE T, char temp_word[]); // remember to return a pointer so it can change its real address void inorder(BTREE root); int main() { char temp_word[26] = {0}; /*prepare to put the content of temp_word to real wordblock.word*/ FILE *in; int i,j; if( (in = fopen("article.txt", "r")) == NULL ) printf("No such file!\n"); BTREE root = NULL; //每次insert 都是把根节点当作参数传进去的 while( !feof(in) ) { char temp_word[26] = {0}; get_word(temp_word,in); root = insert(root, temp_word); } printf("%s ", root->word); if(root->rchild != NULL && root->rchild->rchild == NULL) printf("%s\n", root->rchild->word ); else printf("%s ", root->rchild->word ); if(root->rchild->rchild != NULL) printf("%s\n", root->rchild->rchild->word); inorder(root); /*traverse the tree using inorder way 因为是二叉排序树 所以输出就是按照字典序的*/ return 0; } int get_word(char *temp_word, FILE *in) { int i = 0; char temp = '0'; temp = fgetc(in); while( !isalpha(temp) ) { temp = fgetc(in); if(temp==EOF) return 1; } while(isalpha(temp) && !isspace(temp) ) { temp = tolower(temp); temp_word[i] = temp; i++; temp = fgetc(in); } return 0; } BTREE insert(BTREE p, char temp_word[]) { int cond; if(p == NULL) { p = (BTREE)malloc(sizeof(BTNode)); strcpy(p->word, temp_word); p->count = 1; p->lchild = p->rchild = NULL; } else if( (cond = strcmp(temp_word, p->word)) == 0) { p->count++; } else if( cond<0 ) { p->lchild = insert(p->lchild, temp_word); } else { p->rchild = insert(p->rchild, temp_word); } return (p); } void inorder(BTREE T) /*using inorder*/ { if(T!= NULL) { inorder(T->lchild); if( strlen(T->word) >0 ) printf("%s %d\n", T->word, T->count); inorder(T->rchild); } }