对于给出一组权构造具有最小带权外部路径长度的扩充二叉树，并求出它带权外部路径长度请给出c++语言实现

这里提供一种基于贪心算法的C++实现：

#include <iostream>
#include <vector>
#include <queue>
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* createHuffmanTree(vector<int>& weights) {
    priority_queue<TreeNode*, vector<TreeNode*>, cmp> pq; // 定义小根堆
    for (int i = 0; i < weights.size(); i++) {
        pq.push(new TreeNode(weights[i])); // 将节点加入小根堆
    }
    while (pq.size() > 1) {
        TreeNode* left = pq.top(); // 取出堆顶节点，即权值最小的节点
        pq.pop();
        TreeNode* right = pq.top();
        pq.pop();
        TreeNode* parent = new TreeNode(left->val + right->val); // 将左右子节点合并，构造出父节点
        parent->left = left;
        parent->right = right;
        pq.push(parent); // 将父节点加回小根堆中
    }
    return pq.top(); // 最终堆中只剩下一个根节点，即为构造好的扩充二叉树
}

// 计算带权外部路径长度
int getWeightedExternalPathLength(TreeNode* root, int depth) {
    if (root == NULL) {
        return 0;
    }
    if (root->left == NULL && root->right == NULL) { // 叶子节点
        return depth * root->val;
    }
    return getWeightedExternalPathLength(root->left, depth + 1) + getWeightedExternalPathLength(root->right, depth + 1);
}

int main() {
    vector<int> weights = {1, 2, 3, 4, 5};
    TreeNode* root = createHuffmanTree(weights);
    int wpl = getWeightedExternalPathLength(root, 0);
    cout << "带权外部路径长度为：" << wpl << endl;
    return 0;
}

在该代码中，我们首先定义了一个二叉树节点结构体 `TreeNode`，包含节点权值 `val`、左子节点指针 `left` 和右子节点指针 `right`。然后，我们定义了一个节点比较函数 `cmp`，用于优先队列排序，将节点按照权值从小到大排列。

接着，我们实现了构造最小带权外部路径长度的扩充二叉树的函数 `createHuffmanTree`。首先，我们定义了一个小根堆 `pq`，将所有节点加入小根堆。然后，每次从小根堆中取出两个权值最小的节点，将它们合并成一个父节点，再将父节点加入小根堆中。最终，小根堆中只剩下一个根节点，即为构造好的扩充二叉树。

最后，我们实现了计算带权外部路径长度的函数 `getWeightedExternalPathLength`。我们采用递归的方式计算带权外部路径长度。如果当前节点是叶子节点，直接返回节点权值乘以当前深度。否则，递归计算左右子树的带权外部路径长度之和。

在 `main` 函数中，我们构造了一个权值数组 `{1, 2, 3, 4, 5}`，并调用 `createHuffmanTree` 函数构造出带权外部路径长度最小的扩充二叉树。然后，调用 `getWeightedExternalPathLength` 函数计算带权外部路径长度，并输出结果。