数据结构哈夫曼树编码代码

以下是哈夫曼树编码的 C++ 代码示例：

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

using namespace std;

struct Node {
    char data;
    int freq;
    Node* left;
    Node* right;

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

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

struct compare {
    bool operator()(Node* l, Node* r) {
        return l->freq > r->freq;
    }
};

void encode(Node* root, string str, unordered_map<char, string>& huffman_code) {
    if (root == nullptr) {
        return;
    }

    if (!root->left && !root->right) {
        huffman_code[root->data] = str;
    }

    encode(root->left, str + "0", huffman_code);
    encode(root->right, str + "1", huffman_code);
}

void decode(Node* root, int& index, string str) {
    if (root == nullptr) {
        return;
    }

    if (!root->left && !root->right) {
        cout << root->data;
        return;
    }

    index++;

    if (str[index] == '0') {
        decode(root->left, index, str);
    } else {
        decode(root->right, index, str);
    }
}

void build_huffman_tree(string text) {
    unordered_map<char, int> freq;
    for (char ch : text) {
        freq[ch]++;
    }

    priority_queue<Node*, vector<Node*>, compare> pq;
    for (auto pair : freq) {
        pq.push(new Node(pair.first, pair.second));
    }

    while (pq.size() != 1) {
        Node* left = pq.top();
        pq.pop();
        Node* right = pq.top();
        pq.pop();

        int sum = left->freq + right->freq;
        pq.push(new Node('\0', sum, left, right));
    }

    Node* root = pq.top();

    unordered_map<char, string> huffman_code;
    encode(root, "", huffman_code);

    cout << "Huffman Codes are:\n";
    for (auto pair : huffman_code) {
        cout << pair.first << " : " << pair.second << endl;
    }

    cout << "Original string was:\n" << text << endl;

    string encoded_string = "";
    for (char ch : text) {
        encoded_string += huffman_code[ch];
    }

    cout << "Encoded string is:\n" << encoded_string << endl;

    int index = -1;
    cout << "Decoded string is:\n";
    while (index < (int)encoded_string.size() - 2) {
        decode(root, index, encoded_string);
    }
    cout << endl;

    delete root;
}

int main() {
    string text = "Huffman coding is a data compression algorithm.";
    build_huffman_tree(text);
    return 0;
}

这个程序会输出原始字符串、哈夫曼编码和解码后的字符串。