哈夫曼树的建立(C++,最优树) 以下是一个简单的C++代码示例,用于生成哈夫曼树: “`cpp #include <iostream> #include <queue> using namespace std; // 哈夫曼树节点 struct HuffmanNode { char data; int frequency; HuffmanNode* left; HuffmanNode* right; HuffmanNode(char data, int frequency) { this->data = data; this->frequency = frequency; left = nullptr; right = nullptr; } }; // 用于比较节点频率的函数对象 struct Compare { bool operator()(HuffmanNode* a, HuffmanNode* b) { return a->frequency > b->frequency; } }; // 构建哈夫曼树 HuffmanNode* buildHuffmanTree(priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare>& pq) { while (pq.size() > 1) { HuffmanNode* left = pq.top(); pq.pop(); HuffmanNode* right = pq.top(); pq.pop(); // 创建一个新节点作为父节点 HuffmanNode* parent = new HuffmanNode(‘$’, left->frequency + right->frequency); parent->left = left; parent->right = right; pq.push(parent); } return pq.top(); } // 打印哈夫曼编码 void printHuffmanCodes(HuffmanNode* root, string code) { if (root == nullptr) { return; } if (root->data != ‘$’) { // 叶子节点 cout << root->data << “: ” << code << endl; } printHuffmanCodes(root->left, code + “0”); printHuffmanCodes(root->right, code + “1”); } int main() { string text = “Hello, World!”; int frequency[256] = {0}; // 统计字符频率 for (char c : text) { frequency[c]++; } // 构建优先队列,按照频率排序 priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> pq; for (int i = 0; i < 256; i++) { if (frequency[i] > 0) { HuffmanNode* node = new HuffmanNode(static_cast<char>(i), frequency[i]); pq.push(node); } } // 构建哈夫曼树 HuffmanNode* root = buildHuffmanTree(pq); // 打印哈夫曼编码 printHuffmanCodes(root, “”); return 0; } “` 上述代码中,首先统计了给定文本中字符的频率。然后,使用优先队列来构建哈夫曼树,每次从队列中取出两个频率最低的节点,并创建一个新的父节点连接它们。最后,通过递归遍历哈夫曼树,生成每个字符的哈夫曼编码并进行打印输出。 请注意,以上只是一个简单的示例,并没有处理特殊字符或文件输入输出。在实际应用中,可能需要进行相关的扩展和修改。
2024最新激活全家桶教程,稳定运行到2099年,请移步至置顶文章:https://sigusoft.com/99576.html
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请联系我们举报,一经查实,本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处:https://sigusoft.com/22752.html