哈夫曼树结构及带权路径长度

哈夫曼树：

在尝试以n个结点（均为叶子节点并各自带有权值）构建一棵树时，在所构建的这棵树具有最小的带权路径长度的前提下，则称此树为最优二叉树或者赫夫曼树。在构造哈夫曼树的过程中，则需遵循一个基本原则：即权值较大的节点应尽可能靠近根节点的位置。图1中所示的情况表明，在由于结点a具有最大的权值时，则应当将其直接作为根节点的孩子节点放置。

哈夫曼树相关的几个名词

在数据结构的学习过程中，请注意以下概念：路径被定义为在一个树结构中任意两个节点之间所存在的连接两者的唯一通路。如图所示，在该树结构中从根节点指向节点a所经过的这条连接两者的通路即为一条路径。

定义为沿着一条路径所经历的所有节点数量。举例来说，在一棵树结构中，默认将最顶层的节点设定为其第1层高度。因此，在这种情况下, 若某一层上的某个特定节点位于第i层，则该特定位置与最顶层父辈之间的连接数目即为其所在层数减一（即其与父辈之间相隔的距离）。如图所示, 在这一具体的树形架构下, 节点c位于距离最顶层父辈三个单位的位置上, 即其与根节点之间的距离是3个单位长

每个顶点都会被赋予一个新数值,称为该顶点的权值.举例来说,在如图所示的情况下,顶点 a 的权值为 7.

其中，节点v的带权路径长度即为从根节点到该节点经过的所有边所构成的总长度与该节点权值之积；具体而言，在图1中计算可得：2×5=10

构建哈夫曼树过程（1）：

给定一组具有相应权重的n个节点时，请问如何生成哈夫曼编码树？

从n个权值中选择出最小的两个。
从原有的n个权值中去除这两个最小的，并将它们相加得到一个新的权值加入到剩下的n-2个权值行列中。
不断重复上述步骤直至所有的结点构造完成了一棵二叉树为止。
这就是哈夫曼树。

构建哈夫曼树过程（2）：

当有n个权值时，构造出的哈夫曼树将包含n个叶子节点。设这些权重分别为w₁, w₂, …, wₙ，则构建哈夫曼树的具体步骤如下：

(1) 将w₁至wₙ视为仅包含单节点的n棵互不相连的树组成的集合；
(2) 在该集合中选择具有最小权值之和的两棵不同的树进行合并；
(3) 移除这两棵被合并后的父节点，并将新生成的父节点重新加入集合中；
(4) 反复执行上述操作直至集合中仅剩一棵完整的二叉搜索树为止。

如：对 下图中的六个带权叶子结点来构造一棵哈夫曼树，步骤如下：

性质

每个初始节点均会成为叶子节点，并且所有的双支节点均为新产生的分支节点。
权值越高则距离根节点越近。
哈夫曼树中不存在度数仅为一的情况（其中叶子节点度数是零）。
拥有n个叶节点时其哈夫曼树总共有2n−1个总_nodes，在此结构中_ degree for branch_nodes的数量是_n−_number.