单选题
由权值为29、12、15、6、23的5个叶子节点构造的哈夫曼树为______，其带权路径长度为______。
单选题
A．
B．
C．
D．
B．
C．
D．
【正确答案】
A
【答案解析】
【正确答案】
B
【答案解析】最优树，又称哈夫曼树，是一类带权路径长度最短的树。
哈夫曼算法如下。
(1)根据给定的n个权值{W 1 ，W 2 ，…，W n }，构成n棵二叉树的集合F={T 1 ，T 2 ，…，T n }，其中每棵二叉树T i 中只有一个权为W i 的根节点，其左右子树均空。
(2)在F中选取两棵根节点的权值最小的树作为左右子树，构造一棵新的二叉树，且置新的二叉树的根节点的权值为其左右子树上根节点的权值之和。
(3)在F中删除这两棵树，同时将新得到的二叉树加入F中。
重复(2)和(3)，直到F只含一棵树为止。这棵树便是所求的哈夫曼树。
满足题目要求的是A答案：(12+6)×3+(15+23+29)×2=188，带权路径长度为188。
哈夫曼算法如下。
(1)根据给定的n个权值{W 1 ，W 2 ，…，W n }，构成n棵二叉树的集合F={T 1 ，T 2 ，…，T n }，其中每棵二叉树T i 中只有一个权为W i 的根节点，其左右子树均空。
(2)在F中选取两棵根节点的权值最小的树作为左右子树，构造一棵新的二叉树，且置新的二叉树的根节点的权值为其左右子树上根节点的权值之和。
(3)在F中删除这两棵树，同时将新得到的二叉树加入F中。
重复(2)和(3)，直到F只含一棵树为止。这棵树便是所求的哈夫曼树。
满足题目要求的是A答案：(12+6)×3+(15+23+29)×2=188，带权路径长度为188。