赫夫曼树用于赫夫曼编码

赫夫曼树

亦被称为哈夫曼树或最优二叉树，其核心特征在于树结构中各节点均附带相应的权值。

各结构的加权路径长度计算结果如下：
图a：WPL=5×2+7×2+2×2+13×2=54

图b：WPL=5×3+2×3+7×2+13×1=48

其中，图b符合赫夫曼树的构造标准。

赫夫曼树构建方法

步骤概述

1，将所有左右子树均为空的节点确立为根节点。
2，在森林中挑选出两棵根节点权值最小的树，将其分别作为新生成树的左、右子树，并设定新树根节点的权值为左右子树根节点权值之和。需注意的是，左子树的权值应当小于右子树的权值。
3，将上述两棵树从森林中移除，并将新生成的树重新加入森林之中。
4，反复执行第2、3步骤，直至森林中仅剩一棵树为止，此时所形成的树即为哈夫曼树。

图解：

a.初始森林：5 7 2 13，选取2 5

b.森林