关于#c++#的问题：(每个结点的哈夫曼编码输出后需换行)输入样例1:47 5 2 4输出样例1:010110111（相关搜索：编写程序|结点个数|哈夫曼树）

Question

c++编写程序，输入结点个数及各结点对应的权值，创建哈夫曼树，生成哈夫曼编码并输出。
输入说明:先输入结点个数，然后依次输入各结点对应的权值。
输出说明:依次输出各结点的哈夫曼编码。(每个结点的哈夫曼编码输出后需换行)
输入样例1:
4
7 5 2 4
输出样例1:
0
10
110
111

输入样例2:
8
5 29 7 8 14 23 3 11
输出样例2:
0001
10
11101
1111
110
01
0000
001

Answer 1

引自免费微信小程序：皆我百晓生

为了实现这个功能，你需要按照以下步骤编写C++代码：

1. 定义一个结构体或类表示二叉树节点，包含左子节点、右子节点以及权重。
2. 创建一个优先队列（最小堆）用于存放二叉树节点，根据权重进行排序。
3. 根据输入的节点个数创建相应的二叉树节点，并将它们添加到优先队列中。
4. 从优先队列中取出两个权重最小的节点，创建一个新的父节点，其权重为这两个子节点的权重之和，然后将新节点插入到优先队列中。
5. 重复第4步，直到优先队列中只剩下一个节点，这个节点就是哈夫曼树的根节点。
6. 从根节点开始，递归地计算每个节点的哈夫曼编码，左子节点对应'0'，右子节点对应'1'。
7. 输出每个节点的哈夫曼编码，每个编码后换行。

以下是完整的C++代码示例：

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

struct TreeNode {
    int weight;
    TreeNode* left;
    TreeNode* right;
    std::string code;

    TreeNode(int w) : weight(w), left(nullptr), right(nullptr), code("") {}
};

class HuffmanTree {
public:
    void buildHuffmanTree(const std::vector<int>& weights) {
        std::priority_queue<TreeNode*, std::vector<TreeNode*>, std::greater<TreeNode*>> minHeap;

        for (int weight : weights) {
            TreeNode* node = new TreeNode(weight);
            minHeap.push(node);
        }

        while (minHeap.size() > 1) {
            TreeNode* leftNode = minHeap.top();
            minHeap.pop();

            TreeNode* rightNode = minHeap.top();
            minHeap.pop();

            TreeNode* newNode = new TreeNode(leftNode->weight + rightNode->weight);
            newNode->left = leftNode;
            newNode->right = rightNode;

            leftNode->parent = newNode;
            rightNode->parent = newNode;

            minHeap.push(newNode);
        }

        root = minHeap.top();
    }

    void generateCodes(TreeNode* node, std::string currentCode) {
        if (node == nullptr) return;

        if (node->left == nullptr && node->right == nullptr) {
            node->code = currentCode;
            std::cout << currentCode << std::endl;
            return;
        }

        generateCodes(node->left, currentCode + "0");
        generateCodes(node->right, currentCode + "1");
    }

private:
    TreeNode* root;
};

int main() {
    int numNodes;
    std::cin >> numNodes;

    std::vector<int> weights(numNodes);
    for (int i = 0; i < numNodes; ++i) {
        std::cin >> weights[i];
    }

    HuffmanTree huffmanTree;
    huffmanTree.buildHuffmanTree(weights);

    huffmanTree.generateCodes(huffmanTree.root, "");

    return 0;
}

这段代码首先定义了一个TreeNode结构体，然后实现了HuffmanTree类，其中包含了构建哈夫曼树和生成哈夫曼编码的方法。在main函数中，读取输入的结点个数和权值，创建HuffmanTree对象并调用相应方法来完成任务。注意，这里使用了STL中的std::priority_queue作为最小堆来实现。