//哈弗曼編碼的實現類
public class HffmanCoding {
    private int charsAndWeight[][];// [][0]是 字符，[][1]存放的是字符的權值（次數）
    private int hfmcoding[][];// 存放哈弗曼樹
    private int i = 0;// 循環變量
    private String hcs[];
    public HffmanCoding(int[][] chars) {
        // TODO 構造方法
        charsAndWeight = new int[chars.length][2];
        charsAndWeight = chars;
        hfmcoding = new int[2 * chars.length - 1][4];// 為哈弗曼樹分配空間
    }
    // 哈弗曼樹的實現
    public void coding() {
        int n = charsAndWeight.length;
        if (n == 0)
            return;
        int m = 2 * n - 1;
        // 初始化哈弗曼樹
        for (i = 0; i < n; i++) {
            hfmcoding[i][0] = charsAndWeight[i][1];// 初始化哈弗曼樹的權值
            hfmcoding[i][1] = 0;// 初始化哈弗曼樹的根節點
            hfmcoding[i][2] = 0;// 初始化哈弗曼樹的左孩子
            hfmcoding[i][3] = 0;// 初始化哈弗曼樹的右孩子
        }
        for (i = n; i < m; i++) {
            hfmcoding[i][0] = 0;// 初始化哈弗曼樹的權值
            hfmcoding[i][1] = 0;// 初始化哈弗曼樹的根節點
            hfmcoding[i][2] = 0;// 初始化哈弗曼樹的左孩子
            hfmcoding[i][3] = 0;// 初始化哈弗曼樹的右孩子
        }
        // 構建哈弗曼樹
        for (i = n; i < m; i++) {
            int s1[] = select(i);// 在哈弗曼樹中查找雙親為零的 weight最小的節點
            hfmcoding[s1[0]][1] = i;// 為哈弗曼樹最小值付雙親
            hfmcoding[s1[1]][1] = i;
            hfmcoding[i][2] = s1[0];// 新節點的左孩子
            hfmcoding[i][3] = s1[1];// 新節點的右孩子
            hfmcoding[i][0] = hfmcoding[s1[0]][0] + hfmcoding[s1[1]][0];// 新節點的權值是左右孩子的權值之和
        }
    }
    // 查找雙親為零的 weight最小的節點
    private int[] select(int w) {
        // TODO Auto-generated method stub
        int s[] = { -1, -1 }, j = 0;// s1 最小權值且雙親為零的節點的序號 ， i 是循環變量
        int min1 = 32767, min2 = 32767;
        for (j = 0; j < w; j++) {
            if (hfmcoding[j][1] == 0) {// 只在尚未構造二叉樹的結點中查找（雙親為零的節點）
                if (hfmcoding[j][0] < min1) {
                    min2 = min1;
                    s[1] = s[0];
                    min1 = hfmcoding[j][0];
                    s[0] = j;
                } else if (hfmcoding[j][0] < min2) {
                    min2 = hfmcoding[j][0];
                    s[1] = j;
                }
            }
        }
        return s;
    }
    public String[] CreateHCode() {// 根據哈夫曼樹求哈夫曼編碼
        int n = charsAndWeight.length;
        int i, f, c;
        String hcodeString = "";
        hcs = new String[n];
        for (i = 0; i < n; i++) {// 根據哈夫曼樹求哈夫曼編碼
            c = i;
            hcodeString = "";
            f = hfmcoding[i][1]; // f 哈弗曼樹的根節點
            while (f != 0) {// 循序直到樹根結點
                if (hfmcoding[f][2] == c) {// 處理左孩子結點
                    hcodeString += "0";
                } else {
                    hcodeString += "1";
                }
                c = f;
                f = hfmcoding[f][1];
            }
            hcs[i] = new String(new StringBuffer(hcodeString).reverse());
        }
        return hcs;
    }
    public String show(String s) {// 對字符串顯示編碼
        String textString = "";
        char c[];
        int k = -1;
        c = new char[s.length()];
        c = s.toCharArray();// 將字符串轉化為字符數組
        for (int i = 0; i < c.length; i++) {
            k = c[i];
            for (int j = 0; j < charsAndWeight.length; j++)
                if (k == charsAndWeight[j][0])
                    textString += hcs[j];
        }
        return textString;
    }
    // 哈弗曼編碼反編譯
    public String reCoding(String s) {
        String text = "";// 存放反編譯后的字符
        int k = 0, m = hfmcoding.length - 1;// 從根節點開始查詢
        char c[];
        c = new char[s.length()];
        c = s.toCharArray();
        k = m;
        for (int i = 0; i < c.length; i++) {
            if (c[i] == '0') {
                k = hfmcoding[k][2];// k的值為根節點左孩子的序號
                if (hfmcoding[k][2] == 0 && hfmcoding[k][3] == 0)// 判斷是不是葉子節點，條件（左右孩子都為零）
                {
                    text += (char) charsAndWeight[k][0];
                    k = m;
                }
            }
            if (c[i] == '1') {
                k = hfmcoding[k][3];// k的值為根節點右孩子的序號
                if (hfmcoding[k][2] == 0 && hfmcoding[k][3] == 0)// 判斷是不是葉子節點，條件（左右孩子都為零）
                {
                    text += (char) charsAndWeight[k][0];
                    k = m;
                }
            }
        }
        return text;
    }
}