哈夫曼树 | 小菜鸟

哈夫曼树（Huffman Tree）：最优二叉树与数据压缩应用

哈夫曼树（又称霍夫曼树）是一种带权路径长度最短的二叉树，也称为 “最优二叉树”。其核心思想是通过合理组织带权节点，使树的总带权路径长度最小，广泛应用于数据压缩（如哈夫曼编码）、信息检索等领域。

哈夫曼树的核心概念

关键术语

路径长度：两个节点之间的分支数量（如根节点到左子节点的路径长度为 1）。
树的路径长度：从根节点到所有节点的路径长度之和。
节点的带权路径长度：从该节点到根节点的路径长度 × 节点的权值（权值可表示频率、代价等）。
树的带权路径长度（WPL）：所有叶子节点的带权路径长度之和（哈夫曼树的优化目标）。

哈夫曼树的定义

对于给定的n个带权叶子节点，构造一棵二叉树，若其树的带权路径长度（WPL）最小，则该二叉树称为哈夫曼树。

示例：
假设有 4 个叶子节点，权值分别为a(4)、b(3)、c(2)、d(1)，其哈夫曼树的 WPL 计算如下：

叶子节点a（权 4）：路径长度 2 → 4×2=8
叶子节点b（权 3）：路径长度 2 → 3×2=6
叶子节点c（权 2）：路径长度 3 → 2×3=6
叶子节点d（权 1）：路径长度 3 → 1×3=3
总 WPL：8+6+6+3=23（为所有可能二叉树中最小）

哈夫曼树的构建算法

哈夫曼树的构建采用贪心策略，步骤如下：

初始化：将所有带权叶子节点视为独立的单节点树，组成森林。
合并：在森林中选取权值最小的两棵树，以它们为左右子树构建一棵新树，新树的权值为两棵树的权值之和。
更新：将新树加入森林，移除被合并的两棵树。
重复：重复步骤 2 和 3，直至森林中只剩一棵树（即哈夫曼树）。

代码实现（Java）

import java.util.*;

public class HuffmanTree<E> {
    // 哈夫曼树节点
    static class Node<E> {
        E data;         // 节点数据（叶子节点有效）
        double weight;  // 权值
        Node<E> left;   // 左子树
        Node<E> right;  // 右子树

        public Node(E data, double weight) {
            this.data = data;
            this.weight = weight;
        }

        @Override
        public String toString() {
            return "Node[data=" + data + ", weight=" + weight + "]";
        }
    }

    // 构建哈夫曼树
    public static <E> Node<E> buildHuffmanTree(List<Node<E>> leafNodes) {
        // 使用优先队列（最小堆）存储树，便于快速获取权值最小的两棵树
        PriorityQueue<Node<E>> heap = new PriorityQueue<>(Comparator.comparingDouble(n -> n.weight));
        heap.addAll(leafNodes);

        while (heap.size() > 1) {
            // 取出权值最小的两棵树
            Node<E> left = heap.poll();
            Node<E> right = heap.poll();

            // 构建新树（非叶子节点，data为null）
            Node<E> parent = new Node<>(null, left.weight + right.weight);
            parent.left = left;
            parent.right = right;

            // 将新树加入队列
            heap.add(parent);
        }

        // 剩余的最后一棵树即为哈夫曼树的根节点
        return heap.poll();
    }

    // 测试：构建权值为4、3、2、1的哈夫曼树
    public static void main(String[] args) {
        List<Node<String>> leafNodes = new ArrayList<>();
        leafNodes.add(new Node<>("a", 4));
        leafNodes.add(new Node<>("b", 3));
        leafNodes.add(new Node<>("c", 2));
        leafNodes.add(new Node<>("d", 1));

        Node<String> root = buildHuffmanTree(leafNodes);
        System.out.println("哈夫曼树的根节点：" + root); // 权值为4+3+2+1=10
    }
}

构建特点

哈夫曼树中没有度为 1 的节点（所有非叶子节点的度均为 2）。
若有n个叶子节点，哈夫曼树的总节点数为 2n - 1（非叶子节点数为n-1）。

哈夫曼编码：数据压缩的应用

哈夫曼编码是哈夫曼树的典型应用，通过对高频字符分配短编码、低频字符分配长编码，实现数据压缩。

编码步骤

统计频率：计算字符串中每个字符的出现频率（作为权值）。
构建哈夫曼树：以字符为叶子节点，频率为权值，构建哈夫曼树。
生成编码：从根节点出发，左分支赋0，右分支赋1，叶子节点的编码为从根到该节点的路径编码。

示例：字符串 “abcdabcaba” 的编码

步骤 1：统计字符频率（权值）

字符串 abcdabcaba 中各字符出现次数（频率）为：

a：出现 4 次（频率 4）
b：出现 3 次（频率 3）
c：出现 2 次（频率 2）
d：出现 1 次（频率 1）

步骤 2：构建哈夫曼树

按哈夫曼树的构建规则（每次合并权值最小的两棵树）：

初始森林：{a(4), b(3), c(2), d(1)}。
第一次合并：权值最小的 c(2) 和 d(1) 合并为新树 N1(3)（左子树 d，右子树 c）。
第二次合并：剩余树 {a(4), b(3), N1(3)} 中，合并 b(3) 和 N1(3) 为新树 N2(6)（左子树 b，右子树 N1）。
第三次合并：剩余树 {a(4), N2(6)} 合并为根节点 N3(10)（左子树 a，右子树 N2）。

最终哈夫曼树结构如下（左分支为 0，右分支为 1）：

  N3(10)
 /    \
a(4)  N2(6)
     /    \
   b(3)  N1(3)
        /    \
      d(1)  c(2)

步骤 3：生成哈夫曼编码

从根节点到叶子节点的路径编码（左 0 右 1）：

a：路径为 根→左 → 编码 0
b：路径为 根→右→左 → 编码 10
c：路径为 根→右→右→右 → 编码 111
d：路径为 根→右→右→左 → 编码 110

步骤 4：字符串编码结果

字符串 abcdabcaba 对应的编码为：

a→0，b→10，c→111，d→110
完整编码：0 10 111 110 0 10 111 0 10 0
合并后：0101111100101110100（共 19 位）

原字符串长度为 10 个字符，若用固定 2 位编码（如 a:00、b:01 等）需 20 位，哈夫曼编码仅用 19 位，实现了轻度压缩。
高频字符（如 a）分配更短编码（1 位），低频字符（如 d）分配更长编码（3 位），符合 “高频短码” 的优化思想

解码过程

从根节点开始，按二进制编码遍历哈夫曼树：遇到0走左子树，1走右子树，到达叶子节点即解码出一个字符，重复直至编码结束。

哈夫曼树的优势与适用场景

优势

最优性：带权路径长度最短，确保编码、检索等场景的效率最高。
灵活性：权值可表示频率、代价等，适应多种优化问题。

适用场景

数据压缩：哈夫曼编码（如 ZIP、PNG 等格式的压缩算法）。
信息检索：根据关键词频率优化检索树，减少平均查找时间。
决策树：基于代价的最优决策路径规划。

总结

哈夫曼树通过贪心策略构建，实现了带权路径长度最小的最优二叉树，其核心价值在于对高频元素的高效处理。哈夫曼编码作为其典型应用，通过变长编码实现数据压缩，在信息传输和存储中不可或缺