哈夫曼树带权路径长度计算 - 权值分别为 9 2 3 5 14 的示例

带权路径长度（Weighted Path Length，WPL）是指从根节点到每个叶子节点的路径长度与该叶子节点的权值的乘积的总和。\n\n给定的叶子节点权值为9、2、3、5、14，构造哈夫曼树的过程如下：\n\n1. 将叶子节点按照权值从小到大排序，得到2、3、5、9、14。\n2. 从权值最小的两个叶子节点2和3开始，合并为一个新的节点，权值为2+3=5。新的节点成为根节点，原来的2和3成为其左右子节点。\n3. 继续从权值最小的两个叶子节点5和5开始，合并为一个新的节点，权值为5+5=10。新的节点成为根节点，原来的5和5成为其左右子节点。\n4. 继续从权值最小的两个叶子节点9和10开始，合并为一个新的节点，权值为9+10=19。新的节点成为根节点，原来的9和10成为其左右子节点。\n5. 最后剩下的叶子节点14成为根节点的右子节点。\n\n构造完成的哈夫曼树如下：\n\n 41\n / \n 19 14\n / \n 9 10\n \ /\n 5 5\n \n 2\n\n根节点的左子树的带权路径长度为23 + 52 + 91 = 6 + 10 + 9 = 25。\n根节点的右子树的带权路径长度为141 = 14。\n根节点的带权路径长度为25 + 14 = 39。\n\n所以带权路径长度为39。