哈夫曼树是完全二叉树吗?(根据权值构造哈夫曼树)

最近来看一下JPEG代码的原理，使用的是瘦香菇(huffman )代码。 在调查的资料上加上个人的理解进行了总结。 首先，让我们来看看这个问题。 /将学生的百分满分成绩转换为五分满分成绩。 90分： A、80~89分： B、70~79分： C、60~69分： D、<； 60分： E。

成绩判断逻辑

如上图所示，是常用的判断逻辑，根据输入的分数找到相应的分支。 在此基础上，考虑到程序的执行效率，假设对应的分数段及其分数段出现的概率相同。 那么，如果使用如上判断逻辑方案1，例如，如果学生的总成绩数据有10000件，则5%的数据需要比较一次，15%的数据需要比较两次，40%的数据需要比较三次，40%的数据需要比较四次

不同的逻辑执行时间

使用方案2的话，这样形状的二叉树需要10000(35 ) 315 ) 240 ) 210 ) 230 ) )次的比较次数。

显然，两种判别树的效率不同。

那么，有没有办法找到最有效率的树呢？ 这时，拉出了瘦长的香菇(huffman )树；

首先，让我们了解相关的概念：

根：树中存在节点序列k1、k2、kj，ki是ki 1的chdgz时，将其节点序列称为从k1到kj的根。

路径长度：路径上的节点数减去1的数。

节点权重：在许多应用中，经常给树中的节点赋予有意义的数量，称为该节点的权重。

节点的加权路径长：从该节点到树根的路径长和该节点的加权的积。

树的赋权路径长度：树中所有叶节点的赋权路径长度之和。 通常表述如下。

n表示叶节点的数量，Wi和Li分别表示叶节点Ki的权重和从根节点到叶节点Ki的路径长度。

瘦香菇树(huffman树)，在具有权重为w1、w2、…、wn的n个叶结点的所有二叉树中，将加权路径长度WPL最小的二叉树称为瘦香菇树或最佳二叉树。 例如有4个节点a、b、c、d，权重分别为7、5、2、4。 尝试构建以这4个节点为叶节点的二叉树。

瘦香菇树介绍

那么，如果有效地制作瘦香菇树呢？ 使用瘦香菇算法；

1 .基于给定的n个权重{w1，w2，…，wn}，构成二叉树的集合F={T1，T2，…，Tn}。 这里，各二叉树Ti中只有一个具有wi权重的根节点，其左右的部分树为空；

2.f中，将2个根节点的权重最小的树作为左右的部分树来构筑1个新的二叉树，并且放置新二叉树的根节点的权重为左右部分根节点的权重之和

3 .用f删除这两棵树，同时向f添加新的二叉树；

重复2、3次，直到f中只含有一棵树，得到瘦长的香菇树。

算法的说明有点抽象，让我们用例子来理解吧。 例如：有4个节点a、b、c、d，权重分别为7、5、2、4，做成瘦香菇树。 在此，为了简洁地表现，用图像表示直接表现结构过程：

给定的节点和权限

步骤1

步骤2和步骤3

关于瘦香菇树的注意事项： 1、被二叉树覆盖的树不一定是瘦香菇树

2、瘦香菇树中权大的甜樱桃根越近(很好理解。 WPL最小的二叉树) ) )。

3、拥有同样权利的结点的瘦长香菇树不是唯一的

4、瘦香菇树的结点度数为0或2，没有度1的结点。

含有5、n个叶节点的瘦香菇树共有2n1个节点。

包含6、n棵树的森林经过n1次合并后形成瘦香菇树，共有n1个新节点诞生

瘦香菇树介绍到这里，下一篇继续介绍瘦香菇树的应用——瘦香菇代码。