5.5.1.1 哈夫曼树的构造
原书定位
印刷页P184起,对应PDF第196页。下文为目视整理的知识提要;完整内容见原书对照。
每个权值作为一棵单结点树;反复选取根权值最小的两棵树合并,新根权值为二者之和,直至只剩一棵。可用小根堆将整体构造做到 。
个叶结点产生 个内部结点,共 个结点,没有度为 1 的结点。WPL 等于所有新建内部结点的权值和。相同权值的选择、左右方向都可能导致形态和编码不同,但最优 WPL 一样。

图5.25 哈夫曼树构造过程,原书P184。
对应练习
关联知识
原书对照
展开原书对照截图
