• 求Huffman树的带权路径长度


    Huffman树的建立过程:

    首先得到整个叶子结点的集合:

     求Huffman树的带权路径长度算法:

    书上讲常见的求Huffman树的带权路径长度算法为:从叶子结点权值乘路径长度:

    WPL=7*2+5*2+5*2+3*3+2*3=49

    另外一种求WPL的算法为:非叶子几点权值之和:

    WPL=22+12+10+5=49

    这种方法并不是毫无道理,应为同一个结点下的两个叶子结点的路径长度是一样的,叶子结点的路径长度完全可以反映到其双亲结点上去。

    这种算法较为简单,直接可以忽略建树的步骤,直接求出WPL(当然要明白如何求WPL)

    算法的主要思想:

    1.首先将得到的元素集合进行排序;(降序。升序也行,请自己尝试)

    2.数组末尾两个元素求和(俩结点的双亲结点权值),将其结果放在数组倒数第二个位置上并且数组长度减1

    3.累加每次求和结果。(即就是非叶子结点的权值)

    注意:当集合元素过小时不适用本算法,需要特殊处理,不然会发生数组越界。

    C语言实现:

    1. #include
    2. #include
    3. // 算法思想:
    4. // 本题主要为求哈夫曼树的带权路径长度,故未将重点放在建树上
    5. // Huffman树的带权路径长其实就是其非叶子结点的权值和
    6. //排序算法
    7. void sort(int *data,int n){
    8. int i,j;
    9. for(i =0;i
    10. for (j = 0; j< n-i; ++j) {
    11. if(data[j]1]){
    12. int t = data[j+1];
    13. data[j+1] = data[j];
    14. data[j] = t;
    15. }
    16. }
    17. }
    18. }
    19. int main() {
    20. int n, *data,i,sum =0,x;
    21. scanf("%d", &n);
    22. //动态开辟数组
    23. data = (int *) malloc(sizeof(int)*n);
    24. for(i =0;i
    25. scanf("%d",&data[i]);
    26. if(n<=2){ //当集合过小时,不适用本算法,特殊处理
    27. for(i =0;i
    28. sum += data[i];
    29. printf("%d",data[0]+data[1]);
    30. return 0;
    31. }
    32. while(1){
    33. sort(data,n); //先对数组排序(降序)
    34. x=data[n-1]+data[n-2]; //将末尾两元素求和(上层结点权值)
    35. data[n-2] = x; //消除原来两元素,增加新元素
    36. sum+=x; //累计非叶子结点权值和
    37. --n; //数组长度减1
    38. if(n==1) //当数组中只剩下一个元素时,得出结果
    39. break;
    40. }
    41. printf("%d\n",sum);
    42. }

    运行测试:

     

  • 相关阅读:
    安卓Compose(一)
    [USACO2012-Mar-Silver] Flowerpot 题解(单调队列 c++)
    Python「面向对象基本语法2」引用概念、方法中的self参数、代码示例
    22年牛客网最全面的Java面试手册,助你金九银十轻松过关
    Typora~阿里云OSS+Typora+PicGo解决方案
    Python爬虫库urllib使用详解
    删除自己在知乎的所有回答
    【Django】开发日报_1.1_Day:模板语法
    【iOS】MVC
    【JavaScript】浏览器支持ES6和使用export import语法
  • 原文地址:https://blog.csdn.net/weixin_64811333/article/details/128116060