Huffman 树构造图示及带权路径长度计算 - 以 {4, 5, 6, 7, 10, 12, 18} 为例 - 常规

首先根据结点权值构造森林，每个结点都是一棵树：

Step 1:

4   5   6   7   10   12   18

Step 2:

将森林中权值最小的两棵树合并成一棵树，并将该树作为一棵子树插入到森林中，直到森林中只剩下一棵树：

4+5  6   7   10   12   18

Step 3:

4+5  6+7  10   12   18

Step 4:

4+5  6+7  10+12   18

Step 5:

4+5+6+7  10+12   18

Step 6:

4+5+6+7+10+12  18

最终得到的 Huffman 树为：

        40
       /  \
     16    24
    /  \   / \
   6   10  12  12
  / \
 4   2

带权路径长度为：

$WPL = 4\times1 + 2\times2 + 6\times2 + 7\times2 + 10\times2 + 12\times2 + 18\times2 = 124$。