先從文本讀取字符,統(tǒng)計(jì)字符出現(xiàn)的次數(shù)用map保存,然后根據(jù)詞頻計(jì)算每個(gè)字符的哈弗曼編碼,哈弗曼樹的建立過(guò)程就是每次取兩個(gè)權(quán)值最小的節(jié)點(diǎn)生成新的節(jié)點(diǎn),根據(jù)建立的哈弗曼樹計(jì)算每個(gè)字符的哈弗曼編碼,如果當(dāng)前節(jié)點(diǎn)在父節(jié)點(diǎn)的左邊,當(dāng)前節(jié)點(diǎn)的編碼為0,否則為1,最后從上往下記錄哈弗曼編碼.代碼如下,代碼注釋很詳細(xì).

HuffmanTree.java

import java.util.*;

public class HuffmanTree {
    class Node {
        int val;
        int weight;
        Node left;
        Node right;
        Node parent;

        Node(int weight) {
            this.weight = weight;
        }
    }

    /**
     * 計(jì)算哈弗曼編碼
     *
     * @param counter key為對(duì)應(yīng)的字符,value為字符出現(xiàn)的次數(shù)
     * @return 返回一個(gè)map, key為字符, value為對(duì)應(yīng)的哈弗曼編碼
     */
    public Map<Integer, String> getHuffmanCode(Map<Integer, Integer> counter) {
        //根據(jù)權(quán)重排序建立一個(gè)優(yōu)先隊(duì)列來(lái)保存節(jié)點(diǎn),方便每次取最小的兩個(gè)節(jié)點(diǎn)
        PriorityQueue<Node> priorityQueue = new PriorityQueue<>(
                new Comparator<Node>() {
                    @Override
                    public int compare(Node o1, Node o2) {
                        return o1.weight - o2.weight;
                    }
                }
        );
        //用數(shù)組保存哈弗曼樹, 哈弗曼數(shù)的度為0的節(jié)點(diǎn)為counter.size(), 度為1的節(jié)點(diǎn)為0
        //度為2的葉子節(jié)點(diǎn)為counter.size() - 1
        Node[] huffmanTree = new Node[counter.size() * 2 - 1];
        int index = 0;
        //把葉子節(jié)點(diǎn)放在數(shù)組前面的counter.size()個(gè)位置
        for (Map.Entry<Integer, Integer> entry : counter.entrySet()) {
            huffmanTree[index] = new Node(entry.getValue());
            huffmanTree[index].val = entry.getKey();
            priorityQueue.add(huffmanTree[index]);
            index++;
        }

        //每次從優(yōu)先隊(duì)列中取權(quán)重最小的兩個(gè)節(jié)點(diǎn)生成新的父節(jié)點(diǎn)
        for (int i = counter.size(); i < huffmanTree.length; i++) {
            Node n1 = priorityQueue.poll();
            Node n2 = priorityQueue.poll();
            huffmanTree[i] = new Node(n1.weight + n2.weight);
            huffmanTree[i].left = n1;
            huffmanTree[i].right = n2;
            n1.parent = huffmanTree[i];
            n2.parent = huffmanTree[i];
            priorityQueue.add(huffmanTree[i]);
        }

        //levelTraverse(huffmanTree);
        //保存每個(gè)字符的哈弗曼編碼
        Map<Integer, String> res = new HashMap<>();
        //計(jì)算每個(gè)字符的哈弗曼值
        StringBuilder huffmanCode = new StringBuilder();
        Node parent, curNode;
        for (int i = 0; i < counter.size(); i++) {
            huffmanCode.setLength(0);
            curNode = huffmanTree[i];
            parent = huffmanTree[i].parent;
            //從下往上計(jì)算huffmanTree[i].val的的哈弗曼編碼
            while (parent != null) {
                //當(dāng)前節(jié)點(diǎn)在父節(jié)點(diǎn)的左邊,哈弗曼編碼為0,在右邊為1
                if (parent.left == curNode) {
                    huffmanCode.append("0");
                } else {
                    huffmanCode.append("1");
                }
                curNode = parent;
                parent = parent.parent;
            }
            //因?yàn)槭菑南峦仙傻?所以需要逆置一下
            huffmanCode.reverse();
            res.put(huffmanTree[i].val, huffmanCode.toString());
        }
        return res;
    }

    /**
     * 從上往下打印哈弗曼數(shù)的權(quán)值,調(diào)試用
     *
     * @param huffamanTree
     */
    private void levelTraverse(Node[] huffamanTree) {
        for (int i = huffamanTree.length - 1; i >= 0; i--) {
            System.out.print(huffamanTree[i].weight + " ");
        }
        System.out.println("");
    }
}

TestHuffmanTree.java

import java.io.*;
import java.util.HashMap;
import java.util.Map;

public class TestHuffmanTree {
    public static void main(String[] args) throws IOException {
        //統(tǒng)計(jì)每個(gè)字符出現(xiàn)的次數(shù)
        BufferedReader bis = null;
        try {
            bis = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
        Map<Integer, Integer> counter = new HashMap<>();
        while (true) {
            int k = bis.read();
            if (k == -1) {
                break;
            }
            counter.putIfAbsent(k, 0);
            counter.put(k, counter.get(k) + 1);
        }
        System.out.println("字符頻率為:");
        System.out.println(counter);
        HuffmanTree huffmanTree = new HuffmanTree();
        Map<Integer, String> huffmanCodes = huffmanTree.getHuffmanCode(counter);
        System.out.println("哈弗曼編碼為:");
        System.out.println(huffmanCodes);
    }

}

input.txt

abbcccddddeeeee