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

好的，我可以帮你解决这个问题。首先，哈夫曼树是一种带权路径长度最小的树，可以用于数据压缩等场景。下面我将介绍如何用 C++ 实现哈夫曼树的创建和编码。

1. 输入要创建的哈夫曼树的结点数和各结点的权权值。

我们可以定义一个结构体来表示每个结点，包含一个权值和指向左右子树的指针。

struct Node {
    int weight;
    Node* left;
    Node* right;
};

然后，我们可以使用一个数组来存储每个结点的权值，如下所示：

int weights[MAX_N]; // 存储每个结点的权值
int n; // 结点数

在实际使用中，可以通过输入或从文件中读取这些权值。

2. 建立哈夫曼树

建立哈夫曼树的过程可以使用贪心算法。算法的基本思路是：每次选择权值最小的两个结点，将它们合并成一个新的结点，并将新结点的权值设为这两个结点的权值之和。重复这个过程直到只剩下一个结点，这个结点就是哈夫曼树的根节点。

具体实现可以使用优先队列（堆）来实现。我们可以将每个结点看作一个单独的树，然后将它们插入到一个最小堆中。每次从最小堆中取出两个权值最小的结点，合并成一个新的结点，并将这个新的结点插入到最小堆中。重复这个过程直到堆中只剩下一个结点，这个结点就是哈夫曼树的根节点。

下面是代码实现：

Node* buildHuffmanTree(int weights[], int n) {
    // 优先队列中存储的是指向结点的指针，然后通过重载运算符实现结点比较的方法
    priority_queue<Node*, vector<Node*>, [](Node* a, Node* b) {
        return a->weight > b->weight;
    }> pq;
    for (int i = 0; i < n; i++) {
        Node* node = new Node();
        node->weight = weights[i];
        node->left = nullptr;
        node->right = nullptr;
        pq.push(node);
    }
    while (pq.size() > 1) {
        Node* left = pq.top();
        pq.pop();
        Node* right = pq.top();
        pq.pop();
        Node* parent = new Node();
        parent->weight = left->weight + right->weight;
        parent->left = left;
        parent->right = right;
        pq.push(parent);
    }
    return pq.top();
}

3. 输出哈夫曼树

输出哈夫曼树可以使用递归的方式进行遍历，并输出每个结点的权值和它的左右子树（如果有的话）。

void printHuffmanTree(Node* root) {
    if (root == nullptr) {
        return;
    }
    cout << root->weight << endl;
    if (root->left != nullptr) {
        cout << "Left: ";
        printHuffmanTree(root->left);
    }
    if (root->right != nullptr) {
        cout << "Right: ";
        printHuffmanTree(root->right);
    }
}

4. 对哈夫曼树进行编码，并输出其哈夫曼编码

对哈夫曼树进行编码需要用到递归。基本思路是：从根节点开始，如果往左走就在编码后的字符串中加入一个 0，如果往右走就在编码后的字符串中加入一个 1。当到达叶子结点时，就得到了这个结点的哈夫曼编码。重复这个过程直到遍历完整个哈夫曼树。

为了方便存储编码，我们可以使用一个数组来存储每个结点的编码。数组的下标表示结点的权值，数组的值表示该结点的编码。

下面是代码实现：

void encodeHuffmanTree(Node* root, string code, vector<string>& codes) {
    if (root == nullptr) {
        return;
    }
    if (root->left == nullptr && root->right == nullptr) {
        codes[root->weight] = code;
    }
    encodeHuffmanTree(root->left, code + "0", codes);
    encodeHuffmanTree(root->right, code + "1", codes);
}

完整代码如下：