十三、哈夫曼树

哈夫曼树构建演示

双击节点编辑 | 左键空白处创建 | 右键删除

速度

双击节点编辑 | 左键空白处创建 | 右键删除

当前森林 (优先队列)

空

算法伪代码

// 1. 初始化 function Huffman(nodes) { let forest = [...nodes]; forest.sort((a,b) => a.weight - b.weight);

// 2. 循环构建 while (forest.length > 1) { // 取出最小的两个 const min1 = forest.shift(); const min2 = forest.shift();

// 3. 合并并放回 const parent = { weight: min1.weight + min2.weight, left: min1, right: min2 }; forest.push(parent); forest.sort((a,b) => a.weight - b.weight); }

// 4. 结束 return forest[0]; }

1、 哈夫曼树定义

定义： 哈夫曼树，又称最优二叉树（Optimal Binary Tree）。它是指在给定一组带有权值的叶子结点中，构造出的带权路径长度（WPL）最小的二叉树。

简单理解： 如果我们把“权值”看作出现的频率，哈夫曼树的核心思想是：让出现频率高的结点离根节点越近（编码越短），出现频率低的结点离根节点越远（编码越长），从而使整棵树的加权成本最低。

---

2、 核心术语（基础概念）

要理解哈夫曼树，必须先搞懂以下几个指标：

1. 路径（Path）：从一个结点到另一个结点之间的分支序列。
2. 路径长度（Path Length）：路径上分支（边）的数目。
   • 若根节点层数为1，则根到第 $L$ 层结点的路径长度为 $L-1$。
3. 权（Weight）：给树中结点赋予的一个具有某种物理意义的数值（如字符出现的次数、频率）。
4. 结点的带权路径长度：该结点的权值 $\times$ 该结点到根节点的路径长度。
5. 树的带权路径长度（WPL - Weighted Path Length）：树中所有叶子结点的带权路径长度之和。 $$ WPL = \sum_{i=1}^{n} (w_i \times l_i) $$
   • $w_i$：第 $i$ 个叶子结点的权值。
   • $l_i$：第 $i$ 个叶子结点的路径长度。

---

3、 哈夫曼树的构建算法

哈夫曼树的构造使用的是贪心算法（Greedy Algorithm）策略。

构造步骤： 假设有 $n$ 个权值为 $\{w_1, w_2, ..., w_n\}$ 的结点：

1. 森林化：将这 $n$ 个结点看作 $n$ 棵只有根节点的二叉树集合。
2. 选最小：在集合中选取权值最小的两棵树。
3. 合并：将这两棵树作为左、右子树，构造一棵新的二叉树。新二叉树根节点的权值为其左、右子树根节点权值之和。
4. 删除与加入：从集合中删除刚才选中的两棵树，并将新生成的树加入集合。
5. 重复：重复步骤 2-4，直到集合中只剩下一棵树为止。这棵树就是哈夫曼树。

图解示例： 假设给定权值集合：{2, 3, 6, 9}

1. 选最小的 2 和 3，合并得到新结点 5 (2+3)。
   • 当前集合：{5, 6, 9} （注：2和3已在树下层）
2. 选最小的 5 和 6，合并得到新结点 11 (5+6)。
   • 当前集合：{11, 9}
3. 选最小的 9 和 11，合并得到新结点 20 (9+11)。
   • 当前集合：{20}
4. 结束。根节点为 20。

---

4、 哈夫曼编码（Huffman Coding）

这是哈夫曼树最著名的应用。

1. 为什么需要哈夫曼编码？

在计算机中，标准的 ASCII 码是等长编码（每个字符都占 8 bits）。但在实际文本中，某些字符（如 a, e）出现频率很高，而某些（如 z, q）很低。 如果给高频字符短编码，低频字符长编码，就能大大压缩数据体积。这叫变长编码。

2. 前缀码（Prefix Code）

变长编码面临一个问题：歧义。 例如：A: 0, B: 1, C: 01。收到 01 时，是解释为 AB 还是 C？ 解决方案：哈夫曼编码是一种前缀码。

• 定义：任何一个字符的编码都不是另一个字符编码的前缀。
• 实现：在哈夫曼树中，字符都在叶子结点上，路径不可能重叠，天然满足前缀码特性。

3. 编码规则

