`
lmoyong
  • 浏览: 3071 次
  • 性别: Icon_minigender_1
  • 来自: 太原
文章分类
社区版块
存档分类
最新评论

哈夫曼树

 
阅读更多

1、定义

 

给定n个权值为n的叶子结点,构造一科二叉树,如果带权路径长度达到最小,成这样的二叉树为最优二叉树,也就是哈夫曼树(Huffman tree)

 

2、构造

 

假设有n个权值,则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1,w2,…,wn,则哈夫曼树的构造规则

为:
(1) w1,w2,…,wn看成是有n 棵树的森林(每棵树仅有一个结点)


(2) 在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和;

 

(3)从森林中删除选取的两棵树,并将新树加入森林;

(4)重复(2)(3)步,直到森林中只剩一棵树为止,该树即为我们所求得的哈夫曼树。 

    下面给出哈夫曼树的构造过程,假设给定的叶子结点的权分别为1,5,7,3,则构造哈夫曼树过程如图6-29所示。 从图6-29可知,n 个权值构造哈夫曼树需n-1次合并,每次合并,森林中的树数目减1,最后森林中只剩下一棵树,即为我们求得的哈夫曼树。

 

  • 大小: 13.6 KB
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics