若某二叉树有 5 个叶结点，其权值分别为 10、12、16、21、30，则其最小的带权路径长度（wpl）是：

### 回答1： 根据给出的条件，我们可以将叶子节点的权值从小到大排序为：10，12，16，21，30。 接下来，我们可以根据哈夫曼编码的规则来构造哈夫曼树。 首先，我们找到权值最小的两个叶子节点，将它们合并成一个新的节点，其权值为它们的和，即10+12=22。然后，我们将这个新节点插入到原来的叶子节点的位置上，得到以下的树形结构： ``` 22 / \ 10 12 / \ 16 21 / 30 ``` 接下来，我们再次找到权值最小的两个叶子节点，将它们合并成一个新的节点，其权值为它们的和，即16+21=37。然后，我们将这个新节点插入到原来的叶子节点的位置上，得到以下的树形结构： ``` 59 / \ 22 37 / \ / \ 10 12 16 21 / 30 ``` 重复上述步骤，直到所有的叶子节点都被合并为一个根节点。最终得到的哈夫曼树如下： ``` 118 / \ / \ / \ / \ / \ / \ 59 59 / \ / \ 22 37 22 37 / \ / \ / \ / \ 10 12 16 21 16 21 30 10 ``` 最小带权路径长度（WPL）定义为叶子节点的权值与其到根节点的路径长度的乘积之和。因此，我们可以计算出最小带权路径长度为： ``` WPL = 10*3 + 12*3 + 16*4 + 21*4 + 30*4 = 226 ``` 因此，该二叉树的带权路径长度为226，即最小带权路径长度为226。 ### 回答2： 首先需要了解什么是二叉树的带权路径长度（wpl）：指二叉树中每一个叶子结点的权值乘上它到根结点的路径长度之和，即以叶子结点为权值的权路径长度之和。最小的带权路径长度指该二叉树中，最优解中的权值和。 根据哈夫曼编码的思想，可以利用贪心算法来求解带权路径长度的最小值。 步骤如下： 1. 根据给定的权值构建哈夫曼树（哈夫曼树是带权路径长度最短的树），将最小的两个权值相加，作为它们共同的父节点的权值，重复此过程直至构建出哈夫曼树。 2. 对于每一次的合并操作，都要计算该节点的带权路径长度，即它的权值乘以它到根节点的距离。对每个节点的带权路径长度进行累加，得到该二叉树的带权路径长度。 3. 计算出二叉树的带权路径长度之和，即为该二叉树的最小带权路径长度。 由给定的权值构建出哈夫曼树如下图： 105 / \ 46 59 / \ / \ 21 25 30 29 \ / \ 10 16 13 在哈夫曼树中，所有叶子结点的带权路径长度之和即为最小的带权路径长度。所以5个叶节点的权值乘以它们到根节点的距离分别为： 10 * 3 + 12 * 3 + 16 * 2 + 21 * 2 + 30 * 2 = 226 因此，最小带权路径长度为 226。 ### 回答3： 根据哈夫曼树的构造方法，我们可以先将这 5 个叶节点按照权值从小到大排序，得到序列 10、12、16、21、30。接下来根据哈夫曼树的构造规则，我们在每一次构造的过程中，都会选择两个权值最小的节点进行合并，形成一个新的节点，其权值为两个节点权值之和。因此，我们可以模拟构造哈夫曼树的过程，具体步骤如下： 1. 选择权值最小的两个节点 10 和 12，将它们合并为一个新节点，权值为 22，得到以下树形结构： 22 / \ 10 12 2. 选择权值最小的两个节点 16 和 21，将它们合并为一个新节点，权值为 37，得到以下树形结构： 22 37 / \ / \ 10 12 16 21 3. 最后，将上一步得到的两个子树合并为一个树，得到以下树形结构： 95 ______|______ | | 37 58 ___|___ ___|___ | | | | 16 21 22 30 最终得到的树就是哈夫曼树，其带权路径长度为： 10 × 2 + 12 × 2 + 16 × 2 + 21 × 2 + 30 × 1 = 118 因此，这个二叉树的最小带权路径长度为 118。