Huffman树在数据结构中的应用与解析

/**
 * 哈夫曼树
 */
public class HuffmanTree {
    static class Node{
        Character ch; // 保存被编码的字符
        long frequency ; // 被编码的字符出现频次
        Node left; // 左子节点
        Node right; // 右子节点
        Node parent; // 父节点
    }

static class Tree{
    Node root;
    List leafNodes;
}

/**
 * 构建huffman树
 * @return
 */
public static Tree buildHuffmanTree(
        Map  charAndCounts){

    Tree huffmanTree = new Tree();
    huffmanTree.leafNodes = new ArrayList();
    // 依据Node有序的队列
    PriorityQueue priorityQueue = new PriorityQueue();

    // 对每个字符进行遍历
    for(Character ch : charAndCounts.keySet()){
        long frequency = charAndCounts.get(ch);
        Node node = new Node(ch,frequency);
        // 存入叶子节点列表，以便于遍历
        huffmanTree.leafNodes.add(node);
        // 入堆
        priorityQueue.add(node);
    }

    // 进行建树操作，进行size-1次操作，每次取出两个最小的权值的节点，构建父节点并合并权值。
    for(int i = 0 ; i         Node node1 = priorityQueue.poll(); // 第一小 ，默认放右边
        Node node2 = priorityQueue.poll(); // 第二小，默认放左边
        Node top = new Node();
        top.right = node1;
        top.left = node2;
        top.frequency = node1.frequency + node2.frequency;

        node1.parent = top;
        node2.parent = top;

        priorityQueue.add(top);
    }

    // 经过size-1次合并操作后，队列中只剩下一个节点
    huffmanTree.root = priorityQueue.poll();
    return huffmanTree;
}

   /**
     * 进行编码
     * @param str
     * @param charAndCounts
     * @return
     */
    public static String encode(
            String str,
            Map charAndCounts){ Map chAndEncoding = new HashMap(); // 1. 构建huffman树 Tree tree = buildHuffmanTree(charAndCounts); // 2.依次遍历每个huffman树的叶子节点，每个节点由叶子节点向根节点遍历，并进行 0 、1的拼接。 List leafNodes = tree.leafNodes; for(Node leafNode : leafNodes){ Node current = leafNode; String binaryCode = ""; while(current != tree.root && current != null){ if(current.parent != null && current == current.parent.left){ binaryCode = "0" + binaryCode; }else if(current.parent != null && current == current.parent.right){ binaryCode = "1" + binaryCode; } current = current.parent; } chAndEncoding.put(leafNode.ch,binaryCode); } System.out.println(chAndEncoding); // 3.遍历每个字符进行编码 StringBuffer strEncoded = new StringBuffer(); for(char ch : str.toCharArray()){ strEncoded.append(chAndEncoding.get(ch)); } return strEncoded.toString(); }

    public static void main(String[] args) {
        Map map = new HashMap(); map.put('a',5l); map.put('b',24l); map.put('c',7l); map.put('d',17l); map.put('e',34l); map.put('f',5l); map.put('g',13l); System.out.println(encode("abcd",map)); }

{a=01001, b=10, c=0101, d=11, e=00, f=01000, g=011}
0100110010111

    /**
     * 解码过程
     * @param binStr
     * @param charsAndCounts
     * @return
     */
    public static String decode(
            String binStr,
            Map charsAndCounts){
        // 1.获得Huffman树
        Tree tree = buildHuffmanTree(charsAndCounts);

        // 2.按照给定的二进制字符串，挨个进行从根的查找，找到叶子节点后就转成原字符，从下一个字符串索引开始继续解码。
        StringBuffer originalStr = new StringBuffer();
        int i = 0;

        while(i < binStr.length()){
            char ch = '\0';
            Node current = tree.root;
            while(current.ch ==null && i < binStr.length()){
                ch = binStr.charAt(i);
                if(ch == '1'){
                    current = current.right;
                }else if(ch == '0'){
                    current = current.left;
                }
                i++;
            }
            originalStr.append(current.ch);
        }
        return originalStr.toString();
    }

    public static void main(String[] args) {
        Map map = new HashMap();
        map.put('a',5l);
        map.put('b',24l);
        map.put('c',7l);
        map.put('d',17l);
        map.put('e',34l);
        map.put('f',5l);
        map.put('g',13l);
        System.out.println(encode("abcd",map));
        System.out.println(decode("0100110010111",map));
    }

{a=01001, b=10, c=0101, d=11, e=00, f=01000, g=011}
0100110010111
abcd
abcd