java实现哈夫曼树模板
package Template;public class HuffmanTree {class HuffmanNode {int w;// 权值int lChild, rChild, parent;// 左右孩子及父节点public HuffmanNode(int w) {this.w = w;lChild = rChild = parent = -1;}}int n;HuffmanNode[] huffman ;//从huffman中找出两个最小的权值，并保存小标到m1和m2int m1,m2;public void selectMin(){//找出最小的int minw = Integer.MAX_VALUE;for (int i = 0; i < n; i++) {if (huffman[i].w < minw && huffman[i].parent == -1) {minw = huffman[i].w;m1 = i;}}//找次小的minw = Integer.MAX_VALUE;for (int i = 0; i < n; i++) {if (huffman[i].w < minw && huffman[i].parent == -1 && i != m1) {minw = huffman[i].w;m2 = i;}}}//建立赫夫曼树public void buildHuffmanTree(int[] w) {n = w.length;huffman = new HuffmanNode[2*n-1];for (int i = 0; i < n; i++)huffman[i] = new HuffmanNode(w[i]);for (int i = n; i < 2 * n - 1; i++)huffman[i] = new HuffmanNode(-1);while(n < huffman.length){//从huffman中选择两个权值最小的节点构建新节点selectMin();//构造新节点huffman[n].w = huffman[m1].w+huffman[m2].w;huffman[n].lChild = m1;huffman[n].rChild = m2;//修改m1和m2的父节点指针huffman[m1].parent = n;huffman[m2].parent = n++;}}//求带权路径长度public int WPL(int[]w){int sum = 0;for(int i = 0;i<w.length;i++){int p = huffman[i].parent;int ans = 0;while(p != -1){ans ++;p = huffman[p].parent;}sum +=ans*w[i]; }return sum;}//测试public void test(){int []w = {7,5,2,4};buildHuffmanTree(w);int r = WPL(w);System.out.println(r);}public static void main(String[] args) {new HuffmanTree().test();}}