树的序列化与反序列化

什么是序列化

序列化（Serialization）：将对象或数据结构转换为可以存储或传输的格式（如字节流）。

反序列化（Deserialization）：从序列化后的格式中恢复出原始的对象或数据结构。

为什么需要序列化？

1. 持久化存储：将数据保存到文件或数据库
2. 网络传输：在网络上传输数据
3. 跨进程通信：在不同进程间传递数据

常见序列化方法：

本项目使用自定义二进制序列化，因为：

• 需要最小化文件大小
• 需要高性能
• 不需要跨语言兼容

Huffman树的序列化设计

前序遍历 + 标记法

我们使用前序遍历 + 标记法来序列化Huffman树：

标记规则：
- '1' 表示叶子节点，后跟字符数据
- '0' 表示内部节点，后跟左右子树

图示序列化过程

示例树：

        root
       /    \
     A(5)   B(7)
    /   \   /  \
  a(2) c(2) b(3) d(4)

序列化过程（前序遍历）：

1. 访问 root（内部节点）
   写入：'0'

2. 递归左子树 A（内部节点）
   写入：'0'
   
3. 递归左子树 a（叶子节点）
   写入：'1', 'a'
   
4. 递归右子树 c（叶子节点）
   写入：'1', 'c'
   
5. 递归右子树 B（内部节点）
   写入：'0'
   
6. 递归左子树 b（叶子节点）
   写入：'1', 'b'
   
7. 递归右子树 d（叶子节点）
   写入：'1', 'd'

最终序列化结果：

0 0 1 a 1 c 0 1 b 1 d

保存树结构

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

void HuffmanCoder::writeTree(std::ofstream& outFile, HuffmanNode* node) {
    if (node == nullptr) {
        return;
    }
    
    // 如果是叶子节点
    if (!node->left && !node->right) {
        outFile.put('1');        // 标记为叶子节点
        outFile.put(node->data); // 写入字符
    } 
    // 如果是内部节点
    else {
        outFile.put('0');            // 标记为内部节点
        writeTree(outFile, node->left);   // 递归保存左子树
        writeTree(outFile, node->right);  // 递归保存右子树
    }
}

判断叶子节点

1

if (!node->left && !node->right)

叶子节点的特征：

• left 指针为 nullptr
• right 指针为 nullptr

写入标记和数据

1
2

outFile.put('1');        // 写入标记字节
outFile.put(node->data); // 写入字符数据（1字节）

示例：

• 叶子节点存储字符 ‘a’，写入：[0x31, 0x61]（‘1’, ‘a’）
• 叶子节点存储字符 ‘\n’，写入：[0x31, 0x0A]（‘1’, 换行符）

递归保存子树

1
2

writeTree(outFile, node->left);   // 先保存左子树
writeTree(outFile, node->right);  // 再保存右子树

问题：字符 ‘0’ 和 ‘1’ 会冲突么？

当前实现使用字符 ‘0’（ASCII 48）和 ‘1’（ASCII 49）作为标记。

问题场景：如果文件中包含字符 ‘0’ 或 ‘1’，会发生混淆吗？

答案：不会混淆！

原因：

• 标记是字符 ‘0’/‘1’（ASCII 48/49）
• 标记后面总是紧跟特定的数据结构
• 读取时先读取标记，再根据标记决定后续操作

读取树结构

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

HuffmanNode* HuffmanCoder::readTree(std::ifstream& inFile) {
    char marker = inFile.get();
    
    // 如果是叶子节点标记
    if (marker == '1') {
        // 读取字符数据
        char data = inFile.get();
        return new HuffmanNode(data, 0);
    } 
    // 如果是内部节点标记
    else {
        // 递归读取左子树
        HuffmanNode* left = readTree(inFile);
        // 递归读取右子树
        HuffmanNode* right = readTree(inFile);
        // 创建内部节点
        return new HuffmanNode(0, left, right);
    }
}

