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

admin2015-12-30 3

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

选项 A、27
B、46
C、54
D、56

答案B

解析将哈夫曼树的思想推广到三叉树的情形。为了构成严格的三叉树，需添加权为0的虚叶结点，对于严格的三叉树(n₀-1)％(3-1)=u=1≠0，需要添加m-u-1=3-1-1个叶结点，说明7个叶结点刚好可以构成一个严格的三叉树。按照哈夫曼树的原则，权为0的叶结点应离树根最远，构造最小带权生成树的过程如下：