哈弗曼，一个在几乎所有讲数据结构的书中都有出现过的人物，他的鼎鼎大名想必就不用我多说了。 这一次来给大家讲解一下哈弗曼树的构建与哈弗曼编码的基本原理，有什么用呢？别急，还是先学会创建 一棵哈弗曼树吧。
哈弗曼树又称最优二叉树，最优二叉树就是带权路径长度WPL最小的二叉树，那么我们就得搞清几个概 念：
1. 路径长度：从树中的一个结点到另一个结点之间的分支构成这两个结点的路径，路径上的分支数目 称为路径长度。
2. 树的路径长度：从树根到每一个结点的路径长度之和，我们所说的完全二叉树就是这种路径长度最 短的二叉树。
3. 树的带权路径长度：如果在树的每一个叶子结点上赋上一个权值，那么树的带权路径长度就等于根 结点到所有叶子结点的路径长度与叶子结点权值乘积的总和。
那么我们怎么判断一棵树是否为最优二叉树呢，先看看下面几棵树
查看本栏目更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/
他们的带权长度分别为：
WPL1：7*2+5*2+2*2+4*2=36
WPL2：7*3+5*3+2*1+4*2=46
WPL3：7*1+5*2+2*3+4*3=35
很明显，第三棵树的带权路径最短，这就是我们所说的最优二叉树（哈弗曼树），它的构建方法很简 单，依次选取权值最小的结点放在树的底部，将最小的两个连接构成一个新结点，需要注意的是构成的新 结点的权值应该等于这两个结点的权值之和，然后要把这个新结点放回我们需要构成树的结点中继续进行 排序，这样构成的哈弗曼树，所有的存储有信息的结点都在叶子结点上。
下面一张图片就为大家演示了哈弗曼树的构建过程：
时间： 2024-12-05 03:36:05