二叉排序树求解pku2418

superwind

原题链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=2418
解法：二叉排序树存储每一个树种，然后中序遍历输出结果即可
代码(c语言):
#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAXSIZE 10001//二叉查找树，中序输出int root=0;//根索引，0表示NULLint curr_size=0;//当前树中结点的个数int num_trees=0;//树的数目//树节点的定义，下标从1开始，0表示NULLchar key[MAXSIZE][31];int value[MAXSIZE];int left_child[MAXSIZE];int right_child[MAXSIZE];//查找二叉排序树，如果树为空,返回0，号码已经存在（计数器加1），返回-1,否则返回最后查找的位置int search(int node, char* k){    int parent=0;    int current=node;    while(current!=0)    {        parent=current;        int tmp = strcmp(key[current],k);        if(tmp == 0)        {            value[current]++;            return -1;        }else if(tmp<0)        {            current = right_child[current];        }else        {            current = left_child[current];        }    }    return parent;}//插入新节点int insert(int node,char* k){    //判断一下插在左子树，还是右子树    int tmp = strcmp(key[node],k);    if(tmp==0)        return 0;    int new_node = ++curr_size;//分配新位置    strcpy(key[new_node],k);    value[new_node]=1;    left_child[new_node]=0;    right_child[new_node]=0;    if(new_node==1)//树为空        root = 1;    if(tmp>0)        left_child[node] = new_node;    else        right_child[node] = new_node;    return 1;}void build_tree(){    //freopen("in.txt","r",stdin);    char buf[31];    while(gets(buf))    {        num_trees++;        int index = search(root,buf);        if(index>=0)        {            insert(index,buf);        }    }}//中序遍历void inorder_tree(int root){    if(!root)        return ;    inorder_tree(left_child[root]);    printf("%s %.4f\n",key[root] ,value[root]*100.0/num_trees);    inorder_tree(right_child[root]);}int main(){    build_tree();    inorder_tree(root);    return 0;}