算法设计-哈夫曼树（C++）

一、详细代码

算法原理：

Huffman编码是一种用于数据压缩的算法，它通过为出现频率较高的字符分配较短的编码，而为出现频率较低的字符分配较长的编码，从而实现数据的压缩。


#include <iostream>
#include <queue>
#include <map>
#include <vector>
#include <cassert>using namespace std;// Huffman Node structure
class HuffmanNode {
public:char character;int frequency;HuffmanNode* left;HuffmanNode* right;HuffmanNode(char c, int f) : character(c), frequency(f), left(NULL), right(NULL) {}
};// Comparator for priority queue to ensure minimum frequency node comes first
struct Compare {bool operator()(const HuffmanNode* l, const HuffmanNode* r) {return l->frequency > r->frequency;}
};// Function to create Huffman Tree
HuffmanNode* CreateHuffmanTree(map<char, int> frequencies) {priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> pq;// Insert all characters into priority queuefor (auto it = frequencies.begin(); it != frequencies.end(); ++it) {pq.push(new HuffmanNode(it->first, it->second));}// Iterate until there is more than one node in the queuewhile (pq.size() != 1) {HuffmanNode* left = pq.top(); pq.pop();HuffmanNode* right = pq.top(); pq.pop();HuffmanNode* newNode = new HuffmanNode('\0', left->frequency + right->frequency);newNode->left = left;newNode->right = right;pq.push(newNode);}return pq.top(); // Return the root node of the Huffman Tree
}// Function to print codes from Huffman Tree
void PrintCodes(HuffmanNode* root, string code, map<char, string>& codes) {if (root == NULL) return;if (root->character != '\0') {codes[root->character] = code;return;}PrintCodes(root->left, code + "0", codes);PrintCodes(root->right, code + "1", codes);
}// Main function
int main() {map<char, int> frequencies = {{'0', 5}, {'1', 5}, {'2', 10}, {'3', 10}, {'4', 10}, {'5', 15},{'6',20},{'7',25}};HuffmanNode* root = CreateHuffmanTree(frequencies);map<char, string> codes;PrintCodes(root, "", codes);cout << "Character Codes:\n";for (auto it = codes.begin(); it != codes.end(); ++it) {cout << it->first << ": " << it->second << endl;}return 0;
}

二、结构体

1. HuffmanNode 结构体

HuffmanNode 是一个表示Huffman树节点的类。
character：存储字符。
frequency：存储字符的频率（即字符在输入中出现的次数）。
left 和 right：分别指向左子树和右子树的指针。
构造函数：用于初始化节点的字符、频率以及左右子树指针。

2. Compare 结构体

Compare 是一个用于优先队列的比较器。
它定义了如何比较两个 HuffmanNode 指针，确保频率较小的节点在优先队列中排在前面。这是为了在构建Huffman树时，能够优先合并频率最小的节点。

三、函数

CreateHuffmanTree 函数用于构建Huffman树。
步骤：
1. 首先，将所有字符及其频率插入到优先队列 pq 中。
2. 然后，循环地从队列中取出两个频率最小的节点，合并它们，生成一个新的节点，新节点的频率为这两个节点的频率之和。
3. 将新节点重新插入队列中。
4. 重复上述步骤，直到队列中只剩下一个节点，这个节点就是Huffman树的根节点。
返回值：返回Huffman树的根节点。

PrintCodes 函数用于从Huffman树中生成每个字符的编码。
参数：
- root：当前节点。
- code：当前路径的编码（从根节点到当前节点的路径）。
- codes：存储字符及其对应编码的映射。
递归过程：
1. 如果当前节点是叶子节点（即 root->character != '\0'），则将当前路径 code 存储到 codes 中。
2. 否则，递归地遍历左子树和右子树，并在路径上添加 0 或 1。

main 函数是程序的入口。
步骤：
1. 定义一个字符频率的映射 frequencies，表示每个字符及其出现的频率。
2. 调用 CreateHuffmanTree 函数构建Huffman树，并返回根节点。
3. 调用 PrintCodes 函数生成每个字符的编码，并存储在 codes 映射中。
4. 最后，遍历 codes 映射，输出每个字符及其对应的Huffman编码。