哈夫曼树

package com.huffman;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author 陈华
 *
 */
public class HahuffmanTree {

	public Node getHaffumanTree(int[] arr) {
		List<Node> list = new ArrayList<Node>();

		for (int i : arr) {
			list.add(new Node(i));
		}
		while (list.size() > 1) {
			Collections.sort(list);
			Node left = list.get(list.size() - 1);
			Node right = list.get(list.size() - 2);
			int weight = left.weight + right.weight;
			Node parent = new Node(weight);
			parent.left = left;
			parent.right = right;
			list.remove(left);
			list.remove(right);
			list.add(parent);
		}
		return list.get(0);
	}

	public void proPrint(Node root) {
		if (root == null) {
			return;
		}
		System.out.println(root.weight);
		proPrint(root.left);
		proPrint(root.right);
	}

	public static void main(String[] args) {
		int[] arr = new int[] { 4, 3, 6, 7, 1, 4, 2, 9 };
			
		HahuffmanTree hahuffmanTree  = new HahuffmanTree();
		Node haffuman = hahuffmanTree.getHaffumanTree(arr);	
		hahuffmanTree.proPrint(haffuman);
	}
}

class Node implements Comparable<Node>{
	Node left ;
	Node right ;
	int weight ;
	
	public Node(int weight) {
		this.weight = weight;
	}

	@Override
	public int compareTo(Node o) {
		return o.weight-this.weight;
	}

	@Override
	public String toString() {
		return "Node [weight=" + weight + "]";
	}
	
	
}