huffmantree.java

来自「用Java编写的编码算法」· Java 代码 · 共 84 行

/*
 * HuffmanTree.java
 *
 * Created on 2008年11月14日, 上午12:21
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */

package coding;

/**
 *
 * @author new
 */
public class HuffmanTree {
    static final double MAXNUMBER=1000;
    /** Creates a new instance of HuffmanTree */
    public HuffmanTree() {
    }
   public void creatHuffmanTree(QHTNode ht[],int n){
    int i,j;
    int lchild,rchild;
    double minL,minR;
    for(i=0;i<2*n-1;i++){
        if(i>=n) ht[i]=new QHTNode();
        ht[i].parent = ht[i].lchild = ht[i].rchild = -1;
    }
    for(i=n;i<2*n-1;i++){
        minL = minR = MAXNUMBER;
        lchild = rchild = -1;
        for(j=0;j<i;j++){
            if(ht[j].parent == -1){
                if(ht[j].weight < minL){
                    minR = minL;
                    minL = ht[j].weight;
                    rchild = lchild;
                    lchild = j;
                }else if(ht[j].weight < minR){
                    minR = ht[j].weight;
                    rchild = j;
                }
            }
        }
        ht[lchild].parent = ht[rchild].parent = i;
        ht[i].weight = minL + minR;
        ht[i].lchild = lchild;
        ht[i].rchild = rchild;
    }    
}
    
    
 public void createHuffmanCode(QHTNode ht[],QHCode hc[],int n){
    int i,f,c;
    for(i=0;i<n;i++){
        hc[i]=new QHCode();
        hc[i].code="字符"+ht[i].c+"的哈弗曼编码为:";
        hc[i].start = n;
        c = i;
        int count=0;
         String[] sstr=new String[100];
        while((f=ht[c].parent) != -1){
            if(ht[f].lchild == c){
                sstr[count++]="0";
               // hc[i].code="0";
                hc[i].start--;
            }else{
                sstr[count++]="1";
               // hc[i].code="1";
                hc[i].start--;
            }
            c = f;
        }
        hc[i].start++;
        for(int j=count-1;j>=0;j--){
            hc[i].code+=sstr[j];
        }
        hc[i].code+="\n";
    }
}
 
 
}