原题链接: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表示NULL
int curr_size=0;//当前树中结点的个数
int num_trees=0;//树的数目
//树节点的定义,下标从1开始,0表示NULL
char 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;
}
分享到:
相关推荐
二叉排序树的c语言实现,创建、插入、删除、查找……
pku acm 2418 Hardwood Species代码,使用二叉查找数(BST),有详细的注释 解题报告请访问:http://blog.csdn.net/china8848
pku acm 2503 Babelfish代码 二叉查找树
pku acm 2371 Questions and answers代码 采用二叉查找树排序,解题报告请访问:http://blog.csdn.net/china8848
pku acm 2075 Tangled in Cables 代码 二叉查找树 prim算法,//解题报告请访问:http://blog.csdn.net/china8848
題目: http://acm.pku.edu.cn/JudgeOnline/problem?id=2418
PKU中一些数据结构基本算法题的java实现,包括DIJ、PRIM、二叉查找树、并查集、动态规划、KMP、匈牙利算法、深搜广搜等
pku部分题代码,不多,试一下怎么上传文件!
二叉查找树 线段树 RMQ LCA+RMQ SB-Tree 数论 生成紧凑素数表 分解质因子 最大公约数 a^b mod n 扩张欧几里德算法 素数表质因子分解 Stirling公式 中国剩余定理 欧拉数(递推法) 欧拉数(公式法) 十...
pku1000 pku1000程序 解题报告
pku经典题目解题报告 pku经典题目解题报告
PKU JudgeOnline FAQ 中文版 常见问题解答
benchmark (PKU-MMD) for continuous multi-modality 3D human action understanding and cover a wide range of complex human activities with well annotated information. PKU-MMD contains 1076 long video ...
pku1664源代码
pku acm 1002 487-3279代码 二叉查找数实现 解题报告请访问:http://blog.csdn.net/china8848
ppt word PKU 课件 五星级灰常强大
8数码代码pku1077,300ms(哈希+广度搜索)
我写的解题报告,关于度限制生成树的 网址:http://acm.pku.edu.cn/JudgeOnline/problem?id=1639<br>题目:Picnic Planning 来源:East Central North America 2000
ACM代码 北大pku。 搞ACM的可以参考一下。代码还是挺规范的。有接近150道题目的代码。
PKU 2339 Rock, Scissors, Paper 源代码