与 writeTree 的对应关系

反序列化过程示例

序列化数据：0 0 1 a 1 c 0 1 b 1 d

反序列化过程：

1. 读取 marker = '0'
   → 内部节点
   → 递归读取左子树

2. 读取 marker = '0'
   → 内部节点
   → 递归读取左子树

3. 读取 marker = '1'
   → 叶子节点
   → 读取 data = 'a'
   → 返回节点 a(2)

4. 读取 marker = '1'
   → 叶子节点
   → 读取 data = 'c'
   → 返回节点 c(2)
   → 返回节点 A(5) = [a(2), c(2)]

5. 读取 marker = '0'
   → 内部节点
   → 递归读取左子树

6. 读取 marker = '1'
   → 叶子节点
   → 读取 data = 'b'
   → 返回节点 b(3)

7. 读取 marker = '1'
   → 叶子节点
   → 读取 data = 'd'
   → 返回节点 d(4)
   → 返回节点 B(7) = [b(3), d(4)]
   → 返回节点 root(12) = [A(5), B(7)]

最终还原出完整的树结构！

文件格式设计

完整文件结构

┌─────────────────────────────────────────┐
│ [原始字符数]          8字节             │
├─────────────────────────────────────────┤
│ [Huffman树结构]      可变长度           │
│  - 使用前序遍历+标记法序列化             │
├─────────────────────────────────────────┤
│ [Padding]            1字节              │
│  - 最后一个字节补了多少0               │
├─────────────────────────────────────────┤
│ [压缩数据]            可变长度           │
│  - 二进制编码的字节数组                 │
└─────────────────────────────────────────┘

1. 原始字符数（8字节）

1
2

size_t originalSize = encodedString.length();
outFile.write(reinterpret_cast<const char*>(&originalSize), sizeof(size_t));

作用：

• 解压时知道要解码多少个字符
• 防止读取padding的无效数据

为什么是8字节？

• size_t 在64位系统上通常是8字节（64位）
• 可以表示非常大的文件（最大 2^64 字节）

2. Huffman树结构（可变长度）

1

writeTree(outFile, root);

大小估计：

• 假设有256个不同字符
• 每个节点：1字节标记 + 1字节字符 = 2字节
• 内部节点：1字节标记
• 总大小约：256 × 2 + 255 × 1 ≈ 767字节

3. Padding（1字节）

1
2

int padding = (8 - (encodedString.length() % 8)) % 8;
outFile.put(static_cast<char>(padding));

作用：

• 记录最后一个字节补了多少0
• 解压时需要根据padding去掉无效的0

4. 压缩数据（可变长度）

1
2
3

std::vector<unsigned char> bytes;
stringToBytes(encodedString, bytes);
outFile.write(reinterpret_cast<const char*>(bytes.data()), bytes.size());

小结与练习

本章内容：

1. 序列化概念：

   • 理解序列化和反序列化的含义
   • 知道常见的序列化方法
   • 理解为什么选择自定义二进制序列化

2. 树的序列化：

   • 掌握前序遍历+标记法
   • 理解叶子节点和内部节点的区分
   • 能够手动序列化和反序列化树

3. 文件格式设计：

   • 理解完整文件的四个部分
   • 知道每个部分的作用
   • 能够设计类似的文件格式

练习1：手动序列化

给定以下树结构，写出序列化结果：

      root
     /    \
   A(3)   B(5)
          /  \
        C(2)  D(3)

练习2：反序列化

给定序列化数据 0 0 1 a 0 1 b 1 c 1 d，画出对应的树结构。

练习3：文件大小计算

假设：

• 原始文件有100个不同字符
• Huffman树有256个节点
• 压缩数据有10000个字节

计算压缩文件的总大小。

练习4：改进标记

如何修改 writeTree 和 readTree，使用bit 0和1（而不是字符'0’和'1’）作为标记。