带权路径长度怎么算

  • 原创
  • |
  • 浏览:33473
  • |
  • 更新:

数据结构是个让很多人头疼的东西,但是它的用处又是如此广泛,让不少人对它又爱又恨的。那么在数据结构中该如何计算带权路径长度呢,下面一起来看看吧。

带权路径长度怎么算

工具/原料

  • 话题

方法/步骤

  1. 1

    一般的,我们是可以用常规的构造哈夫曼树求带权路径长度。

    树的带权路径长度(Weighted Path Length of Tree,简记为WPL)

    计算结点的带权路径长度:结点到树根之间的路径长度与该结点上权的乘积。

    带权路径长度怎么算
  2. 1
    本页面未经授权抓取自百度经验
  3. 2

    带权路径长度WPL(Weighted Path Length)最小的二叉树,也称为最优二又树。

     

     

  4. 3

    在这里简单举个例子说一下:

    题目:

    给定6个字符(a,b,c,d,e,f),它们的权值集合W =(2,3,4,7,8,9),试构造关于W的一棵哈夫曼树,求其带权路径长度WPL。

    解:根据题意构造关于W的哈夫曼树如1图所示:

    带权路径长度怎么算
  5. 4

    那么其带权路径长度WPL=(9+7+8)×2+4×3+(2+3)×4=80。

    (结点到树根之间的路径长度与该结点上权的乘积)

    带权路径长度怎么算
  6. 5

    构造哈夫曼树的办法是:在W中选出两个权小结点,并同时计算出它们的和,如果两个数的和正好是下一步的两个最小数的其中的一个,那么这个树直接往上生长就可以了,如果这两个数的和比较大,不是下一步的两个最小数的其中一个,那么就并列生长。

    带权路径长度怎么算
    END

注意事项

  • 多思考,勤练习
经验内容仅供参考,如果您需解决具体问题(尤其法律、医学等领域),建议您详细咨询相关领域专业人士。
作者声明:本篇经验系本人依照真实经历原创,未经许可,谢绝转载。
展开阅读全部