`
369540808
  • 浏览: 194351 次
文章分类
社区版块
存档分类
最新评论

数据结构--哈夫曼树

 
阅读更多

哈夫曼树是二叉树的一种。被称为最优二叉树。实际应用中最重要的是带权路径长度。

基本术语:

树的路径长度:树中每个结点的路径长度之和。

权:附加在树节点上,表示出现的概率。

树的带权路径长度:所有叶子结点带权长度之和。


看实例:


D的结点路径长度:从dA的路径,共走了两条边,所以为2树中的叶子结点D,EF。结点路径都为2。假设子结点的权都为2,那么树的带权路径长度=2*2+2*2+2*2=12

哈夫曼树实现:


实质是求树的带权路径长度的最小值。使算法更简便,访问的路径最小。

描述:

1)从给定值中构造森林F,且森林中的每个二叉树只有根结点。

2)从F中选择最小的两个二叉树构成新的二叉树T,权值为两个二叉树的和。

3)重复上述2,直到F中只含有一个二叉树。

实例


1)首先看给定的权值7,4,3,8,9.

转为只有根结点的二叉树。


2)找到最小的两个二叉树进行合并,成为新的二叉树。

可以查出4,3量权值是最小的。


构造二叉树



再将合并的二叉树和剩下二叉树中找合并的最小值进行合并,依次类推。顺序图如下


8,9合并最小17,







Notice:合并的时候,要考虑合并的权值是否为最小.


主要应用:

通信领域中,哈夫曼编码。左子树标识0,右子树标识为1.

总括:

哈夫曼树的学习,刚开始看上去我也很是头晕,完全傻眼了一样,但是不要被外表所迷惑,相信自己可以。不要被公式所吓倒,公式也是从算法出推到推导出来的,只要理解本质,完全可以深刻掌握的。

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics