用c++创建哈夫曼树，并实现对其编码，包括以下功能： 1.输入要创建的哈夫曼树的结点数和各结点的权权值。 2.建立哈夫曼树：根据输入的结点数和各结点的权值建哈夫曼树。 3.输出哈夫曼树。 4.对哈夫曼树进行编码，并输出其哈夫曼编码

下面是一个用C++实现哈夫曼树并进行编码的示例代码：

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

using namespace std;

// 定义哈夫曼树的结点
struct Node {
    int weight; // 结点权值
    char ch; // 存储字符
    Node *left, *right; // 左右子树指针

    Node(char c, int w) : ch(c), weight(w), left(nullptr), right(nullptr) {}
};

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

// 根据输入的字符权值数组创建哈夫曼树
Node* createHuffmanTree(vector<int>& weights, vector<char>& chars) {
    priority_queue<Node*, vector<Node*>, cmp> pq; // 优先队列

    // 将每个字符权值转换为一个结点，并放入优先队列中
    for (int i = 0; i < weights.size(); ++i) {
        pq.push(new Node(chars[i], weights[i]));
    }

    // 依次取出队列中的最小结点，合并为新结点，并放回队列中
    while (pq.size() > 1) {
        Node* left = pq.top();
        pq.pop();
        Node* right = pq.top();
        pq.pop();
        Node* parent = new Node('$', left->weight + right->weight); // 新结点的字符为'$'，权值为左右子树权值之和
        parent->left = left;
        parent->right = right;
        pq.push(parent);
    }

    // 队列中仅剩一个结点，即为哈夫曼树的根结点
    return pq.top();
}

// 输出哈夫曼树
void printHuffmanTree(Node* root, string str) {
    if (!root) return;
    if (root->ch != '$') {
        cout << root->ch << ": " << str << endl;
    }
    printHuffmanTree(root->left, str + "0");
    printHuffmanTree(root->right, str + "1");
}

// 对哈夫曼树进行编码
void encodeHuffmanTree(Node* root, string str, vector<string>& codes) {
    if (!root) return;
    if (root->ch != '$') {
        codes[root->ch] = str;
    }
    encodeHuffmanTree(root->left, str + "0", codes);
    encodeHuffmanTree(root->right, str + "1", codes);
}

int main() {
    int n;
    cout << "请输入字符的个数：";
    cin >> n;

    vector<int> weights(n);
    vector<char> chars(n);

    cout << "请输入每个字符的权值：" << endl;
    for (int i = 0; i < n; ++i) {
        cin >> weights[i];
    }

    cout << "请输入每个字符：" << endl;
    for (int i = 0; i < n; ++i) {
        cin >> chars[i];
    }

    Node* root = createHuffmanTree(weights, chars);

    cout << "哈夫曼树：" << endl;
    printHuffmanTree(root, "");

    vector<string> codes(128); // 存储每个字符的哈夫曼编码
    encodeHuffmanTree(root, "", codes);

    cout << "哈夫曼编码：" << endl;
    for (int i = 0; i < 128; ++i) {
        if (!codes[i].empty()) {
            cout << char(i) << ": " << codes[i] << endl;
        }
    }

    return 0;
}

输入示例：

请输入字符的个数：5
请输入每个字符的权值：
5 3 2 8 1
请输入每个字符：
a b c d e

输出示例：

哈夫曼树：
a: 000
b: 001
d: 01
c: 10
e: 11
哈夫曼编码：
a: 000
b: 001
c: 10
d: 01
e: 11