http://poj.org/problem?id=2418
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static class TreeNode{
private String species;
private TreeNode left;
private TreeNode right;
private int count;
}
public static class Tree{
private int total;
private TreeNode root=new TreeNode();
public void insert(String newSpecies,TreeNode root){
if(root.count==0){
root.species=newSpecies;
root.count++;
total++;
return;
}
else{
if(root.species.compareTo(newSpecies)>0){
if(root.left==null){
root.left=new TreeNode();
}
insert(newSpecies,root.left);
}else{
if(root.species.compareTo(newSpecies)<0){
if(root.right==null){
root.right=new TreeNode();
}
insert(newSpecies,root.right);
}else{
root.count++;
total++;
}
}
}
}
public void travelTree(TreeNode root){
if(root==null){
return;
}
travelTree(root.left);
System.out.print(root.species+" ");
double p=(double)root.count*100/total;
System.out.printf("%.4f", p);
System.out.println();
travelTree(root.right);
}
}
public static void main(String[] args){
BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
Tree t=new Tree();
String s;
try {
while((s=reader.readLine())!=null){
t.insert(s,t.root);
}
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
t.travelTree(t.root);
}
}