C++ 实现霍夫曼树生成算法

#include #include #include using namespace std;

struct Node { int weight; Node* left; Node* right; Node(int w) : weight(w), left(nullptr), right(nullptr) {} };

struct cmp { bool operator () (Node* a, Node* b) { return a->weight > b->weight; } };

Node* buildHuffmanTree(vector& weights) { priority_queue<Node*, vector<Node*>, cmp> pq; for (int weight : weights) { pq.push(new Node(weight)); } while (pq.size() > 1) { Node* left = pq.top(); pq.pop(); Node* right = pq.top(); pq.pop(); Node* parent = new Node(left->weight + right->weight); parent->left = left; parent->right = right; pq.push(parent); } return pq.top(); }

void printHuffmanCode(Node* root, string code) { if (!root) return; if (!root->left && !root->right) { cout << 'value: ' << root->weight << ', code: ' << code << endl; return; } if (root->left) printHuffmanCode(root->left, code + '0'); if (root->right) printHuffmanCode(root->right, code + '1'); }

int main() { vector weights = { 5, 3, 9, 7, 2, 4 }; Node* root = buildHuffmanTree(weights); printHuffmanCode(root, ""); return 0; }