• hello，大家好，我是 Lorin，今天给大家带来数据结构中，二叉树的一种应用哈夫曼树，下面我们来看看它是如何实现数据存储和传输的压缩。

哈夫曼树（最优二叉树）

• 给定N个权值作为N个叶子节点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。
• 哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
• 基本定义：
  • 权：赋予节点一些属性，如数量或权重，如 A 的权重为 2。
  • 路径：一棵树中，一个节点到另外相邻一个节点之间的通路称为路径,或者边。
  • 节点路径长度：在一棵树中，从一个节点到根节点所经历的路径或边的数量，我们称为节点路径长度，如 A 的路径长度为 3。
  • 节点的带权路径长度：一棵树中，每一个节点都有自己的权重，权重*节点路径长度=节点的带权路径长度；如节点 A 的带权路径长度= 3 * 2 = 6。
  • 树的带权路径长度：所有节点的带权路径长度之和，如上述二叉树带权路径长度 = 2 * 3 + 1 * 3 + 3 * 2 + 1 * 3 + 1 * 3 + 2 * 2 = 25。

哈夫曼算法

• 构建哈夫曼树的过程称为哈夫曼算法，核心思想是将权重越大的节点放在靠近根节点的位置使节点的带权路径长度最小。
• 具体步骤：

1、根据给定的n个权值{w1,w2,…,wn}构成n棵二叉树的集合F={T1,T2,…,Tn}，其中每棵二叉树Ti中只有一个带权为wi根结点，其左右子树均为空。
2、在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。
3、在F中删除这两棵树，同时将新得到的二叉树加入F中。
4、重复2和3步骤，直到F只含一棵树为止。这棵树便是哈夫曼树。

图解

• Java 实现

/**
 * 哈夫曼树
 *
 */
public class HuffmanTree {
    public static void main(String[] args) {
        HashMap<String, Integer> hashMap = new HashMap<>(8);
        hashMap.put("A", 5);
        hashMap.put("B", 87);
        hashMap.put("C", 4);
        hashMap.put("D", 2);
        hashMap.put("E", 2);
        hashMap.put("F", 9);

        ArrayList<HuffmanTreeNode> huffmanTreeNodes = new ArrayList<>();
        for (String key : hashMap.keySet()) {
            HuffmanTreeNode huffmanTreeNode = new HuffmanTreeNode(key, hashMap.get(key));
            huffmanTreeNodes.add(huffmanTreeNode);
        }

        HuffmanTreeNode root = createTree(huffmanTreeNodes);

        printTree(root);
    }

    /**
     * 先序遍历哈夫曼树 根左右
     *
     * @param root
     */
    private static void printTree(HuffmanTreeNode root) {
        if (root == null) {
            return;
        }
        System.out.println("key:" + root.key + " weight:" + root.weight);
        printTree(root.leftChildren);
        printTree(root.rightChildren);
    }

    /**
     * 创建哈夫曼树
     *
     * @param huffmanTreeNodes
     * @return
     */
    private static HuffmanTreeNode createTree(ArrayList<HuffmanTreeNode> huffmanTreeNodes) {
        HuffmanTreeNode huffmanTreeNodeNew = null;
        while (huffmanTreeNodes.size() >= 2) {
            // 取出权值最小的两个值
            huffmanTreeNodes.sort(Comparator.comparing(o -> o.weight));
            String newKey = huffmanTreeNodes.get(0).key + huffmanTreeNodes.get(1).key;
            int newWeight = huffmanTreeNodes.get(0).weight + huffmanTreeNodes.get(1).weight;
            System.out.println(newKey + newWeight);
            huffmanTreeNodeNew = new HuffmanTreeNode(newKey, newWeight);
            huffmanTreeNodeNew.leftChildren = huffmanTreeNodes.get(0);
            huffmanTreeNodeNew.rightChildren = huffmanTreeNodes.get(1);
            huffmanTreeNodes.remove(0);
            huffmanTreeNodes.remove(1);
            huffmanTreeNodes.add(huffmanTreeNodeNew);
        }
        return huffmanTreeNodeNew;
    }

    /**
     * 哈夫曼树节点
     */
    static class HuffmanTreeNode {
        String key;
        // 权重
        Integer weight;

        HuffmanTreeNode leftChildren;

        HuffmanTreeNode rightChildren;

        public HuffmanTreeNode(String key, Integer weight) {
            this.key = key;
            this.weight = weight;
        }
    }
}

应用-哈夫曼编码

• 哈夫曼编码在数据压缩中有非常广泛的运用。
• 哈夫曼编码是可变长编码(VLC)的一种。如果长短不等其实很容易混淆，若要设计长短不等的编码，则必须是任一字符的编码都不是另一个字符的编码的前缀，这种编码又称做前缀编码。

案例

• 比如我们有一段文字内容为“BADCADFEED”要网络传输给别人，使用定长编码（3位）用二进制的数字（0和1）来实现，我们可以用相应的二进制数据编码表示：

• 使用上述编码进行编码对文字内容“BADCADFEED”，真正传输的数据就是编码后的“001 000 011 010 000 011 101 100 100 011”，对方接收时可以按照3位一分来译码。如果一篇文章很长，这样的二进制串也将非常的可怕。

哈夫曼编码构建

• 实际上，一段内容中不同的字符出现的频率是不同的，哈夫曼树编码的的思想就是使出现频率高的字符编码长度尽可能小。
• 上述字符串“BADCADFEED”构建哈夫曼编码，流程如下图所示：

• 定长编码二进制串：001 000 011 010 000 011 101 100 100 011（共30个字符）
• 哈夫曼编码二进制串：100 000 01 101 000 01 001 11 11 01（共25个字符）
• 可以看到编码数据被压缩节约了大约17%的存储或传输成本。随着字符的增加和多字符权重的不同，这种压缩会更加显出其优势。

总结

• 给定N个权值作为N个叶子节点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。最优二叉树经常用于数据存储和传输中来压缩数据，减少存储成本和传输成本。
• 构造最优二叉树的过程中，子树的构建可能有多种选择，因此构建的最优二叉树也可能不同，但树的带权路径长度一定满足等于最小值。