5.5.1.1 哈夫曼树的构造

教材导航 · 第5章

原书定位

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

每个权值作为一棵单结点树;反复选取根权值最小的两棵树合并,新根权值为二者之和,直至只剩一棵。可用小根堆将整体构造做到 O(nlog⁡n)O(n\log n)。

nn 个叶结点产生 n−1n-1 个内部结点,共 2n−12n-1 个结点,没有度为 1 的结点。WPL 等于所有新建内部结点的权值和。相同权值的选择、左右方向都可能导致形态和编码不同,但最优 WPL 一样。

图5.25 哈夫曼树构造过程

图5.25 哈夫曼树构造过程,原书P184。

对应练习

5.5 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

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