首页 > ACM题库 > 九度OJ > 九度-1172-哈夫曼树[解题代码]
2013
12-13

九度-1172-哈夫曼树[解题代码]

题目来源:2010年北京邮电大学计算机研究生机试真题

题目描述:

哈夫曼树,第一行输入一个数n,表示叶结点的个数。需要用这些叶结点生成哈夫曼树,根据哈夫曼树的概念,这些结点有权值,即weight,题目需要输出所有结点的值与权值的乘积之和。

输入:

输入有多组数据。
每组第一行输入一个数n,接着输入n个叶节点(叶节点权值不超过100,2<=n<=1000)。

输出:

输出权值。

样例输入:
5  
1 2 2 5 9
样例输出:
37

java 代码如下:
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {
	static int num;
//	static int deep;
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		while(s.hasNextInt()){
			ArrayList<Tree> list = new ArrayList<Tree>();

			int n = s.nextInt();
			for(int i=0; i<n; i++){
				Tree temp = new Tree(null,null,s.nextInt(),0);
				list.add(temp);
			}
			Tree root = null;
			
			while(list.size()>1){
				Collections.sort(list);
				Tree t1 = list.get(0);
				Tree t2 = list.get(1);
				int a = t1.value;
				int b = t2.value;
				Tree t = new Tree(t1,t2,a+b,1);
				list.add(t);
				list.remove(0);
				list.remove(0);
				root = t;
			}
			num = 0;
			method(root,0 );
			System.out.println(num);
		}
		
	
	}
	
	static void method(Tree root,int deep){
		if(root != null){
			if(root.flag == 0){
				num += deep * root.value;
				return;
			}
			method(root.left,++deep);
			method(root.right,deep);
		}
	}
	
	

}

class Tree implements Comparable<Tree>{
	Tree left;
	Tree right;
	public int value;
	int flag;
	public Tree(Tree l,Tree r,int i,int flag){
		left = l;
		right = r;
		value = i;
		this.flag = flag;
	}
	
	@Override
	public int compareTo(Tree o) {
		if(this.value>o.value)
			return 1;
		else if(this.value<o.value)
			return -1;
		else
			 return 0;
	}
}

/**************************************************************
	Problem: 1172
	User: coder
	Language: Java
	Result: Accepted
	Time:1140 ms
	Memory:40928 kb
****************************************************************/


  1. 如果两个序列的最后字符不匹配(即X [M-1]!= Y [N-1])
    L(X [0 .. M-1],Y [0 .. N-1])= MAX(L(X [0 .. M-2],Y [0 .. N-1]),L(X [0 .. M-1],Y [0 .. N-1])
    这里写错了吧。

  2. 嗯 分析得很到位,确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样:push时,比较要push的elem和辅助栈的栈顶,elem<=min.top(),则min.push(elem).否则只要push(elem)就好。在pop的时候,比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();},否则{stack.pop();}.