哈夫曼树的相关概念

基本术语

• 结点的路径长度：从根节点到该结点的路径上的连线数目。
• 结点的带权路径长度（权值在结点上）：结点权值乘以结点的路径长度。
• 树的路径长度：树中每个叶子结点的路径长度之和（结点数相同时，完全二叉树是路径最短的二叉树）。
• 树的带权路径长度（WPL）：树中所有叶子结点的带权路径长度之和。
• 最优树：在所有的含 n 个叶子结点、带有相同权值的 m 叉树中，必存在一棵带权路径长度最小的树。
• 最优二叉树（哈夫曼树）：带权路径长度最小的二叉树。

扩充二叉树

将非满二叉树中，所有度不满 2 的节点扩充为 2，便得到了扩充二叉树。扩充的节点称为外部结点，其余原来的节点称为内部结点。

如内结点数为 n，则外结点数为 S = n + 1（利用性质 n0 = n2 + 1，内结点全部度数为 2，外结点全部度数为 0）。

内外部结点路径长度

• 内结点路径长度 I：从根结点到每个内结点的路长的总和。
• 外结点路径长度 E：从根结点到每个外结点的路长的总和。

结论：如内结点路径长度为 I，则外结点路径长度 E = I + 2 * n（数学归纳法证明）。

链接到

• 上一个知识点：6.10 树和森林的遍历
• 下一个知识点：6.12 哈夫曼树的构造