问题
单项选择题 案例分析题
由权值为29、12、15、6、23的五个叶子节点构造的哈夫曼树为（1），其带权路径长度为（2）。
空白（2）处应选择（）
A.85
B.188
C.192
D.222
答案
参考答案：B
解析：哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶节点的权值乘上其到根节点的路径长度（若根节点为0层，叶节点到根节点的路径长度为叶节点的层数）。哈夫曼算法如下。①对给定的n个权值{W，W，W，…，W，…，W）构成n棵二叉树的初始集合F={T，T，T，…，T，…，T}，其中每棵二叉树T中只有一个权值为W的根节点，它的左右子树均为空。（为方便在计算机上实现算法，一般还要求以T的权值W的升序排列。）②在F中选取两棵根节点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根节点的权值为其左右子树的根节点的权值之和。③从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入集合F中。④重复②和③两步，直到集合F中只有一棵二叉树为止。由上述步骤构造出来的哈夫曼树是选项A，带权路径长度为（12+6）×3+（15+23+29）×2=188。