Huffman树的数据结构设计
本节阅读量:
二叉树基础
树是一种重要的非线性数据结构，它由节点（Node）和边（Edge）组成：
A ← 根节点（Root）
/ \
B C ← 内部节点（Internal Node）
/ \ \
D E F ← 叶子节点（Leaf Node）
基本术语：
- 根节点：树的起点，没有父节点
- 叶子节点：没有子节点的节点
- 内部节点：至少有一个子节点的节点
- 父节点：某个节点的上一级节点
- 子节点：某个节点的下一级节点
- 深度（Depth）：从根节点到该节点的边数
- 高度（Height）：从该节点到最远叶子节点的边数
二叉树的表示方法
方法1：节点+指针
在C++中，我们使用结构体或类来表示节点：
1
2
3
4
5
|
struct TreeNode {
int data; // 存储数据
TreeNode* left; // 指向左子节点
TreeNode* right; // 指向右子节点
};
|
方法2：数组表示
对于完全二叉树（除了最后一层外，所有层的节点都是满的），可以用数组表示：
A(0)
/ \
B(1) C(2)
/ \
D(3) E(4)
数组表示：[A, B, C, D, E]
索引关系：
- 父节点：
(i-1)/2
- 左子节点：
2*i+1
- 右子节点：
2*i+2
本项目使用节点+指针的方式，因为：
- Huffman树不是完全二叉树
- 指针方式更灵活直观
递归遍历
二叉树的遍历主要有三种方式：
前序遍历（Preorder）：根 → 左 → 右
A
/ \
B C
/ \
D E
遍历结果：A B D E C
代码示例（前序遍历）：
1
2
3
4
5
6
7
|
void preorder(TreeNode* root) {
if (root == nullptr) return;
std::cout << root->data << " "; // 访问根节点
preorder(root->left); // 遍历左子树
preorder(root->right); // 遍历右子树
}
|
在Huffman编码中，我们主要使用前序遍历来保存和恢复树结构。
中序遍历（Inorder）：左 → 根 → 右
遍历结果：D B E A C
后序遍历（Postorder）：左 → 右 → 根
遍历结果：D E B C A
HuffmanNode结构体设计
Huffman树的节点需要存储以下信息：
1
2
3
4
5
6
|
struct HuffmanNode {
char data; // 存储字符（仅叶子节点有效）
int frequency; // 出现频率
HuffmanNode* left; // 左子节点指针
HuffmanNode* right; // 右子节点指针
};
|
为什么需要频率字段？
频率字段有两个作用：
作用1：构建树时排序
1
2
|
// 根据频率构建最小堆，频率小的节点优先合并
priority_queue<HuffmanNode*, ..., Compare> pq;
|
作用2：内部节点也需要频率
初始节点：
(2) (3) (2) (3)
a b c d
合并后创建内部节点：
(4) ← 新节点的频率是子节点频率之和
/ \
(2) (2)
a c
叶子节点 vs 内部节点的区别
叶子节点：
data 字段存储实际的字符（如 ‘a’, ‘b’ 等）left 和 right 都是 nullptr- 没有子节点
内部节点：
data 字段通常为 \0（空字符）left 和 right 不为 nullptr- 不存储实际字符，只用于连接子树
示例：
1
2
3
4
5
6
7
8
9
10
11
12
13
|
// 创建叶子节点
HuffmanNode* leaf = new HuffmanNode('a', 5);
// leaf->data = 'a'
// leaf->frequency = 5
// leaf->left = nullptr
// leaf->right = nullptr
// 创建内部节点
HuffmanNode* internal = new HuffmanNode(0, leftChild, rightChild);
// internal->data = '\0' (ASCII 0)
// internal->frequency = left->frequency + right->frequency
// internal->left 指向左子树
// internal->right 指向右子树
|
构造函数
为了让代码更清晰，我们添加构造函数：
1
2
3
4
5
6
7
|
// 叶子节点的构造函数
HuffmanNode(char data, int freq)
: data(data), frequency(freq), left(nullptr), right(nullptr) {}
// 内部节点的构造函数
HuffmanNode(int freq, HuffmanNode* l, HuffmanNode* r)
: data('\0'), frequency(freq), left(l), right(r) {}
|
使用示例：
1
2
3
4
5
6
|
// 创建叶子节点
HuffmanNode* nodeA = new HuffmanNode('a', 5);
HuffmanNode* nodeB = new HuffmanNode('b', 3);
// 创建内部节点
HuffmanNode* internal = new HuffmanNode(8, nodeA, nodeB);
|
优先队列（最小堆）
优先队列是一种特殊的队列，元素按照优先级出队：
普通队列：先进先出（FIFO）
输入：[3, 1, 4, 1, 5]
输出：[3, 1, 4, 1, 5]
优先队列：按优先级出队
输入：[3, 1, 4, 1, 5]
输出：[1, 1, 3, 4, 5] ← 最小的先出（最小堆）
std::priority_queue 介绍
1
2
3
4
5
6
7
|
#include <queue>
// 默认是最大堆（最大的先出）
std::priority_queue<int> pq; // [5, 4, 3, 1, 1]
// 最小堆（最小的先出）
std::priority_queue<int, std::vector<int>, std::greater<int>> pq; // [1, 1, 3, 4, 5]
|
基本操作：
1
2
3
4
5
|
pq.push(3); // 插入元素
pq.top(); // 获取队首元素（不删除）
pq.pop(); // 删除队首元素
pq.empty(); // 判断是否为空
pq.size(); // 获取元素个数
|
自定义比较器
对于Huffman树，我们需要按频率从小到大排序，所以需要自定义比较器：
1
2
3
4
5
|
struct Compare {
bool operator()(HuffmanNode* l, HuffmanNode* r) {
return l->frequency > r->frequency; // 注意：这里是大于号
}
};
|
为什么用大于号？
std::priority_queue 默认使用最大堆（最大的在队首）。为了实现最小堆，我们需要反转比较逻辑：
- 返回
l->frequency > r->frequency 表示：如果左边大于右边，左边优先级低
- 结果：最小的会在队首
使用示例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
std::priority_queue<HuffmanNode*, std::vector<HuffmanNode*>, Compare> pq;
// 创建节点
HuffmanNode* a = new HuffmanNode('a', 5);
HuffmanNode* b = new HuffmanNode('b', 3);
HuffmanNode* c = new HuffmanNode('c', 7);
// 插入优先队列
pq.push(a);
pq.push(b);
pq.push(c);
// 依次取出（按频率从小到大）
while (!pq.empty()) {
HuffmanNode* node = pq.top();
std::cout << "字符: " << node->data
<< ", 频率: " << node->frequency << std::endl;
pq.pop();
}
// 输出：
// 字符: b, 频率: 3
// 字符: a, 频率: 5
// 字符: c, 频率: 7
|
示例：使用优先队列构建简单数组
让我们用优先队列手动模拟Huffman树的构建过程：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
#include <iostream>
#include <queue>
#include <vector>
struct Compare {
bool operator()(int l, int r) {
return l > r; // 最小堆
}
};
int main() {
std::vector<int> data = {5, 3, 8, 2, 7};
std::priority_queue<int, std::vector<int>, Compare> pq;
// 将所有元素放入优先队列
for (int num : data) {
pq.push(num);
}
// 构建树（合并最小的两个）
while (pq.size() > 1) {
int a = pq.top(); pq.pop();
int b = pq.top(); pq.pop();
int sum = a + b;
std::cout << "合并 " << a << " 和 " << b << " = " << sum << std::endl;
pq.push(sum);
}
std::cout << "最终根节点频率: " << pq.top() << std::endl;
return 0;
}
|
输出：
合并 2 和 3 = 5
合并 5 和 5 = 10
合并 7 和 8 = 15
合并 10 和 15 = 25
最终根节点频率: 25
这就是Huffman树构建的核心思想！
HuffmanCoder类框架
类的封装原则
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class HuffmanCoder {
private:
// 私有成员：内部实现细节
HuffmanNode* root;
std::unordered_map<char, std::string> huffmanCode;
public:
// 公有接口：对外提供的服务
HuffmanCoder();
~HuffmanCoder();
bool compress(const std::string& inputFile, const std::string& outputFile);
bool decompress(const std::string& inputFile, const std::string& outputFile);
};
|
封装的好处：
- 隐藏实现细节：用户不需要知道树是如何构建的
- 提供清晰接口：只需要调用
compress 和 decompress
- 便于维护：内部实现改变不影响外部调用
构造函数
1
2
3
4
|
HuffmanCoder::HuffmanCoder() : root(nullptr) {
// 初始化成员变量
// root 初始化为 nullptr，表示树还没构建
}
|
为什么需要初始化列表？
1
2
3
4
5
6
7
|
// 方式1：使用初始化列表（推荐）
HuffmanCoder::HuffmanCoder() : root(nullptr) {}
// 方式2：在构造函数体内赋值
HuffmanCoder::HuffmanCoder() {
root = nullptr; // 先默认初始化，再赋值，效率稍低
}
|
初始化列表更高效，尤其是对于类类型的成员变量。
析构函数
1
2
3
|
HuffmanCoder::~HuffmanCoder() {
// 清理内存，下一节实现
}
|
析构函数的作用：
- 当对象被销毁时自动调用
- 释放动态分配的内存
- 防止内存泄漏
示例：
1
2
3
4
5
|
{
HuffmanCoder coder; // 构造函数调用
coder.compress("input.txt", "output.huf");
// coder.compress(...) 内部构建了树
} // 离开作用域，析构函数自动调用，清理树内存
|
类的成员变量
1
2
3
4
5
6
|
private:
HuffmanNode* root; // Huffman树的根节点
// 编码表：字符 → Huffman编码
std::unordered_map<char, std::string> huffmanCode;
// 例如：{'a': "0", 'b': "10", 'c': "11"}
|
为什么用 unordered_map 而不是 map？
std::unordered_map：哈希表，平均 O(1) 查找std::map：红黑树，O(log n) 查找
对于字符编码查找，用 unordered_map 更快。
代码实现
更新 huffman.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
#ifndef HUFFMAN_H
#define HUFFMAN_H
#include <string>
#include <unordered_map>
#include <vector>
#include <queue>
#include <fstream>
// Huffman树节点
struct HuffmanNode {
char data; // 存储字符
int frequency; // 出现频率
HuffmanNode* left; // 左子节点
HuffmanNode* right; // 右子节点
// 叶子节点构造函数
HuffmanNode(char data, int freq)
: data(data), frequency(freq), left(nullptr), right(nullptr) {}
// 内部节点构造函数
HuffmanNode(int freq, HuffmanNode* l, HuffmanNode* r)
: data('\0'), frequency(freq), left(l), right(r) {}
};
// 用于优先队列的比较器
struct Compare {
bool operator()(HuffmanNode* l, HuffmanNode* r) {
return l->frequency > r->frequency; // 最小堆
}
};
class HuffmanCoder {
private:
HuffmanNode* root;
std::unordered_map<char, std::string> huffmanCode;
// （后续会添加更多方法）
public:
HuffmanCoder();
~HuffmanCoder();
// 压缩文件
bool compress(const std::string& inputFile, const std::string& outputFile);
// 解压文件
bool decompress(const std::string& inputFile, const std::string& outputFile);
};
#endif // HUFFMAN_H
|
更新 huffman.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
#include "huffman.h"
#include <iostream>
HuffmanCoder::HuffmanCoder() : root(nullptr) {}
HuffmanCoder::~HuffmanCoder() {
std::cout << "✓ HuffmanCoder对象自动销毁，内存已清理" << std::endl;
}
bool HuffmanCoder::compress(const std::string& inputFile, const std::string& outputFile) {
std::cout << "压缩功能将在下一章实现！" << std::endl;
return true;
}
bool HuffmanCoder::decompress(const std::string& inputFile, const std::string& outputFile) {
std::cout << "解压功能将在后续章节实现！" << std::endl;
return true;
}
|
更新 main.cpp（测试代码）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
#include "huffman.h"
#include <iostream>
#include <unordered_map>
int main(int argc, char* argv[]) {
std::cout << "=== Huffman编码压缩工具测试 ===" << std::endl;
// 测试：构造函数和析构函数
{
HuffmanCoder coder;
std::cout << "✓ HuffmanCoder对象创建成功" << std::endl;
}
return 0;
}
|
预期输出：
=== Huffman编码压缩工具测试 ===
✓ HuffmanCoder对象创建成功
✓ HuffmanCoder对象自动销毁，内存已清理
小结与练习
本章内容：
-
二叉树基础：
- 理解树的基本概念（根节点、叶子节点、内部节点）
- 掌握三种遍历方式（前序、中序、后序）
- 学会递归遍历的实现
-
HuffmanNode结构体：
- 设计了包含
data、frequency、left、right 的节点
- 理解叶子节点和内部节点的区别
- 掌握内存管理和析构函数的使用
-
优先队列：
- 理解最小堆的概念和用途
- 学会使用
std::priority_queue
- 掌握自定义比较器
-
HuffmanCoder类框架：
- 设计了类的公有和私有接口
- 实现了构造函数和析构函数
练习1：理解二叉树遍历
给定以下二叉树：
A
/ \
B C
/ \
D E
请写出：
- 前序遍历结果
- 中序遍历结果
- 后序遍历结果
练习2：优先队列操作
编写程序，创建一个最小堆，插入数字 [5, 2, 8, 1, 9, 3]，然后依次输出队首元素并删除，直到队列为空。
练习3：手动构建Huffman树
对于字符串 "aaabbc"，手动构建Huffman树，并写出每个节点的构造过程。
