首页 > 试题广场 > 由权值分别为1、20、23、3、10的叶子节点生成一颗哈夫曼树,它的带权路...
[单选题]
由权值分别为1、20、23、3、10的叶子节点生成一颗哈夫曼树,它的带权路径长度为()
  • 119
  • 90
  • 80
  • 60

2个回答

添加回答
答案是不是错的啊?为什么我算出来是109啊,有无大佬给我解释啊
发表于 2018-07-11 21:17:09 回复(1)
n个叶节点组成的所有二叉树中,带权路径长度最小的二叉树称为哈夫曼树或最优二叉树。
解法:给定叶节点的两个带权最小值相加代入累加器中,然后吧最小值去掉,加入相加取得的值。知道数组中只剩一个值。
function count(arr){
var sum=0;
countsum(arr,sum); 
return sum;
}
function countsum(arr,sum){
while(arr.length>1){
 arr.sort(function(a,b){
  return a-b;});
  var s=arr[0]+arr[1];
   sum+=s;
   count(arr.splice(0,2,s),sum);   
} 
return sum+arr[0];
}  

发表于 2018-07-11 17:01:31 回复(0)
牛客网,程序员必备求职神器
QQ群:169195721
微 信:www_nowcoder_com 关注
微 博:牛客网 关注

扫一扫,把题目装进口袋