2021 数据结构第5题

2021 数据结构 ★★★☆ 哈夫曼树Huffman 构建过程带权路径长度选择题

第 5 题

若某二叉树有 5 个叶结点，其权值分别为 10、12、16、21、30，则其最小的带权路径长度（WPL）是（）。

A. 89 B. 200 C. 208 D. 289

[tag_link]

正确答案：B

根据 Huffman 构建过程来构建得到如下二叉树：

         89
      /      \
     52      37
   /   \    /  \
  22   30  16  21
 /  \
10  12

带权路径长度为：(10+12)×3+(30+16+21)×2=200