给定叶节点权值：(2，3，5，7，8，11)，构造哈夫曼树，并计算其带权路径长度WPL。

首先，我们需要将叶节点按照权值从小到大排序：(2，3，5，7，8，11)

然后，我们需要将权值最小的两个节点合并为一个新节点，其权值等于这两个节点的权值之和。这里我们可以选择先合并2和3，得到一个新节点5，然后将5和5合并，得到一个新节点10，再将7和8合并，得到一个新节点15，最后将10和15合并，得到一个根节点25。

构造出的哈夫曼树如下所示：

             25
            /  \
           10  15
          / \   / \
         5   5 7   8
             |   |
             2   3

根据定义，带权路径长度WPL等于每个叶节点的权值乘以它到根节点的路径长度之和，最后再把所有叶节点的WPL相加。因此，我们可以计算出每个叶节点的WPL如下所示：

WPL(2) = 2*3 = 6
WPL(3) = 3*3 = 9
WPL(5) = 5*2 = 10
WPL(7) = 7*2 = 14
WPL(8) = 8*2 = 16
WPL(11) = 11*2 = 22

然后，我们可以将每个叶节点的WPL相加，得到总的WPL：

WPL = 6 + 9 + 10 + 14 + 16 + 22 = 77

因此，构造出的哈夫曼树的带权路径长度为77。

相关问题

已知权值集合为{5,7,2,3,6,9}，要求给出哈夫曼树，并计算带权路径长度WPL。

好的，根据哈夫曼树的构建规则，我们先将权值从小到大排序得到{2,3,5,6,7,9}，然后构建哈夫曼树如下所示：

      32
    /    \
   12     20
  /  \   /  \
 5   7  6   9
    / \
   2   3

其中，每个叶子结点代表一个权值，叶子结点的权值即为该权值出现的次数，每个非叶子结点代表两个权值的合并，其权值为左右子树权值之和。

带权路径长度WPL定义为所有叶子结点的权值乘上其到根结点的路径长度之和，因此，WPL的计算公式为：

WPL = 5*2 + 7*2 + 6*2 + 9*2 + 3*3 + 2*3 = 74

因此，给定的权值集合的哈夫曼树的带权路径长度为74。

已知权值集合为{5,7,2,3,6,9}，要求给出哈夫曼树，并计算带权路径长度WPL,写出c++算法

首先，哈夫曼树的构建需要用到最小堆，因此我们需要先实现最小堆。

#include <iostream>
#include <vector>
using namespace std;

template<class T>
class MinHeap {
private:
    vector<T> heap;
    void shift_up(int idx) {
        if (idx == 0) return;
        int parent = (idx - 1) / 2;
        if (heap[parent] > heap[idx]) {
            swap(heap[parent], heap[idx]);
            shift_up(parent);
        }
    }
    void shift_down(int idx) {
        int left = idx * 2 + 1;
        int right = idx * 2 + 2;
        int smallest = idx;
        if (left < heap.size() && heap[left] < heap[smallest]) {
            smallest = left;
        }
        if (right < heap.size() && heap[right] < heap[smallest]) {
            smallest = right;
        }
        if (smallest != idx) {
            swap(heap[idx], heap[smallest]);
            shift_down(smallest);
        }
    }
public:
    void push(T val) {
        heap.push_back(val);
        shift_up(heap.size() - 1);
    }
    void pop() {
        if (heap.empty()) return;
        heap[0] = heap.back();
        heap.pop_back();
        shift_down(0);
    }
    T top() {
        return heap.front();
    }
    bool empty() {
        return heap.empty();
    }
};

接下来，我们可以使用最小堆来构建哈夫曼树。对于给定的权值集合，我们可以将它们放入最小堆中，并不断地取出最小的两个权值进行合并，直到堆中只剩下一个节点为止。

#include <iostream>
#include <vector>
using namespace std;

template<class T>
class TreeNode {
public:
    T val;
    TreeNode<T> *left;
    TreeNode<T> *right;
    TreeNode(T val) : val(val), left(nullptr), right(nullptr) {}
};

template<class T>
TreeNode<T> *build_huffman_tree(vector<T> weights) {
    MinHeap<TreeNode<T> *> heap;
    for (auto weight : weights) {
        heap.push(new TreeNode<T>(weight));
    }
    while (!heap.empty()) {
        TreeNode<T> *left = heap.top();
        heap.pop();
        if (heap.empty()) {
            return left;
        }
        TreeNode<T> *right = heap.top();
        heap.pop();
        TreeNode<T> *parent = new TreeNode<T>(left->val + right->val);
        parent->left = left;
        parent->right = right;
        heap.push(parent);
    }
    return nullptr;
}

最后，我们可以计算哈夫曼树的带权路径长度，即将每个叶子节点的权值乘以到根节点的距离，再将所有叶子节点的带权路径长度相加得到的值。可以使用递归来实现。

template<class T>
int calc_wpl(TreeNode<T> *root, int depth = 0) {
    if (!root->left && !root->right) {
        return root->val * depth;
    }
    return calc_wpl(root->left, depth + 1) + calc_wpl(root->right, depth + 1);
}

完整的c++代码如下：