C++数据结构--哈夫曼树

一.什么是哈夫曼树哈夫曼树Huffman Tree是一种特殊的二叉树也被称为最优二叉树。它的核心目标非常明确让带权路径长度WPL达到最小。在哈夫曼树中每个叶子节点都有一个“权值”Weight可以理解为出现的频率或重要性。权值越大的节点离根节点越近路径越短权值越小的节点离根节点越远路径越长。这样就能保证整体的 WPL 最小。哈夫曼树最经典的应用数据压缩核心思想是出现频率高的字符用短的二进制编码出现频率低的字符用长的二进制编码。二.代码实现class HuffmanTree { public: HuffmanTree() :root(nullptr) { } //创建哈夫曼树 void create(string str) { mapchar, uintdataMap; for (char s : str) { dataMap[s]; } for (auto pair : dataMap) { p_que.push(new Node(pair.first, pair.second)); } while (p_que.size() 1) { Node* n1 p_que.top(); p_que.pop(); Node* n2 p_que.top(); p_que.pop(); Node* node new Node(\0, n1-weight n2-weight); node-left n1; node-right n2; p_que.push(node); } root p_que.top(); p_que.pop(); } //获取字符串编码 string showhuffMancode(string str) { string encode; if (root nullptr) { throw the tree is empty; } huffMancode(); for (auto s : str) { encode.append(mp[s]); } return encode; } //解码 void delcode( string encode) { Node* node root; for (char c : encode) { if (c 0) { nodenode-left; } else { nodenode-right; } if (node-left nullptr node-right nullptr) { cout node-m_data; node root; } } cout endl; } private: //输出哈夫曼编码 void huffMancode() { if (root nullptr) { return; } string code; huffMancode(root, code); /*for (auto pair : mp) { cout pair.first : pair.second endl; }*/ } struct Node { Node(char data, uint w) :m_data(data) , weight(w) , left(nullptr) , right(nullptr) { } bool operator(const Node* a) { return weight a-weight; } char m_data; uint weight; Node* left; Node* right; }; Node* root; mapchar, stringmp; using minHeap priority_queue Node*, vectorNode*, greaterNode* ; minHeap p_que; private: void huffMancode(Node* node, string code) { if (node-left nullptr node-right nullptr) { mp.emplace(node-m_data, code); return; } huffMancode(node-left, code 0); huffMancode(node-right, code 1); } };