数据结构哈夫曼树建立代码

哈夫曼树是一种用于编码的数据结构，它可以将出现频率较高的字符编码为较短的二进制码，从而提高数据的传输效率。下面是哈夫曼树的建立代码：

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

struct Node {
    int freq;          // 字符出现的频率
    char ch;           // 字符
    Node* left;        // 左子树
    Node* right;       // 右子树
    Node(int f, char c) : freq(f), ch(c), left(nullptr), right(nullptr) {}
};

struct cmp {
    bool operator()(const Node* a, const Node* b) const {
        return a->freq > b->freq;  // 小根堆
    }
};

Node* buildHuffmanTree(vector<int>& freq, vector<char>& ch) {
    priority_queue<Node*, vector<Node*>, cmp> pq;
    for (int i = 0; i < freq.size(); i++) {
        pq.push(new Node(freq[i], ch[i]));
    }
    while (pq.size() > 1) {
        Node* left = pq.top();
        pq.pop();
        Node* right = pq.top();
        pq.pop();
        Node* parent = new Node(left->freq + right->freq, '\0');
        parent->left = left;
        parent->right = right;
        pq.push(parent);
    }
    return pq.top();
}

void printHuffmanCode(Node* root, string code) {
    if (root->left == nullptr && root->right == nullptr) {
        cout << root->ch << ": " << code << endl;
        return;
    }
    if (root->left != nullptr) {
        printHuffmanCode(root->left, code + "0");
    }
    if (root->right != nullptr) {
        printHuffmanCode(root->right, code + "1");
    }
}

int main() {
    vector<int> freq = {5, 9, 12, 13, 16, 45};
    vector<char> ch = {'a', 'b', 'c', 'd', 'e', 'f'};
    Node* root = buildHuffmanTree(freq, ch);
    string code;
    printHuffmanCode(root, code);
    return 0;
}

在这个代码中，我们使用了一个小根堆来存储每个字符的频率以及对应的字符节点。首先，我们将每个字符节点加入堆中。然后，我们不断地从堆中取出频率最小的两个字符节点，将它们合并成一个父节点，并将父节点加入堆中。这个过程一直持续到堆中只剩下一个节点，这个节点就是哈夫曼树的根节点。

在建立哈夫曼树之后，我们可以通过遍历树，将每个字符的编码打印出来。对于每个字符节点，它的左子树的编码为当前编码加上 0，右子树的编码为当前编码加上 1。当遇到叶子节点时，我们就可以将编码打印出来了。

以上是哈夫曼树建立的代码，希望对你有所帮助！