频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
Huffman tree(赫夫曼树、霍夫曼树、哈夫曼树、最优二叉树)
2015-08-02 10:28:06         来源:flyfish1986的专栏  
收藏   我要投稿

Huffman tree(赫夫曼树、霍夫曼树、哈夫曼树、最优二叉树)

flyfish 2015-8-1

Huffman tree因为翻译不同所以有其他的名字 赫夫曼树、霍夫曼树、哈夫曼树
定义引用自严蔚敏《数据结构》
路径
从树中一个结点到另一个结点之间的分支构成两个结点之间的路径.

路径长度
路径上的分支数目称作路径长度。

树的路径长度
树的路径长度就是从根节点到每一结点的路径长度之和。

结点的带权路径长度
结点的带权路径长度就是从该结点到根节点之间的路径长度与结点上权的乘积。

树的带权路径长度
树的带权路径长度就是树中所有叶子结点的带权路径长度之和,通常记做WPL。

Huffman tree
假设有n个权值{w1,w2,…wn},构造一棵有n个叶子结点的二叉树,每个叶子结点带权wi,则其中带权路径长度WPL最小的二叉树称作Huffman tree 。

假设有一个字符串每个字符出现的次数如下
A:5
B:15
C:40
D:30
E:10
将字符按照出现次数从小到大排序形成一个有序序列
这里写图片描述
自底向上建树过程
第一步
这里写图片描述

第二步
这里写图片描述

第三步
这里写图片描述

第四步
这里写图片描述

构造完成<喎"/kf/ware/vc/" target="_blank" class="keylink">vcD4NCjxwPjxzdHJvbmc+uMXE7rK5s+Q8L3N0cm9uZz48L3A+DQo8cD48aW1nIGFsdD0="这里写图片描述" src="/uploadfile/Collfiles/20150802/20150802090847408.png" title="" />

 

点击复制链接 与好友分享!回本站首页
上一篇:hihoCoder_#1066_无间道之并查集
下一篇:leetcode-242-Valid Anagram
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站