• 构造好哈夫曼树后，规定：
  • 左分支标记为 0
  • 右分支标记为 1
• 从根节点遍历到叶子结点，经过的路径数字序列就是该字符的编码。

---

5、 哈夫曼树的重要性质

1. 结点总数： 如果有 $n$ 个叶子结点，那么哈夫曼树的总结点数为 $2n - 1$。
   • 解释：每次合并减少2个结点，增加1个结点（净减1）。最后剩1个，共进行了 $n-1$ 次合并，产生 $n-1$ 个新结点。$n + (n-1) = 2n-1$。
2. 没有度为 1 的结点： 哈夫曼树中，结点的度要么是 0（叶子），要么是 2（分支结点）。它是严格的正则二叉树。
3. 最优性： 权值越大的结点，离根节点越近；权值越小的结点，离根节点越远。
4. 不唯一性： 虽然 WPL 最小值是唯一的，但哈夫曼树的形态不唯一（例如权值相同时，谁做左子树谁做右子树没有规定）。

---

6、 代码实现（C 版）

在实际编程中，我们通常使用优先队列（最小堆）来实现，因为需要频繁取出最小的两个元素。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

// --- 数据结构定义 ---

// 哈夫曼树结点
typedef struct {
    int weight;     // 权值
    int parent;     // 父结点下标，0表示无父结点
    int lchild;     // 左孩子下标
    int rchild;     // 右孩子下标
    char data;      // 存储的字符（可选，用于展示）
} HTNode, *HuffmanTree;

// 存储哈夫曼编码表 (指针数组)
typedef char **HuffmanCode;

// --- 辅助函数：选择最小的两个结点 ---

/**
 * 在 HT[1...end] 中选择两个 parent 为 0 且 weight 最小的结点
 * 将它们的下标分别赋值给 s1 和 s2
 */
void Select(HuffmanTree HT, int end, int *s1, int *s2) {
    int min1 = INT_MAX; // 最小值
    int min2 = INT_MAX; // 次小值
    *s1 = 0;
    *s2 = 0;

    // 1. 找到最小的 s1
    for (int i = 1; i <= end; i++) {
        if (HT[i].parent == 0 && HT[i].weight < min1) {
            min1 = HT[i].weight;
            *s1 = i;
        }
    }

    // 2. 找到次小的 s2
    for (int i = 1; i <= end; i++) {
        // 注意：要排除掉刚才选中的 s1
        if (HT[i].parent == 0 && HT[i].weight < min2 && i != *s1) {
            min2 = HT[i].weight;
            *s2 = i;
        }
    }
}

// --- 核心逻辑：构建哈夫曼树 ---

/**
 * 创建哈夫曼树
 * HT: 指向哈夫曼树的指针
 * HC: 指向哈夫曼编码表的指针
 * weights: 权值数组
 * data: 字符数组
 * n: 叶子结点的数量
 */
void CreateHuffmanTree(HuffmanTree *HT, int *weights, char *data, int n) {
    if (n <= 1) return;

    int m = 2 * n - 1; // 总结点数
    
    // 1. 初始化分配内存 (从下标1开始使用，所以分配 m+1)
    *HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode));

    // 2. 初始化前 n 个元素（叶子结点）
    for (int i = 1; i <= n; i++) {
        (*HT)[i].weight = weights[i - 1];
        (*HT)[i].data = data[i - 1];
        (*HT)[i].parent = 0;
        (*HT)[i].lchild = 0;
        (*HT)[i].rchild = 0;
    }

    // 3. 初始化后 m-n 个元素（非叶子结点）
    for (int i = n + 1; i <= m; i++) {
        (*HT)[i].weight = 0;
        (*HT)[i].parent = 0;
        (*HT)[i].lchild = 0;
        (*HT)[i].rchild = 0;
        (*HT)[i].data = '\0'; // 中间结点没有字符
    }

    // 4. 构建树：循环 n-1 次，每次合并两个
    int s1, s2;
    for (int i = n + 1; i <= m; i++) {
        // 在 1 到 i-1 范围内找两个最小的
        Select(*HT, i - 1, &s1, &s2);

        // 建立关系
        (*HT)[s1].parent = i;
        (*HT)[s2].parent = i;
        
        (*HT)[i].lchild = s1;
        (*HT)[i].rchild = s2;
        (*HT)[i].weight = (*HT)[s1].weight + (*HT)[s2].weight;
        
        // 打印构建过程（调试用）
        // printf("合并结点: %d(%d) 和 %d(%d) -> 新结点 %d(%d)\n", 
        //        s1, (*HT)[s1].weight, s2, (*HT)[s2].weight, i, (*HT)[i].weight);
    }
}

