用c++构造一个哈夫曼树
时间: 2023-07-01 22:25:47 浏览: 62
好的,下面是用C++实现构造哈夫曼树的代码:
```cpp
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
// 哈夫曼树节点
struct HuffmanTreeNode {
char data; // 字符
int weight; // 权值
HuffmanTreeNode* left; // 左子树指针
HuffmanTreeNode* right; // 右子树指针
};
// 比较器,构造小根堆
struct cmp {
bool operator()(HuffmanTreeNode* a, HuffmanTreeNode* b) {
return a->weight > b->weight;
}
};
// 构造哈夫曼树
HuffmanTreeNode* constructHuffmanTree(vector<int>& weights, vector<char>& chars) {
priority_queue<HuffmanTreeNode*, vector<HuffmanTreeNode*>, cmp> minHeap;
int n = weights.size();
for (int i = 0; i < n; i++) {
HuffmanTreeNode* node = new HuffmanTreeNode();
node->data = chars[i];
node->weight = weights[i];
node->left = nullptr;
node->right = nullptr;
minHeap.push(node);
}
while (minHeap.size() > 1) {
HuffmanTreeNode* node1 = minHeap.top();
minHeap.pop();
HuffmanTreeNode* node2 = minHeap.top();
minHeap.pop();
HuffmanTreeNode* newNode = new HuffmanTreeNode();
newNode->data = '\0';
newNode->weight = node1->weight + node2->weight;
newNode->left = node1;
newNode->right = node2;
minHeap.push(newNode);
}
return minHeap.top();
}
// 前序遍历哈夫曼树
void preOrder(HuffmanTreeNode* root) {
if (root == nullptr) {
return;
}
cout << root->data << "(" << root->weight << ")" << " ";
preOrder(root->left);
preOrder(root->right);
}
int main() {
vector<int> weights = { 2, 3, 4, 5 };
vector<char> chars = { 'a', 'b', 'c', 'd' };
HuffmanTreeNode* root = constructHuffmanTree(weights, chars);
preOrder(root);
return 0;
}
```
这段代码通过使用优先队列来构造小根堆,然后依次取出队列中最小的两个节点合并,直到队列中只剩下一个节点,这个节点就是哈夫曼树的根节点。我们可以通过前序遍历来验证构造出来的哈夫曼树是否正确。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)