哈夫曼树及带权路径长度WPL值

哈夫曼树,又称最优树,是一类带权路径长度最短的树。(了解即可)

带权路径长度WPL值的求法,就是每个带权*(该结点到根结点的长度)的总分,如下图b所示,7、5到根结点长度为3,4到根结点的长度为2,2到根结点的长度为1。WPL=7*3+5*3+4*2+2*1=46。

哈夫曼编码(二进制前缀编码),很简单的,左子树是0,右子树是1,

设计哈夫曼树

注意:如何选择下面的值进行树生长呢?分两种情况

  1. 如果新得到值在即将合成两个结点最小的值中间,则选择即将中值最小的结点进行树生长
  2. 如果新得到值等于或大于即将合成两个结点最小的值,则即将合成的结点选择并列生长
赞赏

微信赞赏支付宝赞赏

213 次阅读量

发表评论