5.5.1 哈夫曼树和哈夫曼编码

教材导航 · 第5章

原书定位

印刷页P183起,对应PDF第195页。下文为目视整理的知识提要;完整内容见原书对照。

结点的带权路径长度等于其权值乘根到该结点的路径边数;树的 WPL 为所有叶结点带权路径长度之和:

WPL=∑i=1nwiliWPL=\sum_{i=1}^{n}w_i l_i

在给定叶权值下 WPL 最小的二叉树称哈夫曼树。根的路径长度按 0 计算,不要与根所在第 1 层混淆。目标是 WPL 最小,未必树高最小。

图5.24 不同带权路径长度的二叉树

图5.24 不同带权路径长度的二叉树,原书P184。

下级知识点

对应练习

5.5 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P183,PDF第195页

原书对照,原书P184,PDF第196页