wpl：树的所有叶结点的带权路径长度之和，称为树的带权路径长度表示为WPL。
wpl最小的树成为哈夫曼树。 构建思路：先选最小的俩个权值最小节点构成小的二叉树，该小二叉树的根节点的权值为这两个节点的权值的和，将该小二叉树的根节点的权值与其他节点权值比较，再选出权值最小的两个节点，在构成新的小二叉树，直到所有节点构成一棵树。即为哈夫曼树
import java.util.ArrayList; import java.util.Collections; import java.util.List; public class HuffmanTree { public static void main(String[] args) { int[] num = {13,7,8,3,29,6,1}; //把所有值放进Node中保存 //使用List对所有Node进行管理,方便每次排序 List<Node> nodes = new ArrayList<Node>(); for(int i =0;i<num.length;i++) { nodes.add(new Node(num[i])); } //构建哈夫曼树,最后nodes.get(0)即为哈夫曼树的根节点 while(nodes.size()>1) { //对节点进行排序 Collections.sort(nodes); //选当前List中最小的两个节点构成连接构成一个新的节点 Node left = nodes.get(0); Node right = nodes.get(1); Node current = new Node(left.value+right.value); current.setLeft(left); current.setRight(right); //将List中已连接的两个最小的节点删除，并将最新节点加入 nodes.remove(left); nodes.remove(right); nodes.add(current); } qian(nodes.get(0)); } //前序输出哈夫曼树进行验证 public static void qian(Node rootNode) { System.out.print(rootNode.value+" "); if(rootNode.getLeft()!=null) { qian(rootNode.getLeft()); } if(rootNode.getRight()!=null) { qian(rootNode.getRight()); } } } class Node implements Comparable<Node>{ int value; Node left; Node right; public Node(int value) { super(); this.value = value; } public int getValue() { return value; } public void setValue(int value) { this.value = value; } public Node getLeft() { return left; } public void setLeft(Node left) { this.left = left; } public Node getRight() { return right; } public void setRight(Node right) { this.right = right; } @Override public String toString() { return "Node [value=" + value + "]"; } /** * 用集合管理节点时，进行排序的规则 * 从小到大排序 return this.value - o.value */ @Override public int compareTo(Node o) { return this.value - o.value; } }