第51章哈夫曼树

本讲对应 GESP C++ 六级知识块 · 树（哈夫曼树）与基于树的编码（哈夫曼编码）

考核目标：理解哈夫曼树（最优二叉树）的定义与"带权路径长度最短"的含意；掌握其贪心构造方法；理解哈夫曼编码作为前缀码的原理，能进行简单应用。

核心知识点：

带权路径长度（WPL）的定义与计算
哈夫曼树的贪心构造（每次合并权值最小的两棵树）
哈夫曼编码：左 0 右 1，前缀码、无歧义解码

哈夫曼树构造与编码

哈夫曼树(Huffman Tree)又称最优二叉树，是一种带权路径长度最短的二叉树，由计算机科学家大卫哈夫曼于1952年提出。哈夫曼树在数据压缩、决策系统等领域有着广泛应用。

51.1 哈夫曼树的基本概念

51.1.1 核心术语

权值：赋予树中点的一个有意义的数值(如频率、概率、代价等)。路径长度：从树中一个节点到另一个节点所经过的边的数量。节点的带权路径长度：从根节点到该节点的路径长度与该节点权值的乘积。树的带权路径长度(WPL)：树中所有叶子节点的带权路径长度之和，计算公式为

W=\sum_{i=1}^{n} w_{i} \times d_{i}

其中 $w_{i}$ 为第 $i$ 个叶子节点的权值， $d_{i}$ 为根节点到第 $i$ 个叶子节点的路径长度， $n$ 为叶子节点总数。

51.1.2 哈夫曼树的定义

哈夫曼树是指对于给定的 $n$ 个带权值的叶子节点，所能构造出的带权路径长度最小的二叉树。

示例：假设有4个叶子节点，权值分别为3、4、5、6。

树A（非最优，让权值小的节点处于更深层）：若 3、4 深度为 3，5、6 深度为 2，则 $W_A=3\times 3+4\times 3+5\times 2+6\times 2=9+12+10+12=43$
树B（哈夫曼树，最优）：按贪心法先合并 3 与 4 得到 7，再合并 5 与 6 得到 11，最后合并 7 与 11 得到 18，此时所有叶子深度均为 2，则 $W_B=2\times(3+4+5+6)=36$

对比可见 $W_B < W_A$ ，哈夫曼树确实使带权路径长度最小。

51.2 哈夫曼树的构造方法

哈夫曼树构造属于贪心算法，核心思路：每次选取权值最小的两棵树合并，直到仅剩一棵树。步骤：

初始化：所有叶子节点各自独立形成森林。
选取合并：从森林取出权值最小两棵树，创建新父节点，权值为两棵树根权值之和，两棵树作为新节点左右子树。
更新森林：移除原来两棵树，将新树加入森林。
循环重复，森林只剩一棵树时构造完成。

示例：权值3、4、5、6构造流程步骤1：森林初始包含 3、4、5、6 步骤2：合并 3 与 4 得新节点权值 7，森林变为 5、6、7 步骤3：合并 5 与 6 得新节点权值 11，森林变为 7、11 步骤4：合并7与11，根节点权值18，构造完成。最终带权路径 $W=2\times(3+4+5+6)=36$ （此时所有叶子节点深度均为 2）。

51.2.1 数据结构选择

构造过程需要频繁取出最小权值节点，优先使用最小堆（优先队列）提升效率。

#include <queue>
#include <vector>
using namespace std;
//哈夫曼树节点结构
struct HuffmanNode {
    int weight;
    HuffmanNode *left;
    HuffmanNode *right;
    HuffmanNode (int w): weight (w), left (NULL), right (NULL) {}
};
//最小堆比较器
struct CompareNode {
    bool operator()(HuffmanNode *a, HuffmanNode *b) {
        return a->weight > b->weight;
    }
};

51.2.2 构造算法实现

HuffmanNode* buildHuffmanTree(vector<int> weights){
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, CompareNode> minHeap;
    //所有权值节点入堆
    for (int w: weights){
        minHeap.push(new HuffmanNode(w));
    }
    //不断合并最小两棵树
    while (minHeap.size()>1){
        HuffmanNode *left = minHeap.top();
        minHeap.pop();
        HuffmanNode *right = minHeap.top();
        minHeap.pop();
        //创建合并父节点
        HuffmanNode *parent = new HuffmanNode(left->weight + right->weight);
        parent->left=left;
        parent->right= right;
        minHeap.push(parent);
    }
    return minHeap.top();
}

