java 哈夫曼編碼

//哈夫曼樹類
public class HaffmanTree {
    //最大權值
    static final int MAXVALUE=1000;
    int nodeNum ; //葉子結點個數
    
    public HaffmanTree(int n)
    {
       this.nodeNum = n;
    }
    
    //構造哈夫曼樹算法
    public void haffman(int[] weight,HaffNode[] nodes)//權值數組，所有節點數組
    {
        int n = this.nodeNum;
        //m1,m2,表示最小的兩個權值，x1,x2,表示最小兩個權值對應的編号,m1表示最小，m2表示次小
        int m1,m2,x1,x2; 
        
        //初始化所有的結點，對應有n個葉子結點的哈夫曼樹，有2n-1個結點。
        for(int i=0;i < 2*n-1;i++)
        {
            HaffNode temp = new HaffNode();
            //初始化n個葉子結點，就是輸入的節點。0、1、2、3是葉子節點也是輸入的節點
            if(i < n)
            {
               temp.weight = weight[i];    
            }
            else
            {
               temp.weight = 0;    
            }
            temp.parent = 0;
            temp.flag = 0;
            temp.leftChild = -1;
            temp.rightChild = -1;
            nodes[i] = temp;
        }
        
        for(int i=0;i<n-1;i++){//初始化n-1個非葉子結點，n-1表示要循環n-1次求的n-1個數。
           m1 = m2 = MAXVALUE;
           x1 = x2 =0;
           for(int j=0;j< n+i;j++)//求得這n-1個數時，每次都是從0到n+i-1,并且flag=0的，flag=1表示已經加入到二叉樹。
           {   //以下2步是找出權值最小的2個
               if(nodes[j].weight<m1 && nodes[j].flag==0)//if成立了else、else if就不進去了。
               {
                //m1,x1初始值為第一個元素，後面如果比m1要小，則m1指向更小的，原來m1指向的現在由m2指向，
                //如果後面比m1大比m2小，則m2指向這個比m1大比m2小的，
                //也就是說m1指向最小的，m2指向第2小的。
                  m2 = m1;
                  x2 = x1;
                  m1 = nodes[j].weight;
                  x1 = j;
               }
               else if(nodes[j].weight<m2 && nodes[j].flag ==0)
               {
                  m2 = nodes[j].weight;
                  x2 = j;
               }
           }
           //将權值最小的2個組合成一個2插樹
           nodes[x1].parent = n+i;
           nodes[x2].parent = n+i;
           nodes[x1].flag = 1;
           nodes[x2].flag = 1;
           nodes[n+i].weight = nodes[x1].weight + nodes[x2].weight;
           nodes[n+i].leftChild = x1;
           nodes[n+i].rightChild = x2;
        }
        /*
        初始化數組之後：[1,3,5,7,4,9,16]
        編碼：100、101、11、0
        */
    }
    
    //哈弗曼編碼算法
    public void haffmanCode(HaffNode[] nodes,Code[] haffCode)
    {
        int n = this.nodeNum;
        Code code = new Code(n);//4
        int child,parent;
        
        for(int i=0;i<n; i++)//給前面n個輸入的節點進行編碼
        {
           code.start = n-1;//3
           code.weight = nodes[i].weight;//1
           child = i;//0
           parent = nodes[child].parent;
           //從葉子節點向上走來生成編碼，畫圖即可。
           while(parent!=0)
           {
              if(nodes[parent].leftChild == child)
              {
                  code.bit[code.start] = 0;
              }
              else
              {
                  code.bit[code.start] = 1;
              }
              
              code.start--; 
              child = parent;
              parent = nodes[child].parent;
           }
           
           Code temp = new Code(n);
           for(int j=code.start+1;j < n;j++)
           {
               temp.bit[j] = code.bit[j];
           }
           temp.weight = code.weight;
           temp.start = code.start;
           haffCode[i] = temp;
        }
    }
}




//哈夫曼樹的結點類
public class HaffNode {
   
    int weight; //權值
    int parent ;//他的雙親
    int flag ;//标志，是否為葉子節點
    int leftChild; //他的左孩子
    int rightChild;//他的右孩子
    
    HaffNode()
    {
        
    }
    
}



//哈夫曼編碼類
public class Code {

    int[] bit;  //編碼的數組
    int start;  //編碼的開始下标
    int weight; //權值
    Code(int n){
        bit = new int[n];
        start = n-1;
    }
}




public class Test {

    public static void main(String[] args) {
        
        int n = 4;
        int[] weight = {1,3,5,7};
        HaffmanTree haffTree = new HaffmanTree(n);
        HaffNode[] nodes = new HaffNode[2*n-1];
        Code[] codes = new Code[n]; 
        //構造哈夫曼樹
        haffTree.haffman(weight, nodes);
        //生成哈夫曼編碼
        haffTree.haffmanCode(nodes, codes);
        
        //列印哈夫曼編碼
        for(int i=0;i<n;i++)
        {
            System.out.print("Weight="+codes[i].weight+" Code=");
            for(int j=codes[i].start+1;j<n;j++)
            {
               System.out.print(codes[i].bit[j]);    
            }
            System.out.println();
        }
    }

}      

哈夫曼樹：

帶權路徑長度是做小的，要使一棵二叉樹的帶權路徑長度WPL值最小，必須使權值越大的葉結點越靠近根結點。哈夫曼提出的構造哈夫曼樹構造算法為：

（1）由給定的n個權值{w1,w2,…,wn}構造n棵隻有根 結點的二叉樹，進而得到一個二叉樹森林F={T1,T2,…,Tn}。

（2）在二叉樹森林F中選取根結點的權值最小和次小的兩棵二叉樹作為新的二叉樹的左右子樹構造新的二叉樹，新的二叉樹的根結點權值為左右子樹根結點權值之和。

（3）在二叉樹森林F中删除作為新二叉樹左右子樹的兩棵二叉樹，将新二叉樹加入到二叉樹森林F中。

（4）重複步驟（2）和（3），當二叉樹森林F中隻剩下一棵二叉樹時，這棵二叉樹就是所構造的哈夫曼樹。