huffmantree.java

这是一个huffmanCode算法

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package lab6;

import java.io.*;
import java.util.*;;
/**
 *
 * @author Administrator
 */
public class HuffmanTree{

     //添加类HuffmanTree中包含的变量。
     ArrayList<HuffmanTree> minHeap = new ArrayList<HuffmanTree>();//最小堆
     ArrayList<HuffmanTree> output = new ArrayList<HuffmanTree>(); //输出链表


     HuffmanTree[] tree = new HuffmanTree[32];//构造最后标数字时候的树


     HuffmanTree parentNode;//构造父节点，左儿子，右儿子和根节点。
     HuffmanTree leftNode;
     HuffmanTree rightNode;
     HuffmanTree root;


     int freq;
     int Char;
     String huffmanCode;
     int heap_size;
     



    /* Construct method */
    public HuffmanTree() {
        freq = 0;
        huffmanCode = "";
    /* add your code here */
    }//初始化。

    /* Generate the HuffmanTree according to the given frequency */
    public void HUFFMAN(int[] C) {

        for(int i = 0;i < C.length;i++){
            if (C[i] != 0)
            {
                HuffmanTree tmp = new HuffmanTree();
                tmp.setFreq(C[i]);
                tmp.setChar(i);
                minHeap.add(tmp);
            }
        }

        int n = minHeap.size();
        buildMinHeap();//建立最小堆。


        for (int i = 0; i < n - 1; i++) {
            HuffmanTree  z = new HuffmanTree();
            HuffmanTree  x = new HuffmanTree();
            HuffmanTree  y = new HuffmanTree();
            x = extractMin();
            z.leftNode = x;
            y = extractMin();
            z.rightNode = y;
            y.parentNode = z;
            x.parentNode = z;
            z.setFreq( x.getFreq() + y.getFreq());
            insert(z);
        }
        root = extractMin();
        root.parentNode = null;
    }


    /* Print out the resulting representation */
    PrintWriter out;
    public void printHuffmanTree() {
       getHuffmanCode(root);
        File file = new File("Hugefile.txt");
        try {
            out = new PrintWriter(new FileWriter(file));
            out.println("Char\tFreq\tRepresentation");
            for(int i = 0;i < count;i++)
                out.println(""+(char)output.get(i).getChar()+"\t"+output.get(i).getFreq()+"\t"+output.get(i).huffmanCode);
        } catch (IOException e) {
            e.printStackTrace();
        }
        try{
            out.close();
        }
        catch(Exception e){
            e.printStackTrace();
        }
        /* add your code here */
        return;

    }


     public void add(HuffmanTree ht){
        for(int i = 0;i < tree.length;i++){
            if(tree[i] == null){
                tree[i] = ht;
                break;
            }
        }
    }

    public HuffmanTree extract(){
       HuffmanTree ret = tree[0];
       for(int i = 0;i < tree.length - 1 && tree[i] != null;i++)
           tree[i] = tree[i + 1];
       return ret;
    }

    public boolean isEmpty(){
        boolean ret = true;
        for(int i = tree.length - 1;i >= 0;i--){
            if(tree[i] != null){
                ret = false;
                break;
            }
        }
        return ret;
    }

    //HuffmanTree中的方法
    public void setChar(int Char){
        this.Char = Char;
    }

    public int getChar(){
        return Char;
    }

    public void setFreq(int freq){
        this.freq = freq;
    }

    public int getFreq(){
        return freq;
    }

    //MINUMHEAP中的方法
    public int parent(int i) {
        return (int)((i + 1) / 2 - 1);
    }

    public int left(int i) {
        return 2 * (i + 1) - 1;
    }

    public int right(int i) {
        return 2 * (i + 1);
    }

    public void minHeapify(int i) {
        int left = left(i);
        int right = right(i);
        int smallest = i;
        if (left <= heap_size && minHeap.get(left).getFreq() < minHeap.get(i).getFreq()) {
            smallest = left;
        } else {
            smallest = i;
        }
        if (right <= heap_size && minHeap.get(right).getFreq() < minHeap.get(i).getFreq()) {
            smallest = right;
        }
        if (smallest != i) {
            HuffmanTree tmp = minHeap.get(i);
            minHeap.set(i,minHeap.get(smallest));
            minHeap.set(smallest,tmp);
            minHeapify(smallest);
        }
    }

    public void buildMinHeap(){
        heap_size = minHeap.size() - 1;
        for (int i = minHeap.size() / 2; i >= 0; i--) {
            minHeapify(i);
        }
    }

    public HuffmanTree extractMin() {
        if (heap_size < 0) {
            System.out.println("ERROR :heap underflow!");
        }
        HuffmanTree min = minHeap.get(0);
        minHeap.set(0,minHeap.get(heap_size));
        heap_size--;
        minHeapify(0);
        return min;
    }

    public void heapDecreaseKey(int i, HuffmanTree key) {
        if (key.getFreq() > minHeap.get(i).getFreq()) {
            System.out.println("ERROR :new key is larger than current key!");
        }
        minHeap.set(i,key);
        while (i > 0 && minHeap.get(parent(i)).getFreq() > minHeap.get(i).getFreq()) {
            HuffmanTree tmp = minHeap.get(i);
            minHeap.set(i,minHeap.get(parent(i)));
            minHeap.set(parent(i),tmp);
            i = parent(i);
        }
    }

    public void insert(HuffmanTree key) {
        heap_size++;
        HuffmanTree tmp = new HuffmanTree();
        tmp.setFreq(Integer.MAX_VALUE);
        minHeap.set(heap_size,tmp);
        heapDecreaseKey(heap_size, key);
    }

    // 在树里面添加元素HuffmanTree，并产生HuffmanCode。
    int count;
    public void getHuffmanCode(HuffmanTree rootNode) {
        add(rootNode);
        while (!isEmpty()) {
            HuffmanTree o = extract();
            HuffmanTree l = o.leftNode;
            HuffmanTree r = o.rightNode;

            if (l != null) {
                add(l);
                l.huffmanCode = "0";
            }
            if (r != null) {
                add(r);
                r.huffmanCode = "1";
            }
            if ((l == null) && (r == null)){
                HuffmanTree p = o.parentNode;
                while (p != null) {
                    o.huffmanCode += p.huffmanCode;
                    p = p.parentNode;
                }
                if (o.huffmanCode != null) {
                    StringBuffer buffer = new StringBuffer(o.huffmanCode);
                    buffer = buffer.reverse();
                    o.huffmanCode = buffer.toString();
                }
                output.add(o);
                count++;
            }
        }
    }

}