哈夫曼树构造及编码：6个字符的权值集合W={2,3,4,7,8,9}的案例分析

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

| 字符 | 权值 | |------|------| | '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。