问题 单项选择题

若以4,5,6,3,8作为叶子结点的权值构造哈夫曼树,则带权路径长度是 (33)

A.55

B.68

C.59

D.28

答案

参考答案:C

解析:

[分析]:
本题考查带权哈夫曼树的构造及求带权路径长度。
树的路径长度是从树根到树中每一结点的路径长度之和,结点到树根之间的路径长度与该结点上权的乘积,称为结点的带权路径长度。树中所有叶结点的带权路径长度之和,称为树的带权路径长度。
在权为w1,w2,…,wn的n个叶子所构成的所有二叉树中,带权路径长度最小(即代价最小)的二叉树称为最优二叉树或哈夫曼树。
假设有n个权值,则构造出的哈夫曼树有n个叶子结点。n个权值分别设为w1,w2,…, wn,则哈夫曼树的构造规则为:
(1)将w1,w2,…,wn看成是有n棵树的森林(每棵树仅有一个结点);
(2)在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和;
(3)从森林中删除选取的两棵树,并将新树加入森林。
重复第(2)步和第(3)步,直到森林中只剩一棵树为止,该树即为所求的哈夫曼树。
根据哈夫曼树的构造规则,不难得到题目中给出叶子结点对应的哈夫曼树,得到哈夫曼树后我们再计算带权路径长度=3×(3+4)+2×(5+6+8)=59。

单项选择题
名词解释