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 + "]";
}
}