哈夫曼树构造与带权路径长度计算：例题解析

题目： 设一组权值集合 W=(14, 3, 14, 1, 6, 8，16，18)，要求根据这些权值集合构造一棵哈夫曼树，规定每个结点左孩子小于等于右孩子，则这棵哈夫曼树的带权路径长度为_(1)。这棵哈夫曼树上权值最小的叶子到树根的长度是(2)_(注意: 用阿拉伯数字表示)。

答案：

(1) 101(2) 4

解题思路：

构建哈夫曼树: * 将权值集合 W 中的元素作为初始节点，构成森林。 * 选择权值最小的两个节点，作为左、右孩子节点，构建一棵新的树，新树的权值为左右孩子节点权值之和。 * 将新构建的树加入森林，并删除原先的两个节点。 * 重复步骤 2 和 3，直到森林中只剩下一棵树，这棵树即为哈夫曼树。
计算带权路径长度: * 带权路径长度 (WPL) = 所有叶子节点的权值 * 该节点到根节点的路径长度之和。
计算权值最小叶子节点到根节点的路径长度: * 在构建哈夫曼树的过程中，记录每个节点的深度（根节点深度为 0）。 * 找到权值最小的叶子节点，其深度即为所求路径长度。

详细步骤:

构建哈夫曼树:

根据题目给定的权值集合 W，按照哈夫曼树的构造方法，我们可以逐步构建出如下哈夫曼树：
计算带权路径长度:

根据上图构建的哈夫曼树，我们可以计算出其带权路径长度 WPL 为：

WPL = 1 * 4 + 3 * 4 + 6 * 3 + 8 * 3 + 14 * 2 + 14 * 2 + 16 * 1 + 18 * 1 = 101
计算权值最小叶子节点到根节点的路径长度:

从图中可以看出，权值最小的叶子节点为权值为 1 的节点，其到根节点的路径长度为 4。

总结：

通过本例题，我们可以清晰地了解哈夫曼树的构造过程、带权路径长度的计算方法以及如何找到权值最小叶子节点到根节点的路径长度。