霍夫曼树是二叉树的一种特殊形式，又称为最优二叉树，其主要作用在于数据压缩和编码长度的优化。
2.1 路径和路径长度
在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。
图2.1
图2.1所示二叉树结点A到结点D的路径长度为2，结点A到达结点C的路径长度为1。
2.2 结点的权及带权路径长度
图2.2
2.3 树的带权路径长度
3.1 定义
图3.1
3.2 构造霍夫曼树
图3.2
结点 编码 A 00 B 01 C 10 D 11
图3.3
图3.4
图3.5
结点 编码 A 0 B 10 C 110 D 111
3.3 代码实现
本文主要介绍了霍夫曼树的实际意义和如何构造一棵二叉树。学习霍夫曼树主要是掌握霍夫曼树的构造思想以及构造过程，至于代码实现则是次要的，而且霍夫曼编码实现过程中运用到了贪心算法。
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.mushiming.com/mjsbk/14892.html