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

Question

编写程序，输入结点个数及各结点对应的权值，创建哈夫曼树，生成哈夫曼编码并输出。
输入说明:先输入结点个数，然后依次输入各结点对应的权值。
输出说明:依次输出各结点的哈夫曼编码。(每个结点的哈夫曼编码输出后需换行)
输入样例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

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

为了帮助你解决这个问题，首先我们需要了解哈夫曼编码是如何生成的。哈夫曼编码是通过构建哈夫曼树来实现的，这是一个贪心算法，用于给每一个输入的权值生成一个独一无二的二进制码。以下是步骤：

1. 创建一个空的优先队列（最小堆）。
2. 将所有节点（每个节点包含权值和一个空的哈夫曼编码）插入队列，初始时每个节点的权重为它们的权值。
3. 从队列中取出两个权值最小的节点，合并它们，形成一个新的节点，新节点的权值为两个子节点权值之和，新的哈夫曼编码为最左子节点的编码加上一个'0'，最右子节点的编码加上一个'1'。
4. 将新节点放回队列，并重复步骤3，直到只剩下一个节点，这个节点就是根节点，其编码即为整个哈夫曼树的编码。
5. 对于输入的每个节点，找到它的路径上从根节点到自身的编码。

以下是C++代码实现：

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

// 定义一个结构体来存储节点
struct Node {
    int weight;
    std::string code;
    Node* left = nullptr;
    Node* right = nullptr;
};

// 建立最小堆
void heapify(Node** heap, int size, int i) {
    int smallest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < size && heap[left]->weight < heap[smallest]->weight)
        smallest = left;

    if (right < size && heap[right]->weight < heap[smallest]->weight)
        smallest = right;

    if (smallest != i) {
        std::swap(heap[i], heap[smallest]);
        heapify(heap, size, smallest);
    }
}

// 插入节点到堆
void insert(Node** heap, int size, Node* node) {
    heap[size] = node;
    heapify(heap, size + 1, size);
    size++;
}

// 生成哈夫曼编码
Node* buildHuffmanTree(int n, int* weights) {
    std::priority_queue<Node*, std::vector<Node*>, std::greater<Node*>> heap;

    for (int i = 0; i < n; i++) {
        Node* node = new Node();
        node->weight = weights[i];
        node->code = "";
        insert(&heap, 0, node);
    }

    while (heap.size() > 1) {
        Node* left = heap.top(); heap.pop();
        Node* right = heap.top(); heap.pop();

        Node* newNode = new Node();
        newNode->weight = left->weight + right->weight;
        newNode->left = left;
        newNode->right = right;

        newNode->code = left->code + "0" + right->code + "1";
        insert(&heap, 0, newNode);
    }

    return heap.top();
}

// 打印哈夫曼编码
void printHuffmanCodes(Node* root, std::string prefix = "") {
    if (!root)
        return;

    std::cout << prefix << root->code << '\n';
    printHuffmanCodes(root->left, prefix + "0");
    printHuffmanCodes(root->right, prefix + "1");
}

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

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

    Node* root = buildHuffmanTree(n, weights);

    printHuffmanCodes(root);

    return 0;
}

这段代码首先定义了一个Node结构体，用于表示哈夫曼树的节点。然后实现了一个最小堆，用于构建哈夫曼树。buildHuffmanTree函数生成哈夫曼树，printHuffmanCodes函数用于打印哈夫曼编码。在main函数中，读取输入数据，调用这两个函数并输出结果。

运行这段代码，输入样例1和样例2会得到相应的输出。如果你有任何疑问，随时告诉我。