哈夫曼树详解

哈夫曼树

一些名词

结点路径：从树中的一个结点到另一结点之间的分支构成的这两个结点之间的路径，路径上的分支数目称作路径长度。
**结点的权：**结点的数值有某种现实的含义（被进行了加权）。
**结点的带权路径长度：**从树的根到该结点的路径长度与该结点上的权值的乘积。
树的带权路径长度为树中所有叶子结点的带权路径长度之和(WPL,Weight Path Length)。

定义

哈夫曼树又称为最优二叉树，是在我们使用n个节点构造一棵树时，如果构造的这棵树的带权路径长度最小，则为哈夫曼树。