二叉排序树求解pku2418
原题链接：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;int value;int left_child;int right_child;//查找二叉排序树，如果树为空,返回0，号码已经存在（计数器加1），返回-1,否则返回最后查找的位置int search(int node, char* k){ int parent=0; int current=node; while(current!=0) { parent=current; int tmp = strcmp(key,k); if(tmp == 0) { value++; return -1; }else if(tmp<0) { current = right_child; }else { current = left_child; } } return parent;}//插入新节点int insert(int node,char* k){ //判断一下插在左子树，还是右子树 int tmp = strcmp(key,k); if(tmp==0) return 0; int new_node = ++curr_size;//分配新位置 strcpy(key,k); value=1; left_child=0; right_child=0; if(new_node==1)//树为空 root = 1; if(tmp>0) left_child = new_node; else right_child = new_node; return 1;}void build_tree(){ //freopen("in.txt","r",stdin); char buf; 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); printf("%s %.4f\n",key ,value*100.0/num_trees); inorder_tree(right_child);}int main(){ build_tree(); inorder_tree(root); return 0;}
页:
[1]