CSP-J 入门级 · CSP 2025 入门级第一轮 第 4 题

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

这题就是考哈夫曼树的构造和WPL计算。拿到题先别急着算，脑子里过一遍：把权值从小到大排，每次挑最小的两个合并，新生成的数放回队列里继续比，直到只剩一棵树。最后看每个原始权值在树里离根有几条边（深度），乘起来再相加就是答案。

最容易翻车的地方是合并后的处理：很多人以为把10和12合并成22后，下一步就该拿22和25合并了，或者忘了把新生成的22放回队列里和剩下的15、20、25一起重新选最小的两个。其实规则是“每次选当前所有节点里最小的两个”，所以第二步必须从{15,20,22,25}里挑15和20，而不是22和25。另外算WPL时也容易把深度数错，比如把10、12当成深度2，或者把15、20、25当成深度3，结果就会偏大或偏小。

这道题考查树形结构中的哈夫曼树（最优二叉树）及其带权路径长度（WPL）的计算。

概念拆解：哈夫曼树的核心就是让所有叶子节点的“权值×深度”之和最小。这里的“权值”就是题目给的10,12,15,20,25，可以理解为编码时出现的频率；“深度”是从根到该叶子经过的边数。WPL就是把每个叶子权值乘以它到根的距离，然后全部加起来。

构造过程（一步步来）： 初始时森林里有5个数：10, 12, 15, 20, 25。 第1步：挑最小的两个10和12，合并成22。森林变成：15, 20, 22, 25。 第2步：注意！新生成的22要放回队列，和剩下的15,20,25一起重新选最小的两个。这时候最小的是15和20，合并成35。森林变成：22, 25, 35。 第3步：再挑最小的两个22和25，合并成47。森林变成：35, 47。 第4步：最后合并35和47，得到根节点82。构造完成。

画树看深度： 根是82，左子树是35（由15和20组成），右子树是47（由22和25组成）。 22下面挂着10和12，所以10和12的深度是3；15、20、25的深度都是2。

WPL计算： 10×3 = 30 12×3 = 36 15×2 = 30 20×2 = 40 25×2 = 50 加起来：30+36+30+40+50 = 186。

避坑提醒：很多学生会在第二步误以为22比25小，就急着合并22和25，忘了15和20还在队列里且更小。记住口诀：每次合并后，新节点必须重新参与“最小两个”的角逐，不能跳过。另外算WPL时，深度数的是边数，不是层数（根在第0层，深度为0）。这里10和12确实到了第3层，深度就是3。

考情与趋势：从题库数据看，树形结构考点整体考频较高，2026年单年就有8题，说明这类题是高频常客。哈夫曼树更是重中之重，历年累计44题，2025年单年10题、2026年11题，呈现明显的上升趋势，尤其在GESP六级和CSP入门级中反复出现。这类题通常以单选题形式出现，直接给一组权值让你算WPL，或者问构造步骤。

预测：基于2025-2026年哈夫曼树考频激增（两年合计21题）且GESP六级占比超60%的趋势，未来两三年在入门级和GESP六级中仍会高频考查哈夫曼树的构造与WPL计算。命题人可能会在权值设计上增加干扰项（比如故意放一个接近的中间值），或者结合编码长度问法变相考查WPL。暂无足够数据预测是否会引入多叉哈夫曼树或动态更新权值的变种，但传统二叉哈夫曼树的单选/填空形式大概率持续稳定。