题目
由权值分别为 3，8，6，2 的叶子生成一颗哈夫曼树[1]，它的带权路径长度为（ ）。A. 11B. 35C. 19D. 53
由权值分别为 3，8，6，2 的叶子生成一颗哈夫曼树[1]，它的带权路径长度为（ ）。
- A. 11
- B. 35
- C. 19
- D. 53
题目解答
答案
B
解析
步骤 1：构建哈夫曼树
哈夫曼树是一种带权路径长度最短的二叉树。构建哈夫曼树的步骤如下：
1. 将所有叶子节点按照权值从小到大排序。
2. 选择两个权值最小的节点，创建一个新节点，其权值为这两个节点权值之和。
3. 将新节点加入到排序后的节点列表中，重复步骤2，直到所有节点合并成一个树。
步骤 2：计算带权路径长度
带权路径长度是所有叶子节点的权值与其到根节点的路径长度的乘积之和。
步骤 3：计算具体数值
1. 将权值从小到大排序：2，3，6，8。
2. 选择权值最小的两个节点2和3，创建一个新节点，权值为5。
3. 将新节点加入到排序后的节点列表中：5，6，8。
4. 选择权值最小的两个节点5和6，创建一个新节点，权值为11。
5. 将新节点加入到排序后的节点列表中：8，11。
6. 选择权值最小的两个节点8和11，创建一个新节点，权值为19。
7. 计算带权路径长度：2×3 + 3×3 + 6×2 + 8×2 = 6 + 9 + 12 + 16 = 43。
哈夫曼树是一种带权路径长度最短的二叉树。构建哈夫曼树的步骤如下：
1. 将所有叶子节点按照权值从小到大排序。
2. 选择两个权值最小的节点，创建一个新节点，其权值为这两个节点权值之和。
3. 将新节点加入到排序后的节点列表中，重复步骤2，直到所有节点合并成一个树。
步骤 2：计算带权路径长度
带权路径长度是所有叶子节点的权值与其到根节点的路径长度的乘积之和。
步骤 3：计算具体数值
1. 将权值从小到大排序：2，3，6，8。
2. 选择权值最小的两个节点2和3，创建一个新节点，权值为5。
3. 将新节点加入到排序后的节点列表中：5，6，8。
4. 选择权值最小的两个节点5和6，创建一个新节点，权值为11。
5. 将新节点加入到排序后的节点列表中：8，11。
6. 选择权值最小的两个节点8和11，创建一个新节点，权值为19。
7. 计算带权路径长度：2×3 + 3×3 + 6×2 + 8×2 = 6 + 9 + 12 + 16 = 43。