哈夫曼树（编码）_哈夫曼编码树

文章目录

一、为什么要引入哈夫曼树

二、哈夫曼树的概念

三、哈夫曼树的构造

四、 哈夫曼树的特点

五、哈夫曼编码

六、 二叉树用于编码

一、为什么要引入哈夫曼树

压缩文件的时候，为了减少不必要的空间，并且使保存和传递都更加高效。于是，介绍最基本的压缩编码方法------哈夫曼树

二、哈夫曼树的概念

• 路径：从树中一个结点到另一个结点之间的分支构成的路径
• 路径长度：路径上分支的数目
• 树的路径长度：从树根到每一结点的路径长度之和

考虑带权的特点：

• 结点的带权路径长度：从根节点到该结点之间的路径长度与该结点权的乘积
• 树的带权路径长度：树中所有叶子结点的带权路径之和

哈夫曼树：带权路径长度WPL最小的二叉树

三、哈夫曼树的构造

• 每次把权值最小的两棵二叉树合并（比较二叉树根结点上的大小）
  哈夫曼树算法的复杂度主要由以下几部分组成：
• 1、调整最小堆：O（N）
• 2、2（N-1）+1个删除：O（NlogN）
• 3、N-1个插入：O（NlogN）
• 整体复杂度为O（NlogN）

四、哈夫曼树的特点：

• 没有度为1的结点；（用于判断是否是哈夫编码），不一定是完全二叉树。

• n0个叶子结点的哈夫曼树共有2n0-1个结点；
• 哈夫曼树的任意非叶节点的左右子树交换后仍是哈夫曼树；
  

五、哈夫曼编码

• 给定一段字符串，如何对字符进行编码，可以使得该字符串的编码存储空间最少？
• 不等长编码：出现频率高的字符用的编码短些，出现频率低的字符则可以编码长些。
• 怎么进行不等长编码？如何避免二义性？
• 前缀码：任何字符的编码都不是另一字符编码的前缀，可以无二义地编码

六、二叉树用于编码

• 1、左右分支：0、1
• 2、字符只在叶节点上