https://m.nowcoder.com/questionTerminal?uuid=0398236c212a446d959724c1c157ff40 ！！！！！！！！！ 哈夫曼树的构建基于贪心算法，其核心思路是每次从当前节点集合中挑出权值最小的两个节点进行合并，直至所有节点融合为一棵完整的树。 一、给定叶子节点权值及构建步骤 – 初始状态，给定叶子节点权值为 1、4、8、12、13。 – 首先，选取权值为 1 和 4 的两个节点，合并后得到新节点，权值为 1 + 4 = 5。此时节点集合变为 5、8、12、13。 – 接着，选出权值为 5 和 8 的节点进行合并，新节点权值为 5 + 8 = 13。此时节点集合更新为 12、13、13。 – 再选取权值为 12 和 13 的节点合并，新节点权值为 12 + 13 = 25。此时节点集合为 13、25。 – 最后，将权值为 13 和 25 的节点合并，得到根节点，权值为 13 + 25 = 38。 二、带权路径长度（WPL）计算方法及结果 带权路径长度是各叶子节点的权值与它到根节点路径长度之积的总和。 – 经分析，权值为 1 的节点路径长度为 4。 – 权值为 4 的节点路径长度同样为 4。 – 权值为 8 的节点路径长度为 3。 – 权值为 12 的节点路径长度为 2。 – 权值为 13 的节点路径长度为 1。 计算带权路径长度公式为：WPL = 1×4 + 4×4 + 8×3 + 12×2 + 13×1。 经过计算可得：WPL = 4 + 16 + 24 + 24 + 13 = 81。 综上所述，这棵哈夫曼树的带权路径长度为 81。

编辑于 2024-11-09 14:53:40