哈夫曼编码

原创
2019/01/16 15:26
阅读数 596

哈夫曼编码的基本思想是以字符的使用频率作为权构建一颗哈夫曼树,然后利用

哈夫曼树对字符进行编码

哈夫曼算法采用的贪心策略是每次从树的集合中取出没有双亲权值最小的两棵作为左右子树,

构造一颗新树,新树根节点的权值为其左右孩子结点权值之和,将新树插入到树的集合中

 

 

构造哈夫曼树-完美图解

1 初始化,构造单节点树集合

2从集合T中取出没有双亲且权值最小的两棵树,将新树的根加入T集合,将原来两个树从集合中删除

3重复上面的方法

4直到集合T中只有一个树,哈夫曼树构造成功

5约定左分支上编码为0,右分支上编码为1

6可以读出从根节点到每个叶子节点的编码

 

展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部