题目

已知三叉树 T 中 6 个叶结点的权分别是 2，3，4，5，6，7，T 的带权(外部)路径长度最小是( )。

错因

A

把"哈夫曼树根节点的权值"当成 WPL 答了。根权 = 所有叶权之和 = 2+3+4+5+6+7 = 27——这只是叶权总和，不是 WPL。WPL = （ 是叶子深度），路径长度被忽略了。

C

忘了补虚节点就硬构造三叉哈夫曼。6 个叶子直接每三个合并：第一轮 {2,3,4} → 9，第二轮 {5,6,7} → 18，剩 {9, 18} 只能两两合并退化成二叉。最终 WPL = (2+3+4)×2 + (5+6,7)×2 = 18 + 36 = 54。这个数对应"二叉哈夫曼"，不是三叉的最优解。

D

忘了补虚节点而且合并顺序错：第一轮 {2,3,4}→9，第二轮取最小三个 {5,6,9}→20，剩 {7, 20}。叶子深度：2、3、4 在最深层 3，5、6 在层 2，9 是中间节点不算，7 在层 1，20 也是中间。WPL = (2+3+4)×3 + (5+6)×2 + 7×1 = 27 + 22 + 7 = 56。这是"既没补虚节点又选错合并对象"的双重错误。

总解析

关键陷阱：n 个叶子能否直接做 k 叉哈夫曼？

k 叉哈夫曼每次合并消去 个节点、新增 个节点，净减 。要从 个叶子合并到只剩 1 个根，需要 次合并。

若 ，最后一轮凑不出 个节点。补救：在叶子集合里添加权值为 0 的虚节点，让 能被 整除。

本题 ，，需要补 1 个虚节点（权 0）。

构造（k=3，权值集合 {0, 2, 3, 4, 5, 6, 7}）：

轮次	取最小三个	合并出新节点	剩余权值多重集
1
2
3		（根）

叶子深度（按合并顺序追踪）：

• 6, 7：在第 3 轮直接挂到根下 → 深度 1
• 4, 5：在第 2 轮挂到 14 下，14 在第 3 轮挂到根下 → 深度 2
• 2, 3, 0：在第 1 轮挂到 下， 在第 2 轮挂到 14 下，14 又挂到根下 → 深度 3

WPL 计算（虚节点权 0，对 WPL 无贡献）：

为什么补虚节点能让 WPL 更小？把"最深层的位置"留一个给权 0 的虚节点，相当于"白嫖"了一个深位置不付权值代价；真正的小权叶子被推到次深层，乘的深度就小了。如果不补、硬把所有 6 个叶子挤到二叉拓扑里，深度都是 2，每个权都被乘 2，加起来反而更大（54）。

最终答案是 B（46）。