一本正经的聊数据结构(6):最优二叉树 —— 哈夫曼树

一本正经的聊数据结构(6):最优二叉树 —— 哈夫曼树

前文传送门:

「一本正经的聊数据结构(1):时间复杂度」

「一本正经的聊数据结构(2):数组与向量」

「一本正经的聊数据结构(3):栈和队列」

「一本正经的聊数据结构(4):树」

「一本正经的聊数据结构(5):二叉树的存储结构与遍历」

基础知识

感谢某位在后台留言的同学,让我想起来我还有这个没写完的系列。

在最开始,先了解几个基础概念:

  • 路径:在一棵树中,一个结点到另一个结点之间的通路,称为路径。

一本正经的聊数据结构(6):最优二叉树 —— 哈夫曼树

上面这个二叉树中,根节点 A 到叶子结点 I 的路径,就是A,B,D,I。

  • 路径长度:在一条路径中,每经过一个结点,路径长度都要加 1 。例如在一棵树中,规定根结点所在层数为1层,那么从根结点到第 i 层结点的路径长度为 i - 1 。

一本正经的聊数据结构(6):最优二叉树 —— 哈夫曼树

在这个二叉树中,根节点 A 到叶子结点 H 的路径长度就是 3 。

  • 结点的权:给每一个结点赋予一个数值,被称为这个结点的权。
  • 结点的带权路径长度:指的是从根结点到该结点之间的路径长度与该结点的权的乘积。

一本正经的聊数据结构(6):最优二叉树 —— 哈夫曼树

我们假设节点 H 的权是 5 ,从根结点到结点 H 的路径长度是 3 ,那么结点 H 的带权路径长度是 3 X 5 = 15。

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

一本正经的聊数据结构(6):最优二叉树 —— 哈夫曼树

还是这颗树,它的带权路径长度是 1 X 2 + 2 X 1 + 2 X 3 + 2 X 4 + 3 X 5 + 3 X 6 = 51 。

哈夫曼树

哈弗曼树就是在用 n 个结点(都做叶子结点且都有各自的权值)试图构建一棵树时,如果构建的这棵树的带权路径长度最小,称这棵树为「最优二叉树」,有时也叫「哈夫曼树」或者「赫夫曼树」。

在构建哈弗曼树时,要使树的带权路径长度最小,只需要遵循一个原则,那就是:权重越大的结点离树根越近。

需要注意的是,同样叶子结点所构成的哈夫曼树可能不止一颗,在同一层,左右叶子节点交换位置,树的带权路径长度是一样的,就比如下面这两个哈夫曼树:

一本正经的聊数据结构(6):最优二叉树 —— 哈夫曼树

哈弗曼树的构建过程

那么如何构建一个哈夫曼树呢?我们这里举个例子,比如我们有这么几个叶子节点:3,4,7,9,13,15,17:

一本正经的聊数据结构(6):最优二叉树 —— 哈夫曼树

第一步:选出两个最小的权值,对应的两个结点组成一个新的二叉树,且新二叉树的根结点的权值为左右孩子权值的和:

一本正经的聊数据结构(6):最优二叉树 —— 哈夫曼树

第二步:从队列中移除上一步选择的两个最小结点,把新的父节点加入队列,也就是从队列中删除 3 和 4 ,插入 7 ,并且仍然保持队列的升序:

一本正经的聊数据结构(6):最优二叉树 —— 哈夫曼树

第三步:选择当前权值最小的两个结点,生成新的父结点。

这一步其实是在重复上一步操作,当前队列中最小的节点是 7 和 7 ,生成新的父结点权值是 7 + 7 = 14 :

一本正经的聊数据结构(6):最优二叉树 —— 哈夫曼树

第四步:从队列中移除上一步选择的两个最小结点,把新的父节点加入队列。

这一步依然是在重复,从队列中删除 7 和 7 ,加入 14 ,并且仍然保持队列的升序:

一本正经的聊数据结构(6):最优二叉树 —— 哈夫曼树

第五步:选择当前权值最小的两个结点,生成新的父结点。

这一步还是重复操作。当前队列中权值最小的结点是 9 和 14 ,生成新的父结点权值是 9 + 14 = 23 :

一本正经的聊数据结构(6):最优二叉树 —— 哈夫曼树

第六步:从队列中移除上一步选择的两个最小结点,把新的父节点加入队列。

这一步依然是在重复,从队列中删除 9 和 14 ,加入 23 ,并且仍然保持队列的升序:

一本正经的聊数据结构(6):最优二叉树 —— 哈夫曼树

第七步:选择当前权值最小的两个结点,生成新的父结点。

这一步从队列中选择权值最小的结点是 13 和 15 ,生成新的父结点权值是 13 + 15 = 28 :

一本正经的聊数据结构(6):最优二叉树 —— 哈夫曼树

第八步:从队列中移除上一步选择的两个最小结点,把新的父节点加入队列。

从队列中删除 13 和 15 ,加入 28 ,并且仍然保持队列的升序:

一本正经的聊数据结构(6):最优二叉树 —— 哈夫曼树

第九步:选择当前权值最小的两个结点,生成新的父结点。

这一步从队列中选择权值最小的结点是 17 和 23 ,生成新的父结点权值是 17 + 23 = 40 :

一本正经的聊数据结构(6):最优二叉树 —— 哈夫曼树

第十步:从队列中移除上一步选择的两个最小结点,把新的父节点加入队列。

从队列中删除 17 和 23 ,加入 40 ,并且仍然保持队列的升序:

一本正经的聊数据结构(6):最优二叉树 —— 哈夫曼树

第十一步:选择当前权值最小的两个结点,生成新的父结点,移除队列中的最后两个节点(懒得画了,最后两步并一步)。

这一步从队列中选择权值最小的结点是 28 和 40 ,生成新的父结点权值是 28 + 40 = 68 :

一本正经的聊数据结构(6):最优二叉树 —— 哈夫曼树

此时,我们得到的这棵树就是哈弗曼树。

哈夫曼树就介绍到这里,下一节,将会介绍哈夫曼树的用途:哈夫曼编码。

参考

http://c.biancheng.net/view/3398.html

https://baijiahao.baidu.com/s?id=1663514710675419737&wfr=spider&for=pc

相关推荐