题14

题14

题目

Q:【2013 统考真题】已知三叉树 中 6 个叶结点的权分别是 的带权 (外部) 路径长度最小是 ( ).
A. 27 B. 46 C. 54 D. 56

分析

A:基于贪心做这个合并，也就是每次选最小的来合并，合并出来的就是权值，重新再加入参与合并

解

题中的三叉树为使 WPL 最小,必须构造三叉哈夫曼树,应满足 的条件,因此需添加 1 个权值为 0 的虚叶结点, 说明 7 个叶结点刚好可构成一棵严格的三叉树。
按照哈夫曼树的原则, 权为 0 的叶结点应离树根最远, 构造三叉哈夫曼树的过程如下:
① 合并权值最小的三个结点 ,得到新结点的权值 ,剩下 。
② 合并权值最小的三个结点 ,得到新结点的权值 ,剩下 。
③ 合并权值最小的三个结点 ,得到新结点的权值 ,仅有 27,建树完成。
权值 深度
或

每个分支结点的权值都累加了其下面所有分支结点的权值, 因此采用第二种方法更方便。