http://acm.pku.edu.cn/JudgeOnline/problem?id=2418 二叉搜索树的典型题.... 很久没做ACM了,感觉有一个月那么多了吧. 现在来打这些也感觉生疏咯... BST用到这题目很合适,也有人说用qsort可以过,应该是题目时间太宽的缘故. 上代码...BST  #include <stdio.h> #include <string.h> #include <stdlib.h> typedef struct BSTNode { char name[100]; int times; struct BSTNode *lchild,*rchild; }BSTNode,*BSTree; int count; void BSTInsert(BSTree &t,char str[]) { BSTree p,f; p = t; while(p) { if(strcmp(str,p -> name) == 0) { p -> times++; return; } f = p; p = (strcmp(str,p -> name) < 0) ? p -> lchild : p -> rchild; } p = (BSTree) malloc (sizeof(BSTNode)); p -> lchild = p -> rchild = NULL; strcpy(p -> name,str); p -> times = 1; if(t == NULL) t = p; else { ( strcmp(p -> name,f -> name) < 0 ) ? (f -> lchild = p) : (f -> rchild = p); } } void InOrderTravel(BSTree &t) { if(t != NULL) { InOrderTravel(t -> lchild); printf("%s %.4f\n",t -> name,t -> times * 100.0 / count); InOrderTravel(t -> rchild); } } int main() { count = 0; BSTree t = NULL; char str[100]; while(gets(str) != NULL) { BSTInsert(t,str); count++; } InOrderTravel(t); return 0; }

评论