5-7 哈夫曼树及其应用

哈夫曼树的基本概念

【例】问题：将学生的百分制成绩转换为五分制成绩

<60:E 60-69:D 70-79:C 80-89:B 90-100:A

• 显然：两种判别树的效率是不一样的。
• 问题：能不能找到一种效率最高的判别树呢？—哈夫曼树（最优二叉树）

5-7 哈夫曼树及其应用（2）

哈夫曼树的基本概念

• 路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的路径
• 结点的路径长度：结点间路径上的分支数
• 树的路径长度：从树根到每一个结点的路径长度之和。记作：TL

结点数目相同的二叉树中，完全二叉树是路径长度最短的二叉树

• 权（weight）：将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权
• 结点的带权路径长度：从根结点到该结点之间的路径长度与该结点的权的乘积
• 树的带权路径长度：树中所有叶子结点的带权路径长度之和。记作：WPL（Weighted Path Length）

【例】有4个结点a，b，c，d权值分别为7，7，2，4。构造以此4个结点为叶子结点的二叉树：