哈夫曼树(编码)
文章目录
一、为什么要引入哈夫曼树
二、哈夫曼树的概念
三、哈夫曼树的构造
四、 哈夫曼树的特点
五、哈夫曼编码
六、 二叉树用于编码
一、为什么要引入哈夫曼树
压缩文件的时候,为了减少不必要的空间,并且使保存和传递都更加高效。于是,介绍最基本的压缩编码方法------哈夫曼树二、哈夫曼树的概念
- 路径:从树中一个结点到另一个结点之间的分支构成的路径
- 路径长度:路径上分支的数目
- 树的路径长度:从树根到每一结点的路径长度之和
考虑带权的特点:
- 结点的带权路径长度:从根节点到该结点之间的路径长度与该结点权的乘积
- 树的带权路径长度:树中所有叶子结点的带权路径之和
哈夫曼树:带权路径长度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、字符只在叶节点上