L6_02 基于树的编码

一、格雷编码

1.1 格雷编码的定义

格雷编码（Gray Code）是一种二进制编码方式，相邻两个数的二进制表示只有一位不同。

1.2 格雷编码的特点

• 任意两个相邻的编码只有一位不同
• 首尾两个编码也只有一位不同（循环特性）
• 减少数字变化时产生的错误

1.3 二进制转格雷码

int binaryToGray(int binary) {
    return binary ^ (binary >> 1);
}

1.4 格雷码转二进制

int grayToBinary(int gray) {
    int binary = gray;
    while (gray >>= 1) {
        binary ^= gray;
    }
    return binary;
}

1.5 生成 n 位格雷码

vector<int> generateGrayCode(int n) {
    vector<int> result;
    for (int i = 0; i < (1 << n); i++) {
        result.push_back(i ^ (i >> 1));
    }
    return result;
}

1.6 格雷码的应用

• 数字通信中的错误检测
• 旋转编码器
• 卡诺图化简

二、哈夫曼编码

2.1 哈夫曼编码的定义

哈夫曼编码是一种变长前缀编码，根据字符出现频率构建最优二叉树，实现数据压缩。

2.2 哈夫曼编码的特点

• 前缀编码：任何一个编码都不是另一个编码的前缀
• 最优性：平均码长最短

2.3 哈夫曼编码的构建步骤

1. 统计每个字符的出现频率
2. 以每个字符作为叶子节点，构建哈夫曼树
3. 从根节点到叶子节点，左分支记为0，右分支记为1
4. 每条路径即为对应字符的编码

2.4 哈夫曼编码实现

#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>
#include <string>

using namespace std;

struct HuffmanNode {
    char ch;
    int freq;
    HuffmanNode *left, *right;
    HuffmanNode(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
};

struct Compare {
    bool operator()(HuffmanNode* a, HuffmanNode* b) {
        return a->freq > b->freq;
    }
};

void generateCodes(HuffmanNode* root, string code, unordered_map<char, string>& codes) {
    if (!root) return;
    if (!root->left && !root->right) {
        codes[root->ch] = code;
        return;
    }
    generateCodes(root->left, code + "0", codes);
    generateCodes(root->right, code + "1", codes);
}

unordered_map<char, string> buildHuffmanCode(const string& text) {
    unordered_map<char, int> freq;
    for (char c : text) freq[c]++;
    
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> pq;
    for (auto& p : freq) {
        pq.push(new HuffmanNode(p.first, p.second));
    }
    
    while (pq.size() > 1) {
        HuffmanNode* left = pq.top(); pq.pop();
        HuffmanNode* right = pq.top(); pq.pop();
        HuffmanNode* parent = new HuffmanNode('\0', left->freq + right->freq);
        parent->left = left;
        parent->right = right;
        pq.push(parent);
    }
    
    unordered_map<char, string> codes;
    generateCodes(pq.top(), "", codes);
    return codes;
}

string encode(const string& text, const unordered_map<char, string>& codes) {
    string encoded;
    for (char c : text) {
        encoded += codes.at(c);
    }
    return encoded;
}

2.5 哈夫曼编码示例

假设字符频率：

• 'a': 5
• 'b': 9
• 'c': 12
• 'd': 13
• 'e': 16
• 'f': 45

生成的哈夫曼编码：

• 'f': 0
• 'c': 100
• 'd': 101
• 'a': 1100
• 'b': 1101
• 'e': 111

2.6 哈夫曼编码的应用

• 文件压缩（如ZIP、JPEG）
• 数据传输中的编码
• 信息论中的最优编码