给定 6 个字符 a~f它们的权值集合 W=234789试构造关于 W 的一棵哈夫曼树求其带权路径长度 WPL和各个字符的哈夫曼编码。

首先，将权值从小到大排序，得到如下表格：

| 字符 | 权值 | |------|------| | a | 2 | | b | 3 | | c | 4 | | d | 7 | | e | 8 | | f | 9 |

接着，构造哈夫曼树。首先选取权值最小的两个节点 a 和 b，合并为一个新节点 ab，其权值为 2+3=5。得到以下树：

    ab
   /  \
  a    b

接着，选取权值最小的两个节点 ab 和 c，合并为一个新节点 abc，其权值为 5+4=9。得到以下树：

    abc
   /   \
  ab    c
 / \  
a   b

继续选取权值最小的两个节点 abc 和 d，合并为一个新节点 abcd，其权值为 9+7=16。得到以下树：

     abcd
    /    \
  abc     d
 /  \
a    b

接着，选取权值最小的两个节点 abcd 和 e，合并为一个新节点 abcde，其权值为 16+8=24。得到以下树：

      abcde
     /     \
   abcd     e
  /   \   
abc   d
 / \
a   b

最后，选取权值最小的两个节点 abcde 和 f，合并为一个新节点 abcdef，其权值为 24+9=33。得到以下树：

       abcdef
       /     \
     abcde    f
     /   \  
   abcd   e
  /   \
abc   d
 / \
a   b

根据哈夫曼树的性质，从根节点到每个叶子节点的路径上，左子树为 0，右子树为 1，即可得到各个字符的哈夫曼编码：

| 字符 | 权值 | 哈夫曼编码 | |------|------|-----------| | a | 2 | 000 | | b | 3 | 001 | | c | 4 | 01 | | d | 7 | 10 | | e | 8 | 110 | | f | 9 | 111 |

最后，计算带权路径长度 WPL。根据哈夫曼树的定义，WPL 等于各个叶子节点的权值乘以其到根节点的路径长度之和。因此，有：

WPL = 2×3 + 3×3 + 4×2 + 7×2 + 8×2 + 9×2 = 72

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