哈夫曼树
1.定义
带权路径长度 WPL 最小的的二叉树即使哈夫曼树
带权路径 = 到此节点经过的边数 * 结点上的权值
2.构造哈夫曼树
选出数组中最小的两个节点作为左右节点,根节点的权值为左右孩子权值之和,然后继续将根节点放入数组中,重新选出两个最小的根节点。
bool myfunction(BTreeNode* i, BTreeNode* j) { return (i->value < j->value); };
BTreeNode* create_huffman_tree(const vector<int>& values) {
vector<BTreeNode*> BT;
int i;
for (i = 0; i < values.size(); i++)
{
BTreeNode* newnode = new BTreeNode(values[i]);
BT.push_back(newnode);
}
while (BT.size() > 1)
{
sort(BT.begin(), BT.end(), myfunction); // 从小到大排序
BTreeNode* newnode = new BTreeNode();
BTreeNode* left = *BT.begin();
BT.erase(BT.begin());
BTreeNode* right = *BT.begin();
BT.erase(BT.begin()); // 取出两个最小结点
newnode->left_child = left;
newnode->right_child = right;
newnode->value = left->value + right->value;
BT.push_back(newnode);
}
return *BT.begin();
}