邯城往事

>>> 展颜笑夙愿,一笑泯恩仇 <<<

目录
树(6)哈夫曼树
/  

树(6)哈夫曼树

哈夫曼是也叫最优二叉树,给我n个带权值的节点,权值可以表示被访问的频率等等,我要做的就是将这n个带权值的节点构成二叉树,限制条件是这n个节点都是所构成二叉树中的叶子节点,且权值越大的叶子节点,到根节点的路径越短,所以由n个节点构成的满足限制条件的二叉树一共有2n-1个节点,且被称为哈夫曼树,又称最优二叉树,

哈夫曼树的概念

概念1:什么是路径?

在一棵树中,从一个结点到另一个结点所经过的所有结点,被我们称为两个结点之间的路径。
image20220408104403vsd9nqs.png

上面的二叉树当中,从根结点A到叶子结点H的路径,就是A,B,D,H

概念2:什么是路径长度?

在一棵树中,从一个结点到另一个结点所经过的“边”的数量,被我们称为两个结点之间的路径长度。
image202204081044449p73rgy.png

仍然用刚才的二叉树举例子,从根结点A到叶子结点H,共经过了3条边,因此路径长度是3

概念3:什么是 结点的带权路径长度?

树的每一个结点,都可以拥有自己的“权重”(Weight),权重在不同的算法当中可以起到不同的作用。

结点的带权路径长度,是指树的根结点到该结点的路径长度,和该结点权重的乘积。
image20220408104504z8tpyre.png

假设结点H的权重是3,从根结点到结点H的路径长度也是3,因此结点H的带权路径长度是 3 X 3 = 9

概念4:什么是 树的带权路径长度?

在一棵树中,所有叶子结点的带权路径长度之和,被称为树的带权路径长度,也被简称为 WPL

仍然以这颗二叉树为例,树的路径长度是 3X3 + 6X3 + 1X2 + 4X2 + 8X2 = 53

哈夫曼树是由麻省理工学院的哈夫曼博士于1952年发明,这到底是一颗什么样的树呢?

刚才我们学习了树的带权路径长度(WPL),而哈夫曼树(Huffman Tree)是在叶子结点和权重确定的情况下,带权路径长度最小的二叉树,也被称为最优二叉树。

构造一棵哈夫曼树:

image202204081046075a2lytd.png

总结一下就是把权值最小的两个数放在最下面先,然后依次把剩下的最小的树慢慢加到这个二叉树上。

哈夫曼树的应用

1.哈夫曼树最典型的应用是在编码技术上的应用。利用哈夫曼树,我们可以得到 平均长度最短的编码

2.压缩

评论
取消