在c++中利用Huffman树和Huffman编码实现一个无损数据压缩软件工具。

Huffman 编码是一种无损数据压缩算法，其原理是将出现频率较高的字符用较短的编码表示，而出现频率较低的字符用较长的编码表示。下面是一个利用 Huffman 树和 Huffman 编码实现无损数据压缩的示例代码：

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

using namespace std;

// 定义 Huffman 树节点
struct Node {
    char ch;
    int freq;
    Node* left;
    Node* right;

    Node(char ch, int freq, Node* left = nullptr, Node* right = nullptr) {
        this->ch = ch;
        this->freq = freq;
        this->left = left;
        this->right = right;
    }

    ~Node() {
        delete left;
        delete right;
    }
};

// 定义比较器
struct Compare {
    bool operator()(Node* a, Node* b) {
        return a->freq > b->freq;
    }
};

// 构建 Huffman 树
Node* buildHuffmanTree(const string& str) {
    // 统计字符频率
    unordered_map<char, int> freq;
    for (char ch : str) {
        freq[ch]++;
    }

    // 构建 Huffman 树
    priority_queue<Node*, vector<Node*>, Compare> pq;
    for (auto& p : freq) {
        pq.push(new Node(p.first, p.second));
    }
    while (pq.size() > 1) {
        Node* left = pq.top();
        pq.pop();
        Node* right = pq.top();
        pq.pop();
        pq.push(new Node('\0', left->freq + right->freq, left, right));
    }

    return pq.top();
}

// 生成 Huffman 编码表
void generateHuffmanCodes(Node* root, const string& prefix, unordered_map<char, string>& codes) {
    if (root == nullptr) {
        return;
    }
    if (root->left == nullptr && root->right == nullptr) {
        codes[root->ch] = prefix;
        return;
    }
    generateHuffmanCodes(root->left, prefix + "0", codes);
    generateHuffmanCodes(root->right, prefix + "1", codes);
}

// 压缩数据
string compress(const string& str, unordered_map<char, string>& codes) {
    string compressed;
    for (char ch : str) {
        compressed += codes[ch];
    }
    return compressed;
}

// 解压数据
string decompress(const string& compressed, Node* root) {
    string decompressed;
    Node* curr = root;
    for (char ch : compressed) {
        if (ch == '0') {
            curr = curr->left;
        } else {
            curr = curr->right;
        }
        if (curr->left == nullptr && curr->right == nullptr) {
            decompressed += curr->ch;
            curr = root;
        }
    }
    return decompressed;
}

int main() {
    string str = "hello world";
    Node* root = buildHuffmanTree(str);
    unordered_map<char, string> codes;
    generateHuffmanCodes(root, "", codes);
    string compressed = compress(str, codes);
    string decompressed = decompress(compressed, root);
    cout << "Original string: " << str << endl;
    cout << "Compressed string: " << compressed << endl;
    cout << "Decompressed string: " << decompressed << endl;
    delete root;
    return 0;
}

以上代码首先定义了一个 `Node` 结构体，表示 Huffman 树的节点。然后使用优先队列和一个哈希表分别构建 Huffman 树和 Huffman 编码表。最后利用 Huffman 编码表对原始数据进行压缩，并解压缩压缩后的数据。