请用c++写一段哈夫曼算法

哈夫曼算法是一种用于构建最优二叉树的算法，其核心思想是从底向上地构建一棵树，从而实现数据的有效编码。它的算法步骤如下：1、从序列中选择权重最小的两个元素，并将它们合并为一个新的节点，其权重为两个元素权重之和；2、将新节点添加回序列中；3、重复上述过程，直到序列中只剩一个节点，即为最优二叉树。

相关问题

用c++写一个哈夫曼树

以下是用C语言实现哈夫曼树的示例代码：

#include <stdio.h>
#include <stdlib.h>

// 定义哈夫曼树结点
typedef struct huffman_node {
    int weight; // 权值
    struct huffman_node *left, *right; // 左子树和右子树
} huffman_node;

// 创建哈夫曼树
huffman_node* create_huffman_tree(int weights[], int n) {
    // 初始化哈夫曼树结点数组
    huffman_node* nodes[n];
    for (int i = 0; i < n; i++) {
        nodes[i] = (huffman_node*)malloc(sizeof(huffman_node));
        nodes[i]->weight = weights[i];
        nodes[i]->left = nodes[i]->right = NULL;
    }
    // 构建哈夫曼树
    while (n > 1) {
        // 找到最小的两个结点
        int min1 = 0, min2 = 1;
        if (nodes[min1]->weight > nodes[min2]->weight) {
            min1 = 1;
            min2 = 0;
        }
        for (int i = 2; i < n; i++) {
            if (nodes[i]->weight < nodes[min1]->weight) {
                min2 = min1;
                min1 = i;
            } else if (nodes[i]->weight < nodes[min2]->weight) {
                min2 = i;
            }
        }
        // 创建新的结点
        huffman_node* parent = (huffman_node*)malloc(sizeof(huffman_node));
        parent->weight = nodes[min1]->weight + nodes[min2]->weight;
        parent->left = nodes[min1];
        parent->right = nodes[min2];
        // 从数组中删除旧的结点，添加新的结点
        if (min1 < min2) {
            nodes[min1] = parent;
            nodes[min2] = nodes[n-1];
        } else {
            nodes[min2] = parent;
            nodes[min1] = nodes[n-1];
        }
        n--;
    }
    // 返回根结点
    return nodes[0];
}

// 打印哈夫曼树
void print_huffman_tree(huffman_node* root, int level) {
    if (root == NULL) {
        return;
    }
    for (int i = 0; i < level; i++) {
        printf("  ");
    }
    printf("%d\n", root->weight);
    print_huffman_tree(root->left, level+1);
    print_huffman_tree(root->right, level+1);
}

int main() {
    int weights[] = {5, 3, 8, 2, 4};
    int n = sizeof(weights) / sizeof(int);
    huffman_node* root = create_huffman_tree(weights, n);
    print_huffman_tree(root, 0);
    return 0;
}

该程序可以创建一个哈夫曼树并打印出来，权值可以根据需要进行修改。

用Ｃ＋＋写一个哈夫曼编码程序

以下是用C++实现哈夫曼编码的程序：

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

using namespace std;

// 哈夫曼树的节点
struct Node {
    char ch;
    int freq;
    Node* left;
    Node* right;

    Node(char ch, int freq, Node* left = nullptr, Node* right = nullptr) : ch(ch), freq(freq), left(left), right(right) {}
};

struct Compare {
    bool operator()(Node* left, Node* right) {
        return left->freq > right->freq;
    }
};

// 建立哈夫曼树
Node* buildHuffmanTree(const string& str) {
    priority_queue<Node*, vector<Node*>, Compare> pq;

    // 统计字符的频率
    unordered_map<char, int> freq;
    for (char c : str) {
        freq[c]++;
    }

    // 把每个字符的频率作为节点的权值，加入优先队列
    for (auto& p : freq) {
        pq.push(new Node(p.first, p.second));
    }

    // 依次取出队列中的前两个节点，组成一个新节点，直到队列中只有一个节点为止
    while (pq.size() > 1) {
        Node* left = pq.top();
        pq.pop();

        Node* right = pq.top();
        pq.pop();

        Node* parent = new Node('\0', left->freq + right->freq, left, right);
        pq.push(parent);
    }

    return pq.top();
}

// 将字符与二进制编码映射保存在哈希表中
void buildEncodingMap(Node* root, string& code, unordered_map<char, string>& encodingMap) {
    if (!root) {
        return;
    }

    if (!root->left && !root->right) {
        encodingMap[root->ch] = code;
    }

    if (root->left) {
        code.push_back('0');
        buildEncodingMap(root->left, code, encodingMap);
        code.pop_back();
    }

    if (root->right) {
        code.push_back('1');
        buildEncodingMap(root->right, code, encodingMap);
        code.pop_back();
    }
}

// 哈夫曼编码
string huffmanEncode(const string& str) {
    Node* root = buildHuffmanTree(str);

    unordered_map<char, string> encodingMap;
    string code;
    buildEncodingMap(root, code, encodingMap);

    string encodedStr;
    for (char c : str) {
        encodedStr += encodingMap[c];
    }

    return encodedStr;
}

// 哈夫曼解码
string huffmanDecode(const string& str, Node* root) {
    string decodedStr;
    Node* p = root;
    for (char c : str) {
        if (c == '0') {
            p = p->left;
        } else {
            p = p->right;
        }

        if (!p->left && !p->right) {
            decodedStr += p->ch;
            p = root;
        }
    }

    return decodedStr;
}

int main() {
    string str = "Huffman coding is a data compression algorithm.";
    cout << "原始字符串：" << str << endl;

    string encodedStr = huffmanEncode(str);
    cout << "编码后的字符串：" << encodedStr << endl;

    Node* root = buildHuffmanTree(str);
    string decodedStr = huffmanDecode(encodedStr, root);
    cout << "解码后的字符串：" << decodedStr << endl;

    return 0;
}

该程序先构建哈夫曼树，然后通过遍历哈夫曼树得到每个字符的二进制编码，最后将原始字符串转换为二进制编码。接着进行解码，通过遍历哈夫曼树对二进制编码进行解码。