带权路径长度怎么算
- 原创
- |
- 浏览:33473
- |
- 更新:
方法/步骤
一般的,我们是可以用常规的构造哈夫曼树求带权路径长度。
树的带权路径长度(Weighted Path Length of Tree,简记为WPL)
计算结点的带权路径长度:结点到树根之间的路径长度与该结点上权的乘积。
- 本页面未经授权抓取自百度经验
带权路径长度WPL(Weighted Path Length)最小的二叉树,也称为最优二又树。
在这里简单举个例子说一下:
题目:
给定6个字符(a,b,c,d,e,f),它们的权值集合W =(2,3,4,7,8,9),试构造关于W的一棵哈夫曼树,求其带权路径长度WPL。
解:根据题意构造关于W的哈夫曼树如1图所示:
那么其带权路径长度WPL=(9+7+8)×2+4×3+(2+3)×4=80。
(结点到树根之间的路径长度与该结点上权的乘积)
构造哈夫曼树的办法是:在W中选出两个权小结点,并同时计算出它们的和,如果两个数的和正好是下一步的两个最小数的其中的一个,那么这个树直接往上生长就可以了,如果这两个数的和比较大,不是下一步的两个最小数的其中一个,那么就并列生长。
END
经验内容仅供参考,如果您需解决具体问题(尤其法律、医学等领域),建议您详细咨询相关领域专业人士。
作者声明:本篇经验系本人依照真实经历原创,未经许可,谢绝转载。
展开阅读全部









