题意:
本题测试你对Huffman树构建的掌握程度。
请填写函数来构建一个棵Huffman树,返回树的根节点
思路:
①对数字排序。要插入树的数字存在vector,故先从小到大排序。
②进入循环。结束条件为存放数字的vector空。
③建节点,赋值。new父节点,左右儿子节点。若vector非空,则赋值给左右儿子节点。
④进入遍历num向量(用于存放每一次左右儿子节点之和的树)循环。若num中有树的值与左儿子或右儿子节点的值相同,则该树赋值给左儿子或右儿子且将该树从num删除。
⑤制作树。将左右儿子与父节点链接。
⑥判空。若vector 为空,退出主循环。
⑦更新向量,并排序。将新建的树的值与节点插入vector与num中,并将两个向量排序。
源码:
#include<vector>
#include<algorithm>
//struct BTreeNode{
// int value{0};
// BTreeNode* left_child{nullptr};
// BTreeNode* right_child{nullptr};
// BTreeNode( int value ){
// this->value = value;
// }
// BTreeNode(){
// this->value = 0;
// }
//};
BTreeNode* create_huffman_tree(const vector<int>& values) {
vector<int>values2(values);
vector<BTreeNode*>num;
sort(values2.begin(), values2.end()); //从小到大排序
while (1) {
BTreeNode* node = new BTreeNode;
BTreeNode* nodel = new BTreeNode;
BTreeNode* noder = new BTreeNode;
if (!values2.empty()) { //将要插入的值赋值给左右儿子节点
nodel->value = values2[0];
values2.erase(values2.begin(), values2.begin() + 1); //删除第一个元素
}
if (!values2.empty()) {
noder->value = values2[0];
values2.erase(values2.begin(), values2.begin() + 1); //删除第一个元素
}
for (int i = 0,l=1,r=1; i < num.size(); i++) { //对存放向量的节点遍历
if (l&&nodel->value == num[i]->value) { //若num中有相同的值则赋值给左节点,并删除
nodel = num[i];
num.erase(num.begin() + i, num.begin() + i+1);
l = 0;
continue;
}
if (r&&noder->value == num[i]->value) { //若num中有相同的值则赋值给左节点,并删除
noder = num[i];
num.erase(num.begin() + i, num.begin() + i + 1);
r = 0;
continue;
}
}
node->value = nodel->value + noder->value; //新建树
node->left_child = nodel;
node->right_child = noder;
if (values2.empty()) //判空
return node;
values2.insert(values2.begin(), node->value); //插入元素
num.insert(num.begin(), node); //插入备用树
sort(values2.begin(), values2.end()); //从小到大排序
}
}
ps:num向量类型是树;要先判空再进行向量更新和排序