CSP-J 2025 第一轮 第 4 题：用权值 10、12、15、20、25 构造哈夫曼树的带权路径长度

题目

用 $5$ 个权值 $10, 12, 15, 20, 25$ 构造哈夫曼树，该树的带权路径长度是多少？

选项

• A. $176$
• B. $186$
• C. $196$
• D. $206$

答案

B

题解

构造哈夫曼树时，每次选取当前最小的两个权值合并，再把它们的和放回，直到只剩一个权值。

这道题的合并过程是：

1. 合并 $10$ 和 $12$，得到 $22$。剩余权值为 $15,20,22,25$。
2. 合并 $15$ 和 $20$，得到 $35$。剩余权值为 $22,25,35$。
3. 合并 $22$ 和 $25$，得到 $47$。剩余权值为 $35,47$。
4. 合并 $35$ 和 $47$，得到根节点 $82$。

带权路径长度等于所有叶子节点的“权值乘以到根的边数”之和，也等于构造过程中每次合并得到的新权值之和。因为每合并一次，被合并的两棵子树中的所有叶子都增加一层深度，对带权路径长度的增量恰好就是这次合并的权值之和。

因此：

$$ \mathrm{WPL}=22+35+47+82=186。 $$

答案选 B。