6.12 赫夫曼树及其应用

6.12 赫夫曼树及其应用

用来干什么呢?其实就是最基本的压缩算法

6.12.2 赫夫曼树定义和原理

1.什么是路径,什么是路径长度

路径就是:从树中一个结点到另一个结点之间的分支

路径长度是:路径上的分支数目

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

比如上图,根节点到A的路径长度是3,树的路径长度=1+2+3+3+2+1=12

2.什么是带权路径长度

就是路径长度*权值,上面的树的带权路径长度=3 *5+3 *15+2 *70+1 *10

3.什么是赫夫曼树

带权路径长度WPL最小的二叉树称作赫夫曼树

4.怎么构造赫夫曼树呢?

  1. 在森林中选出两颗根结点的权值最小的二叉树。

  2. 合并两棵树,增加一个新结点作为新二叉树的根,权值为左右孩子的权重之和。

  3. 再从未选中的结点中选择一个最小的,和第2步的结点比较,小的放左边,大的放右边,然后重复,一直到结点没有了为止

    具体如下图所示

6.12.3 赫夫曼编码

1.什么是赫夫曼编码

其实是一种按照赫夫曼树定义的编码规则,出现多的字符的编码比较短,反之比较长,赫夫曼编码可以节省空间

2.怎么生成赫夫曼编码呢?

先把一系列数字转换成赫夫曼树,然后将权值左分支改为0右分支改为1,得到下图:

然后用树根到叶子所经过路径的0或者1来编码,比如B的编码是1001

3.怎么由赫夫曼编码解码呢?

  1. 先得到已知的赫夫曼树
  2. 按照数字对着赫夫曼树逐个查找就可以了

比如说10010100101是什么?

B A D C


  目录