哈夫曼树构造及编码示例：字符 a~f 的带权路径长度 WPL 计算

首先按照权值从小到大排序，得到字符序列 a=2，b=3，c=4，d=7，e=8，f=9。

接着，将权值最小的两个字符 a 和 b 合并，得到一个新的节点 ab，其权值为 2+3=5。此时字符序列变为 ab=5，c=4，d=7，e=8，f=9。

再将权值最小的两个字符 ab 和 c 合并，得到一个新的节点 abc，其权值为 5+4=9。此时字符序列变为 abc=9，d=7，e=8，f=9。

接着，将权值最小的两个字符 d 和 e 合并，得到一个新的节点 de，其权值为 7+8=15。此时字符序列变为 abc=9，de=15，f=9。

最后，将权值最小的两个字符 abc 和 f 合并，得到一个新的节点 abcdef，其权值为 9+9=18。此时哈夫曼树构造完成。

哈夫曼树如下图所示：

根据哈夫曼树，可以得到各个字符的哈夫曼编码如下：

a：0 b：10 c：11 d：100 e：101 f：11

计算带权路径长度 WPL：

WPL = 2×1 + 3×2 + 4×2 + 7×2 + 8×2 + 9×2 = 70

因此，该哈夫曼树的带权路径长度为 70。