哈夫曼树-最优二叉树

带权值的叶节点:就是一个描述这个节点使用频率的系数,越大,表明经常要访问到。

结点路径:从根结点到叶节点要经过的节点数。

树的带权路径长度WPL: 将每个叶节点的权值和它的路径相乘 累加起来的和。


哈夫曼树就是这个WPL值最小的树,要将一颗树改造成哈夫曼树,那么就要将权重值高的放在离根节点相近的地方。

  1. 将所有的叶子子节点(子树)从小到大排列

  2. 取两个权值最小的子结点,较小的做左孩子,较大的做右孩子,构成一个新的树,根节点为新的,叫他为T吧。

  3. 计算T的权值,为两个子节点权值的和,将T放回到1的队伍中,继续2步骤直到队伍只剩下一个根节点了。


首页 我的博客
粤ICP备17103704号