哈夫曼树

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();
}

3.哈夫曼编码