/*
二叉查找樹：對於樹中的每個節點X，它的左子樹中的所有節點的值小於X的值，它的右子樹中的所有節點的值大於X的值；
*/
題目大意：給出一些單詞（包含大小寫和空格），單詞可以重復出現（單詞最多10000種，最多1000000個）。要求按字典序輸出單詞並輸出每個單詞占的比例；
思路：單詞的比較可以用strcmp，由於單詞數較多，直接排序可能超時，若用字典樹的話需要的空間較大。因此可以考慮將單詞作為二叉查找樹的關鍵字建樹，然後按中序遍歷輸出。
[cpp]
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
using namespace std;
struct node
{
char word[33];
int cnt;
node *left,*right;
node(char *n){
strcpy(word,n);
cnt=1;
left=NULL;
right=NULL;
}
}*root;
double count;
//插入二叉查找樹
node* insert(char *word,node *p)
{
if(p==NULL){
p=new node(word);
}
else if(strcmp(word,p->word)<0)
p->left=insert(word,p->left);
else if(strcmp(word,p->word)>0)
p->right=insert(word,p->right);
else
p->cnt++;
return p;
}
//輸出中序遍歷結果
void output(node *p)
{
if(p==NULL)
return;
output(p->left);
printf("%s %.4lf\n",p->word,(p->cnt)/count*100);
output(p->right);
delete p;
}
int main()
{
char word[33];
count=0;
while(gets(word)){
root=insert(word,root);
count++;
}
output(root);
return 0;
}
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
using namespace std;
struct node
{
char word[33];
int cnt;
node *left,*right;
node(char *n){
strcpy(word,n);
cnt=1;
left=NULL;
right=NULL;
}
}*root;
double count;
//插入二叉查找樹
node* insert(char *word,node *p)
{
if(p==NULL){
p=new node(word);
}
else if(strcmp(word,p->word)<0)
p->left=insert(word,p->left);
else if(strcmp(word,p->word)>0)
p->right=insert(word,p->right);
else
p->cnt++;
return p;
}
//輸出中序遍歷結果
void output(node *p)
{
if(p==NULL)
return;
output(p->left);
printf("%s %.4lf\n",p->word,(p->cnt)/count*100);
output(p->right);
delete p;
}
int main()
{
char word[33];
count=0;
while(gets(word)){
root=insert(word,root);
count++;
}
output(root);
return 0;
}
