编写类及成员函数 构造哈夫曼树 实现求哈夫曼编码及解码的实现 c++

哈夫曼树是一种用于数据压缩的树形结构，通过构造最优的二叉树来实现。在C语言中，可以通过编写类及成员函数来实现哈夫曼树的构建和哈夫曼编码及解码的实现。

首先，需要定义一个节点的结构体，包括字符值、权重值和指向左右子节点的指针。然后，定义一个哈夫曼树的类，包含构建哈夫曼树的函数、求哈夫曼编码的函数和解码的函数。

在构建哈夫曼树的函数中，可以通过构建最小堆来选择权重最小的两个节点，然后将这两个节点合并为一个新节点，将新节点的权重值设置为两个节点的权重值之和，并将新节点插入最小堆中。重复这个过程，直到最小堆中只剩下一个节点，即为哈夫曼树的根节点。

在求哈夫曼编码的函数中，可以通过遍历哈夫曼树，记录路径上的编码。对于左子节点的路径，可以设置编码值为0，对于右子节点的路径，可以设置编码值为1。最终，将每个字符的编码存储在一个哈希表中，以字符值作为键，编码作为值。

在解码函数中，可以通过遍历哈夫曼树的路径，根据编码的值来判断是向左还是向右，直到叶子节点，即可找到对应的字符值。

总的来说，通过定义节点的结构体、编写构建哈夫曼树的函数、求哈夫曼编码的函数和解码的函数，可以实现哈夫曼树的构建和哈夫曼编码及解码的功能。这样就可以对数据进行压缩和解压缩，提高数据的传输效率。

相关问题

c++构造哈夫曼树并实现哈夫曼编码

好的，我可以帮你解答这个问题。

首先，哈夫曼树是一种用于编码的树形结构，它可以根据字符出现的频率构建一种最优的编码方式，使得编码后的数据长度最短。

构建哈夫曼树的基本步骤如下：

1. 统计每个字符出现的频率，并将它们按照频率从小到大排序。
2. 取出当前频率最小的两个字符，将它们组成一个新的节点，且该节点的权值为两个字符的频率之和。
3. 将新节点插入到频率表中，并删除原来的两个字符，然后重新排序。
4. 重复步骤2和3，直到只剩下一个节点，这个节点就是哈夫曼树的根节点。

构建好哈夫曼树后，就可以对每个字符进行编码了。编码的规则是，对于哈夫曼树中的每个叶子节点，从根节点到该节点的路径上的左右分支分别用0和1表示，这就是该字符的哈夫曼编码。

这里是一个 C++ 实现的示例代码：

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

using namespace std;

// 定义哈夫曼树的节点结构体
struct HuffmanNode {
    char ch; // 字符
    int freq; // 频率
    HuffmanNode* left; // 左子节点
    HuffmanNode* 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; // 按照频率从小到大排序
    }
};

// 统计字符频率
unordered_map<char, int> countFreq(string str) {
    unordered_map<char, int> freq;
    for(char c: str) {
        freq[c]++;
    }
    return freq;
}

// 构建哈夫曼树
HuffmanNode* buildHuffmanTree(unordered_map<char, int> freq) {
    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);
    }
    // 最后队列中只剩下一个节点，它就是哈夫曼树的根节点
    return pq.top();
}

// 递归遍历哈夫曼树，生成每个字符的编码
void generateHuffmanCode(HuffmanNode* root, string code, unordered_map<char, string>& huffmanCode) {
    if(!root) return;
    // 如果是叶子节点，就记录下该字符的哈夫曼编码
    if(!root->left && !root->right) {
        huffmanCode[root->ch] = code;
        return;
    }
    // 分别遍历左右子树，并在编码后面加上0或1
    generateHuffmanCode(root->left, code + "0", huffmanCode);
    generateHuffmanCode(root->right, code + "1", huffmanCode);
}

// 对给定字符串进行哈夫曼编码
string huffmanEncode(string str) {
    unordered_map<char, int> freq = countFreq(str);
    HuffmanNode* root = buildHuffmanTree(freq);
    unordered_map<char, string> huffmanCode;
    generateHuffmanCode(root, "", huffmanCode);
    string encodedStr;
    for(char c: str) {
        encodedStr += huffmanCode[c];
    }
    return encodedStr;
}

// 解码给定的哈夫曼编码
string huffmanDecode(string encodedStr, HuffmanNode* root) {
    string decodedStr;
    HuffmanNode* cur = root;
    for(char c: encodedStr) {
        if(c == '0') {
            cur = cur->left;
        } else {
            cur = cur->right;
        }
        if(!cur->left && !cur->right) {
            decodedStr += cur->ch;
            cur = root;
        }
    }
    return decodedStr;
}