// --- 核心逻辑：生成哈夫曼编码 ---

/**
 * 从叶子到根逆向求每个字符的哈夫曼编码
 */
void CreateHuffmanCode(HuffmanTree HT, HuffmanCode *HC, int n) {
    // 分配 n+1 个字符串指针
    *HC = (HuffmanCode)malloc((n + 1) * sizeof(char *));
    
    // 临时空间用于存储当前字符的编码，最长路径不会超过 n
    char *cd = (char *)malloc(n * sizeof(char));
    cd[n - 1] = '\0'; // 字符串结束符

    // 遍历每一个叶子结点
    for (int i = 1; i <= n; i++) {
        int start = n - 1; // 编码结束位置
        int c = i;         // 当前结点下标
        int f = HT[i].parent; // 父结点下标

        // 从叶子向上回溯直到根节点 (parent == 0)
        while (f != 0) {
            start--;
            if (HT[f].lchild == c) {
                cd[start] = '0'; // 左孩子为 0
            } else {
                cd[start] = '1'; // 右孩子为 1
            }
            // 继续向上
            c = f;
            f = HT[f].parent;
        }

        // 为第 i 个字符分配具体的存储空间，并复制编码
        (*HC)[i] = (char *)malloc((n - start) * sizeof(char));
        strcpy((*HC)[i], &cd[start]);
    }

    free(cd); // 释放临时空间
}

// --- 测试主函数 ---

int main() {
    HuffmanTree HT;
    HuffmanCode HC;

    // 测试数据
    // 字符集: {A, B, C, D, E}
    // 权值集: {5, 2, 9, 4, 8}
    char data[] = {'A', 'B', 'C', 'D', 'E'};
    int weights[] = {5, 2, 9, 4, 8};
    int n = sizeof(weights) / sizeof(weights[0]);

    printf("=== 哈夫曼树构建与编码 ===\n");
    printf("原始数据与权值:\n");
    for(int i=0; i<n; i++) {
        printf("%c: %d  ", data[i], weights[i]);
    }
    printf("\n\n");

    // 1. 构建
    CreateHuffmanTree(&HT, weights, data, n);

    // 2. 编码
    CreateHuffmanCode(HT, &HC, n);

    // 3. 输出结果
    printf("--- 生成的哈夫曼编码 ---\n");
    printf("字符\t权值\t编码\n");
    for (int i = 1; i <= n; i++) {
        printf("%c\t%d\t%s\n", HT[i].data, HT[i].weight, HC[i]);
    }

    // 4. 计算 WPL (验证)
    int wpl = 0;
    for (int i = 1; i <= n; i++) {
        wpl += HT[i].weight * strlen(HC[i]);
    }
    printf("\n带权路径长度 (WPL): %d\n", wpl);

    // 5. 内存释放
    free(HT);
    for (int i = 1; i <= n; i++) {
        free(HC[i]);
    }
    free(HC);

    return 0;
}

---

7、 复杂度分析

假设有 $N$ 个字符（叶子结点）：

1. 时间复杂度：

   • 统计频率：$O(Length\_of\_Text)$。
   • 堆操作：每次插入删除是 $O(\log N)$。
   • 构建树过程：进行 $N-1$ 次合并，每次涉及堆操作，所以是 $O(N \log N)$。
   • 如果是已经排序好的数组，可以是 $O(N)$。

2. 空间复杂度：

   • 需要存储树结构（$2N-1$ 个结点）和编码表，复杂度为 $O(N)$。

8、 总结

知识点	关键内容
核心目标	最小化带权路径长度 (WPL)。
构造策略	贪心算法：每次合并权值最小的两个。
应用场景	无损数据压缩（Huffman Coding）。
编码特性	前缀码（无歧义），高频短码，低频长码。
树的形态	只有度为0和2的结点，总结点数 $2n-1$。