数据结构--哈夫曼树

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

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

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

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

看实例：

D的结点路径长度：从d到A的路径，共走了两条边，所以为2。树中的叶子结点有D,E和F。结点路径都为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.

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

9楼zhangyingjie0912小时前

很多东西没有自己想象中那么难，最难克服的还是自己。

Re: han_yankun200911小时前

回复zhangyingjie09n谢谢鼓励

8楼zhang_xinxiu15小时前

很重要的概念，一种思想，很好的表示了算法

7楼lishuangzhe7047昨天 21:18

哈夫曼树编码是不唯一的。

Re: han_yankun2009昨天 21:20

回复lishuangzhe7047n是呀。不唯一，但是最合适的也就一种呢

6楼lishehe昨天 21:09

数据结构--哈夫曼树 ，静下心来学习

Re: han_yankun2009昨天 21:09

回复lishehen谢谢提醒呢

5楼liutengteng130昨天 20:47

哈弗曼树好详细啊。

Re: han_yankun2009昨天 21:08

回复liutengteng130n真的很详细么，要是真的详细，那就真有问题啦

4楼tang_huan_11昨天 20:46

哈夫曼树---找最小值

Re: han_yankun2009昨天 20:47

回复tang_huan_11n恩。是呀。最优

3楼zhuanzhe117昨天 19:30

借鉴了

2楼xiaoxian8023昨天 16:46

lz的例子很清晰

1楼hanxuemin12345前天 21:02

一种带权路径长度最短的二叉树

Re: han_yankun2009昨天 09:02

回复hanxuemin12345n恩。很精确