首页7-2 哈夫曼编码pta

7-2 哈夫曼编码pta

时间: 2025-02-28 14:06:23 浏览: 66

### 关于哈夫曼编码的PTA题解 #### 构建哈夫曼树并计算带权路径长度构建哈夫曼树的过程涉及创建一个优先队列（最小堆），其中每个节点代表一个字符及其频率。通过不断取出两个具有最低权重的节点，组合成一个新的内部节点，并将其重新加入到优先队列中直到只剩下一个根节点为止。对于给定的一组叶结点数量`n`以及对应的权重列表，在C++中的实现可以如下所示： ```cpp #include <iostream> #include <queue> using namespace std; struct Node { int weight; Node *left, *right; bool operator<(const Node& rhs)const{ return this->weight > rhs.weight; // 小顶堆比较函数 } }; // 计算所有节点的值与权值乘积之和 int calculateWPL(Node* root,int level=0){ if (!root) return 0; if (root->left==nullptr && root->right==nullptr) return level * root->weight; return calculateWPL(root->left,level+1)+calculateWPL(root->right,level+1); } void huffmanTree(vector<int>& weights){ priority_queue<Node> pq; for(auto w : weights){ pq.push({w,nullptr,nullptr}); } while(pq.size() != 1){ auto node1 = new Node{pq.top().weight , nullptr, nullptr}; pq.pop(); auto node2 = new Node{pq.top().weight , nullptr, nullptr}; pq.pop(); auto parent = new Node {node1->weight + node2->weight,node1,node2}; pq.push(*parent); } cout << "The WPL of the Huffman Tree is:"<<endl<<calculateWPL(&pq.top())<< endl; } ``` 此代码片段展示了如何基于一组权重建立哈夫曼树，并最终打印出整个树结构的加权路径长度(WPL)[^2]。

阅读全文