c++哈夫曼树及哈夫曼编码

哈夫曼树（Huffman Tree）是一种特殊的二叉树，用于压缩数据，常用于数据传输和存储中。哈夫曼编码（Huffman Coding）则是一种基于哈夫曼树的编码方式，可以将字符或数据压缩成更短的二进制序列，从而节省存储空间和传输时间。

哈夫曼树的构建过程如下：

1. 统计每个字符出现的频率，并将它们作为叶子节点的权值。
2. 将所有权值列表按照从小到大的顺序排序。
3. 取出权值最小的两个节点（可以是叶子节点，也可以是非叶子节点）作为左右子节点，它们的父节点的权值为左右子节点的权值之和。
4. 将新生成的父节点插入到权值列表中，并按照权值大小重新排序。
5. 重复步骤3和步骤4，直到只剩下一个节点，此节点即为根节点，构成哈夫曼树。

构建完成后，每个字符对应的编码可以通过从根节点到叶子节点的路径上的0和1来表示。从根节点出发，左儿子表示为0，右儿子表示为1，最终到达叶子节点所经过的路径就是该字符的哈夫曼编码。

哈夫曼编码可以达到无损压缩的效果，因为每个字符都有唯一的编码，解压时只需根据编码从根节点出发，沿着路径找到对应的叶子节点即可还原原始字符。

相关问题

构建哈夫曼树及编码c++

哈夫曼树是一种带权路径长度最短的树，可以用于数据压缩等领域。构建哈夫曼树的过程可以通过递归实现，具体步骤如下：
1. 将所有权值存储在一个数组中，并按照从小到大的顺序排序。
2. 取出权值最小的两个节点，将它们合并成一个新节点，新节点的权值为两个节点的权值之和。
3. 将新节点插入到数组中，并按照权值从小到大的顺序排序。
4. 重复步骤2和3，直到数组中只剩下一个节点，即为哈夫曼树的根节点。

下面是C++实现哈夫曼树的代码示例：

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

// 定义哈夫曼树节点结构体
struct HuffmanNode {
    int weight; // 权值
    HuffmanNode* left; // 左子节点
    HuffmanNode* right; // 右子节点
    HuffmanNode(int w) : weight(w), left(nullptr), right(nullptr) {}
};

// 定义比较函数，用于优先队列中节点的排序
struct cmp {
    bool operator()(HuffmanNode* a, HuffmanNode* b) {
        return a->weight > b->weight;
    }
};

// 构建哈夫曼树
HuffmanNode* buildHuffmanTree(vector<int>& weights) {
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, cmp> pq;
    for (int w : weights) {
        pq.push(new HuffmanNode(w));
    }
    while (pq.size() > 1) {
        HuffmanNode* left = pq.top();
        pq.pop();
        HuffmanNode* right = pq.top();
        pq.pop();
        HuffmanNode* parent = new HuffmanNode(left->weight + right->weight);
        parent->left = left;        parent->right = right;
        pq.push(parent);
    }
    return pq.top();
}

// 生成哈夫曼编码
void generateHuffmanCode(HuffmanNode* root, string code, vector<string>& codes) {
    if (!root) {
        return;    }
    if (!root->left && !root->right) {
        codes.push_back(code);
        return;
    }
    generateHuffmanCode(root->left, code + "0", codes);
    generateHuffmanCode(root->right, code + "1", codes);
}

int main() {
    vector<int> weights = {5, 9, 12, 13, 16, 45};
    HuffmanNode* root = buildHuffmanTree(weights);
    vector<string> codes;
    generateHuffmanCode(root, "", codes);
    for (int i = 0; i < weights.size(); i++) {
        cout << "Weight: " << weights[i] << ", Code: " << codes[i] << endl;
    }
    return 0;
}

哈夫曼树与哈夫曼编码C++

哈夫曼树是一种带权路径长度最短的树，常用于数据压缩中的编码和解码。哈夫曼编码是一种前缀编码，即任何一个字符的编码都不是另一个字符编码的前缀。下面是C++实现哈夫曼树和哈夫曼编码的示例代码：

#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <unordered_map>
using namespace std;

// 哈夫曼树结点类
class HuffmanNode {
public:
    char ch; // 字符
    int freq; // 频率
    HuffmanNode* left; // 左子树
    HuffmanNode* right; // 右子树
    HuffmanNode(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
    ~HuffmanNode() {
        delete left;
        delete right;
    }
};

// 哈夫曼编码类
class HuffmanCoding {
public:
    // 构造函数
    HuffmanCoding(string s) : str(s) {
        for (char c : s) {
            freq[c]++;
        }
        buildHuffmanTree();
        buildHuffmanTable();
    }
    // 编码函数
    string encode() {
        string res = "";
        for (char c : str) {
            res += table[c];
        }
        return res;
    }
    // 解码函数
    string decode(string code) {
        string res = "";
        HuffmanNode* cur = root;
        for (char c : code) {
            if (c == '0') {
                cur = cur->left;
            } else {
                cur = cur->right;
            }
            if (cur->left == nullptr && cur->right == nullptr) {
                res += cur->ch;
                cur = root;
            }
        }
        return res;
    }
private:
    string str; // 待编码的字符串
    unordered_map<char, int> freq; // 字符频率
    unordered_map<char, string> table; // 哈夫曼编码表
    HuffmanNode* root; // 哈夫曼树根节点
    // 建立哈夫曼树
    void buildHuffmanTree() {
        priority_queue<HuffmanNode*, vector<HuffmanNode*>, [](HuffmanNode* a, HuffmanNode* b) { return a->freq > b->freq; }> 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);
        }
        root = pq.top();
    }
    // 建立哈夫曼编码表
    void buildHuffmanTable() {
        dfs(root, "");
    }
    void dfs(HuffmanNode* node, string code) {
        if (node->left == nullptr && node->right == nullptr) {
            table[node->ch] = code;
            return;
        }
        dfs(node->left, code + "0");
        dfs(node->right, code + "1");
    }
};

// 测试
int main() {
    string s = "hello world";
    HuffmanCoding hc(s);
    string code = hc.encode();
    cout << "编码结果：" << code << endl;
    string decode = hc.decode(code);
    cout << "解码结果：" << decode << endl;
    return 0;
}