int main() {
    string str = "hello world";
    string encodedStr = huffmanEncode(str);
    cout << "Encoded string: " << encodedStr << endl;
    HuffmanNode* root = buildHuffmanTree(countFreq(str));
    string decodedStr = huffmanDecode(encodedStr, root);
    cout << "Decoded string: " << decodedStr << endl;
    return 0;
}

上述代码中，我们首先定义了一个哈夫曼树节点的结构体 `HuffmanNode`，其中包含字符、频率、左右子节点等信息。然后，我们通过 `countFreq` 函数统计每个字符出现的频率，并通过 `buildHuffmanTree` 函数构建哈夫曼树。在构建哈夫曼树的过程中，我们使用了一个优先队列来存储每个字符的节点，并按照频率从小到大排序。

构建好哈夫曼树后，我们通过递归遍历树的方式生成每个字符的哈夫曼编码，并记录在一个哈希表中。最后，我们使用 `huffmanEncode` 函数对给定字符串进行编码，使用 `huffmanDecode` 函数对编码后的字符串进行解码，恢复原来的字符串。

用C++完成输入n个叶子结点的权值构造哈夫曼树；根据哈夫曼树构造哈夫曼编码，并对密文完成解码工作

好的，以下是用C++实现输入n个叶子节点的权值构造哈夫曼树，并根据哈夫曼树构造哈夫曼编码，最后对密文进行解码的代码：

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

// 哈夫曼树节点
struct HuffmanNode {
    int val; // 权值
    char ch; // 叶子节点的字符
    HuffmanNode *left, *right; // 左右子节点
    HuffmanNode(int val, char ch = '\0', HuffmanNode *left = nullptr, HuffmanNode *right = nullptr) :
        val(val), ch(ch), left(left), right(right) {}
};

// 哈夫曼编码表
unordered_map<char, string> huffmanCode;

// 构造哈夫曼树
HuffmanNode* buildHuffmanTree(vector<int>& weights) {
    auto cmp = [](HuffmanNode* a, HuffmanNode* b) {
        return a->val > b->val;
    };
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, decltype(cmp)> pq(cmp);
    for (int i = 0; i < weights.size(); ++i) {
        pq.push(new HuffmanNode(weights[i], (char)('A' + i)));
    }
    while (pq.size() > 1) {
        auto left = pq.top(); pq.pop();
        auto right = pq.top(); pq.pop();
        auto parent = new HuffmanNode(left->val + right->val, '\0', left, right);
        pq.push(parent);
    }
    return pq.top();
}

// 构造哈夫曼编码
void buildHuffmanCode(HuffmanNode* root, string code) {
    if (!root) return;
    if (root->ch != '\0') {
        huffmanCode[root->ch] = code;
    }
    buildHuffmanCode(root->left, code + '0');
    buildHuffmanCode(root->right, code + '1');
}

// 压缩数据
string compress(string data) {
    string compressed;
    for (char ch : data) {
        compressed += huffmanCode[ch];
    }
    return compressed;
}

// 解压缩数据
string decompress(string compressed, HuffmanNode* root) {
    string decompressed;
    auto curr = root;
    for (char ch : compressed) {
        if (ch == '0') {
            curr = curr->left;
        } else {
            curr = curr->right;
        }
        if (curr->ch != '\0') {
            decompressed += curr->ch;
            curr = root;
        }
    }
    return decompressed;
}

int main() {
    int n;
    cout << "请输入叶子节点的个数n：" << endl;
    cin >> n;
    vector<int> weights(n);
    cout << "请输入n个叶子节点的权值：" << endl;
    for (int i = 0; i < n; ++i) {
        cin >> weights[i];
    }
    HuffmanNode* root = buildHuffmanTree(weights);
    buildHuffmanCode(root, "");
    string data;
    cout << "请输入需要压缩的数据：" << endl;
    cin >> data;
    string compressed = compress(data);
    cout << "压缩后的数据：" << compressed << endl;
    string decompressed = decompress(compressed, root);
    cout << "解压缩后的数据：" << decompressed << endl;
    return 0;
}

注意，此代码中将输入的叶子节点的字符默认为'A'到'A'+n-1，如果需要输入其他字符，可以修改代码。另外，此代码中没有对输入数据进行错误处理，如果输入数据不符合要求，程序可能会出错。