数据结构-构造哈夫曼树【详解+代码+图示】一文解惑！ 哈夫曼树是一种特殊的二叉树，它的叶子节点对应着要编码的字符，而非叶子节点则对应着编码。哈夫曼树的构建过程是基于贪心策略的，即每次选取出现频率最小的两个节点，将它们合并成一个新节点，直到最后形成一棵哈夫曼树。以下是一个 C++ 的实现： “`c++ #include <iostream> #include <queue> #include <vector> using namespace std; // 定义哈夫曼树节点结构体 struct TreeNode { char data; // 节点存储的字符 int freq; // 节点对应字符出现的频率 TreeNode* left; // 左子节点 TreeNode* right; // 右子节点 TreeNode(char data, int freq) : data(data), freq(freq), left(nullptr), right(nullptr) {} }; // 定义比较函数，用于优先队列的排序 struct cmp { bool operator()(TreeNode* a, TreeNode* b) { return a->freq > b->freq; // 频率小的节点优先级高 } }; // 构建哈夫曼树的函数 TreeNode* buildHuffmanTree(vector<char>& chars, vector<int>& freqs) { priority_queue<TreeNode*, vector<TreeNode*>, cmp> pq; // 定义优先队列 for (int i = 0; i < chars.size(); i++) { TreeNode* node = new TreeNode(chars[i], freqs[i]); // 创建节点，存储字符和频率 pq.push(node); // 将节点加入到优先队列中 } while (pq.size() > 1) { // 只要队列中还有两个及以上的节点 TreeNode* left = pq.top(); // 取出频率最小的节点 pq.pop(); TreeNode* right = pq.top(); // 取出频率次小的节点 pq.pop(); TreeNode* parent = new TreeNode(‘$’, left->freq + right->freq); // 新建一个父节点 parent->left = left; // 将左子节点挂到父节点下面 parent->right = right; // 将右子节点挂到父节点下面 pq.push(parent); // 将新建的父节点加入到队列中 } return pq.top(); // 队列中最后剩下的节点即为根节点 } // 递归打印哈夫曼树的编码 void printHuffmanCode(TreeNode* root, string code) { if (!root) return; // 递归结束条件 if (root->data != ‘$’) { // 如果是叶子节点，输出对应字符和编码 cout << root->data << ” ” << code << endl; } printHuffmanCode(root->left, code + “0”); // 递归处理左子树 printHuffmanCode(root->right, code + “1”); // 递归处理右子树 } int main() { vector<char> chars = {‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’}; vector<int> freqs = {5, 9, 12, 13, 16, 45}; TreeNode* root = buildHuffmanTree(chars, freqs); printHuffmanCode(root, “”); return 0; } “` 输出结果： “` f 0 c 100 d 101 a 1100 b 1101 e 111 “` 以上代码中，`buildHuffmanTree` 函数用于构建哈夫曼树，它使用了优先队列（堆）来维护频率最小的两个节点，不断合并成为新的节点，直到最后形成一棵哈夫曼树。`printHuffmanCode` 函数用于递归打印哈夫曼树的编码，其中传入的 `code` 参数表示当前节点的编码。
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/49726.html
