320 哈夫曼树1 #
- 哈夫曼树介绍
- 哈夫曼树构建
- 哈夫曼树编码
哈夫曼树介绍 #
哈夫曼树也称为最优二叉树，给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，即为哈夫曼树
哈夫曼树中有这样几个名词需要了解：
理解哈夫曼树的概念
掌握构建哈夫曼树的方法
- 路径：在一棵树中，一个结点到另一个结点之间的通路，称为路径
- 路径长度：在一条路径中，每经过一个结点，路径长度都要加1。例如在一棵树中，规定根结点所在层数为1层，那么从根结点到第i层结点的路径长度为i-1。上图中从根结点到结点5的路径长度为3
- 结点的权：给每一个结点赋予一个新的数值，被称为这个结点的权，也就是每个结点的值
- 结点的带权路径长度：指的是从根结点到该结点之间的路径长度与该结点的权的乘积。如结点5的带权路径长度为 3 * 5 = 15
哈夫曼树构建 #
在构建哈弗曼树时，要使树的带权路径长度最小，只需要遵循一个原则：权重越大的结点离树根越近。
可以按照下述步骤构建哈夫曼树：
可以按照下述步骤构建哈夫曼树：
- 首先，找出所有元素中权重最小的两个元素
- 以最小的两个元素为子结点构建二叉树，则构建的二叉树的父结点的权重为两个子结点之和
- 剩下的元素和新构建的的父结点中选出权重最小的两个节点
进行第2步操作
以此类推，直至最后合成一个二叉树就是哈夫曼树
哈夫曼编码 #
如果将访问左节点定义为0，访问右节点定义为1，那么访问某个结点所形成的二进制码就称为哈夫曼编码。例如图中的5，对应
哈夫曼编码为110，而结点8的哈夫曼编码为111。
哈夫曼编码为110，而结点8的哈夫曼编码为111。
小结 #
习题 #
- 哈夫曼树的构造结果是唯一的吗?
- 比对不同字母的哈夫曼编码，你发现了什么?
