CSP-S 提高级 · CSP 2026 提高级第一轮 第 2 题

【单选】用权值 {1, 2, 3, 4, 5, 6, 7, 8} 构造哈夫曼树，其带权路径长度是（ ）。

哈夫曼树用"每次取最小的两个权值合并"的贪心过程构造，带权路径长度 WPL 恰好等于"所有合并代价之和"。把 1…8 依次按规则合并，把每次合并得到的数加起来即可。

只算最后一次合并的 36（等于总权重，也是错选 A 的来源）；或者把"合并次数"当成 WPL；也会忘了合并后的新结点要放回集合参与后续比较。

解析

本题考查哈夫曼树的构造与带权路径长度（WPL）。

关键性质

• WPL = Σ(权值 × 该叶子的深度)；
• 用哈夫曼算法（每次取当前最小的两个权值合并，把和放回集合）构造出的树 WPL 最小；
• 有一条极好用的捷径：WPL 恰好等于每一次合并产生的"新结点权值"之和（因为每个新结点内部包含的路径长度增量正好等于它的权值）。

逐步合并

初始集合 {1, 2, 3, 4, 5, 6, 7, 8}：

WPL = 3 + 6 + 9 + 12 + 15 + 21 + 36 = 102，选 D。

交叉验证（按深度算）

合并完成后各叶子的深度：8 和 7 在第 2 层，6、4、5 在第 3 层，3 在第 4 层，1 和 2 在第 5 层。

WPL = 8×2 + 7×2 + 6×3 + 4×3 + 5×3 + 3×4 + 1×5 + 2×5 　　 = 16 + 14 + 18 + 12 + 15 + 12 + 5 + 10 = 102 ✓ 与合并法一致。

其他选项为什么错

• A. 108：把 8 个叶子当成"完美二叉树"（深度全为 3），3 × 36 = 108，这是非最优的结果；
• B. 96、C. 99：合并非最优顺序（如先合大的），WPL 偏小但树不合法或对应其他权值；
• 常见陷阱还有把最后一次合并的 36 当成答案。

记忆点

• 权值越大的叶子应当越靠近根（深度越小）；
• 8 个叶子的最优深度分布一般是 2,2,3,3,3,3,4,5 这类"局部平衡"结构；
• 手算技巧：列出每一步的合并代价求和，比画树、数深度更快也更不易错。