51.3 哈夫曼编码

哈夫曼编码是哈夫曼树核心应用，无损压缩算法，高频字符分配短编码，低频分配长编码，整体总编码长度最小。

51.3.1 编码规则

从根到叶子，左分支标记0、右分支标记1，路径拼接得到该字符编码。前缀编码特性：任意字符编码不会是另一个字符编码的前缀，解码无歧义。

示例：字符权值A=3、B=4、C=5、D=6 A编码：000 B编码：001 C编码：01 D编码：1 总编码长度：

3 \times 3+4 \times 3+5 \times 2+6 \times 1=9+12+10+6=37

51.3.2 编码实现

void generateHuffmanCodes (HuffmanNode *root, string code, vector<pair<int, string>>& codes){
    if (root == NULL) return;
    //到达叶子节点，记录编码
    if (root->left == NULL && root->right == NULL){
        codes.push_back({root->weight, code});
        return;
    }
    generateHuffmanCodes(root->left, code + "0", codes);
    generateHuffmanCodes(root->right, code + "1", codes);
}

51.4 哈夫曼树的特性

结构特性：哈夫曼树不存在度为1的节点，所有非叶子节点度均为2；若叶子数量为 $n$ ，则非叶子节点数为 $n-1$ ，总节点数 $= 2n-1$ 。
最优性：相同叶子权值集合下，哈夫曼树WPL一定最小。
不唯一性：合并时左右子树可交换、相同权值选取顺序不同，树结构可能不同，但WPL完全相等。

51.5 应用场景

数据压缩：ZIP、GZIP等压缩文件核心算法，减少冗余数据。
通信编码：降低传输数据量，节省带宽。
决策系统：依据代价构建最优决策树。
文本频率统计：根据字符频次生成最短编码。

51.6 注意事项

权值为0的节点必须参与构造，否则WPL计算出错。
仅单个叶子节点时，编码统一记为"0"。
时间复杂度：使用最小堆构造哈夫曼树复杂度 $O(n \log n)$ ，无序数组暴力查找为 $O(n^2)$ 。
解码流程：读取编码0/1，从根向下遍历，抵达叶子即完成一个字符解码。

练习题

哈夫曼树是指（） A. 节点数最多的二叉树 B. 带权路径长度（WPL）最小的二叉树 C. 深度最小的二叉树 D. 完全二叉树

答案与解析
答案：B
解析：哈夫曼树又称最优二叉树，其定义就是在给定一组带权叶子节点时，构造出的带权路径长度（WPL）最小的二叉树。它不一定是完全二叉树，也不一定最深或最浅。
构造哈夫曼树时，每次应选取（） A. 权值最大的两棵树合并 B. 权值最小的两棵树合并 C. 深度最大的两棵树合并 D. 任意两棵树合并

答案与解析
答案：B
解析：哈夫曼构造属于贪心算法，核心策略是每次从森林中取出权值最小的两棵树合并，使权值小的节点尽早、尽量浅地被重复累加，从而保证整体 WPL 最小。
关于哈夫曼编码，下列说法错误的是（） A. 它是一种前缀码，任意字符的编码都不是另一个字符编码的前缀 B. 出现频率高的字符通常被分配较短的编码 C. 编码过程中从根到叶子，左分支记 0、右分支记 1 D. 不同字符的编码长度一定相同

答案与解析
答案：D
解析：哈夫曼编码的核心正是"高频短码、低频长码"，因此不同字符的编码长度通常不同（这正是压缩的来源）。A、B、C 均为正确描述，前缀码保证了译码无歧义。
若哈夫曼树有 $n$ 个叶子节点，则其总节点数为（） A. $n+1$ B. $2n$ C. $2n-1$ D. $2n+1$

答案与解析
答案：C
解析：哈夫曼树每次合并减少一棵树、增加一个非叶子节点，最终只有 1 棵树；非叶子节点数 $= n-1$ ，故总节点数 $= n + (n-1) = 2n-1$ 。