由权值为 9、2、1、6、4 五个叶子结点构造哈夫曼树为（请作答此空），其带权路径长度为（ ）。
- A.见图A
- B.见图B
- C.见图C
- D.见图D
正确答案及解析
正确答案
A
解析
本题考察最优二叉树（哈夫曼树）构造和带权路径长度计算。构造最优二叉树哈夫曼算法如下：（1）、根据给定n个权值{w1, w2, …，wn}， 构成n棵二叉树集合F= {T1, T2, …Tn}，其中，每棵树Ti中只有一个带权为wi根结点，其左、右子树均空。（2）、在F中选取两棵权值最小树作为左、右子树构造一棵新二叉树，新构造二叉树根结点权值为其左、右子树根结点权值之和。（3）、从F中删除这两棵树，同时将新得到二叉树加入到F中。（4）、重复（2）、（3）步，直到F中只含一棵树时为止，这棵树便是最优二叉树(哈夫曼树)。所以由权值为 9、2、1、6、4 五个叶子结点构造哈夫曼树为（红色圈内填写数字为构造新节点，在选项中没有体现出来，用空白圆圈进行了替代）：
结点带权路径长度为从该结点到树根之间路径长度与该结点权值乘积，而树带权路径长度为树中所有叶子结点带权路径长度之和。所以构造哈夫曼树带权路径长度为9*1+6*2+4*3+（1+2）*4=9+12+12+12=45。
