哈夫曼树的构造规则_二叉树的带权路径长度

哈夫曼树的构造规则_二叉树的带权路径长度哈夫曼树的建立(C++,最优树)以下是一个简单的C++代码示例,用于生成哈夫曼树:“`cpp#include <iostream>#include <queue>using nam

哈夫曼树的建立(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

(0)
上一篇 2024年 9月 14日
下一篇 2024年 9月 14日

相关推荐

关注微信