5.5.1 哈夫曼树和哈夫曼编码
原书定位
印刷页P183起,对应PDF第195页。下文为目视整理的知识提要;完整内容见原书对照。
结点的带权路径长度等于其权值乘根到该结点的路径边数;树的 WPL 为所有叶结点带权路径长度之和:
在给定叶权值下 WPL 最小的二叉树称哈夫曼树。根的路径长度按 0 计算,不要与根所在第 1 层混淆。目标是 WPL 最小,未必树高最小。

图5.24 不同带权路径长度的二叉树,原书P184。
下级知识点
对应练习
关联知识
原书对照
展开原书对照截图


原书定位
印刷页P183起,对应PDF第195页。下文为目视整理的知识提要;完整内容见原书对照。
结点的带权路径长度等于其权值乘根到该结点的路径边数;树的 WPL 为所有叶结点带权路径长度之和:
在给定叶权值下 WPL 最小的二叉树称哈夫曼树。根的路径长度按 0 计算,不要与根所在第 1 层混淆。目标是 WPL 最小,未必树高最小。

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

