hardwoodspecies.java

PKU中一些数据结构基本算法题的java实现

import java.math.BigDecimal;
import java.util.Scanner;


/**
 * ID:2418
 * 二叉查找树
 * @author yhm
 *
 */
public class HardwoodSpecies {

	static int num;
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		num = 0;
		TreeNode root = null;
		while(cin.hasNextLine()){
			String key = cin.nextLine();
//			if(key.equals("")){
//				continue;
//			}
//			if(key.equals("0"))
//				break;
			num++;
			root = insert(root,key);
			
			
		}
		inorder_walk(root);

	}
	
	
	static void inorder_walk(TreeNode t)
	{
	    //如果该树为null，返回
	    if(t==null)
	        return;
	    
	    //递归遍历左右子树

	    inorder_walk(t.left);

		double rate = (double)(t.count*100)/(double)num;
		BigDecimal b = new BigDecimal(rate);
		b = b.setScale(4, BigDecimal.ROUND_HALF_UP);
		System.out.println(t.name + " "+ b);
	    
	    inorder_walk(t.right);
	    
	}
	
	
	static TreeNode insert(TreeNode t, String key){
	    //x指示查找过程中下降的路径，y始终指向x的父结点
	    TreeNode y=null;
	    TreeNode x=t;

	    //x下降
	    while(x!=null)
	    {	//如果已经有该名字
	        if(x.name.equals(key)){
	        	x.count++;
	        	return t;
	        }
	        
	        y=x;
	        //判断向左or向右
	        x=x.name.compareTo(key)>0?x.left:x.right;
	    }
	    //初始化结点	
	    x=new TreeNode();
	    x.name = key;


	    //如果树为空
	    if(t==null)
	        t=x;
	    else
	    {
	        //设置父结点的孩子结点
	        if(y.name.compareTo(key)>0)
	            y.left=x;
	        else
	            y.right=x;
	    }
	    return t;
	}

}

class TreeNode{
	TreeNode left;
	TreeNode right;
	String name;
	int count=1;
}