请用C++实现初始化HuffmanTree参数
时间: 2023-06-13 14:08:17 浏览: 70
以下是用C++实现初始化HuffmanTree参数的示例代码:
```cpp
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct TreeNode{
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x): val(x), left(NULL), right(NULL){}
};
struct cmp{
bool operator()(TreeNode* a, TreeNode* b){
return a->val > b->val;
}
};
TreeNode* buildHuffmanTree(vector<int>& nums){
priority_queue<TreeNode*, vector<TreeNode*>, cmp> pq;
for(int i=0; i<nums.size(); i++){
pq.push(new TreeNode(nums[i]));
}
while(pq.size()>1){
TreeNode* left = pq.top();
pq.pop();
TreeNode* right = pq.top();
pq.pop();
TreeNode* newNode = new TreeNode(left->val + right->val);
newNode->left = left;
newNode->right = right;
pq.push(newNode);
}
return pq.top();
}
int main(){
vector<int> nums{1,3,4,6,7,8};
TreeNode* root = buildHuffmanTree(nums);
return 0;
}
```
该示例代码中,我们首先定义了一个结构体 `TreeNode` 来表示树节点,其中包含一个权值变量 `val`、左右子节点指针 `left` 和 `right`。
然后定义了一个比较结构体 `cmp`,来作为优先队列 `priority_queue` 的比较规则,这里规定了比较方式为比较节点的权值大小。
接着,我们定义了一个函数 `buildHuffmanTree` 来构建哈夫曼树,该函数接受一个整型数组 `nums` 作为参数,首先将每个元素构造成一个单独的节点,然后将所有节点加入到优先队列中。接下来,每次从队列中取出权值最小的两个节点,将它们合并成一个新的节点,并将新节点插入到优先队列中。最终,队列中只剩下一个节点,即为哈夫曼树的根节点,返回即可。
在 `main` 函数中,我们构造了一个整型数组 `nums`,包含了哈夫曼树的所有叶子节点的权值,然后调用 `buildHuffmanTree` 函数来构造哈夫曼树。