(哈)赫夫曼树（Java版）

[java] 
package D0727; 
 
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和m2 
    int 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(); 
    } 
 
} 
作者：lhfight

补充：软件开发 , Java ,