问题
单项选择题
带权为9,2,4,6的4个叶子结点构造一棵哈夫曼树,该树的带权路径长度为______。
A.21
B.41
C.36
D.39
答案
参考答案:D
解析:
本题考查哈夫曼树。哈夫曼树又称最优二叉树,是一种带权路径长度最短的树。路径是从树中一个结点到另一个结点之间的通路,路径上的分支数目称为路径长度。树的路径长度是从树根到每一个叶子之间的路径长度之和。结点的带权路径长度为从该结点到树根之间的长度与该结点权的乘积。哈夫曼是指含有n个权值分别为w1,w2,…,wn的n个叶子结点的二叉树中带权路径长度最小的那棵树。所以应该将权重最大的叶子结点距离根结点最近,权重次小的距离根结点次远,依次类推。所以WPL=9+6*2+(2+4)*3=39。