带权为0.5，1，2，3.5，4，5，6的最优二叉树的权值是（ ）。

带权为0.5，1，2，3.5，4，5，6的最优二叉树的权值是（ ）。

要构建带权值序列 $\{0.5, 1, 2, 3.5, 4, 5, 6\}$ 的最优二叉树（哈夫曼树），就是求它的带权路径长度 $WPL$。

---

1. 哈夫曼树构建过程

哈夫曼算法：每次选最小的两个权值合并，直到得到一棵树。

初始排序（从小到大）：
$0.5, 1, 2, 3.5, 4, 5, 6$

第一步：

选 $0.5$ 和 $1$，合并：
$0.5 + 1 = 1.5$，新序列：
$1.5, 2, 3.5, 4, 5, 6$

第二步：

选 $1.5$ 和 $2$，合并：
$1.5 + 2 = 3.5$，新序列：
$3.5, 3.5, 4, 5, 6$
（注意此时有两个 $3.5$）

第三步：

选 $3.5$ 和 $3.5$（两个最小的），合并：
$3.5 + 3.5 = 7$，新序列：
$4, 5, 6, 7$

第四步：

选 $4$ 和 $5$，合并：
$4 + 5 = 9$，新序列：
$6, 7, 9$

第五步：

选 $6$ 和 $7$，合并：
$6 + 7 = 13$，新序列：
$9, 13$

第六步：

选 $9$ 和 $13$，合并：
$9 + 13 = 22$，结束。

---

2. 计算 WPL

画树（层次）在纸上做记录，或者直接由合并过程计算：

0.5 和 1 的合并后深度会继续参与合并，在最终树里深度 +1 每合并一次。我们可以记录每个原始权重在合并过程中的被加的次数，就是它在树中的“路径长度”再乘以权重。

用列表法（合并时记录新节点包含的原始叶节点，再算深度等价于算被合并的次数）：

---

记叶子：
$A=0.5, B=1, C=2, D=3.5, E=4, F=5, G=6$

$A,B$ 合并为 $X_1=1.5$，深度 1（下一步被合并一次深度就+1）。

$X_1, C$ 合并为 $X_2=3.5$，那么 A、B、C 的深度在当前这个子树是 1+1=2，在下一步合并会深度+1。

$X_2$ 和 $D$ 合并：注意此步骤是 $X_2$ (含A,B,C) 与 D(原始) 吗？ 这里要看清楚，第三步时序列是 $3.5,3.5,4,5,6$，两个 3.5 分别是 $X_2$ 和 $D$，所以第三轮合并：
$X_2$ (A,B,C) 和 $D$ 合并为 $X_3=7.0$，此时 A、B、C、D 的深度增加 1 到 3？我们需要仔细跟踪。原始深度逻辑更容易乱，换成“被合并次数”来计算：

---

更保险的办法：
每个原始权重的路径长度 = 它被选入合并的次数（即参与合并轮数）。

初始所有叶子深度 0，
每轮如果某个叶子在合并的某个节点里，它会在新的父节点里深度+1（即路径长度+1）。

我们一步步记录每个叶子到根的路径长度（合并次数）。

用合并过程记录每一步合并的两个集合的深度增加，初始各集合深度=0。

---

轮次 1：
合并 {A(0)} 与 {B(0)} ⇒ {A,B} 深度 1

现在集合：
{A,B}(深1), {C}(深0), {D}(深0), {E}(深0), {F}(深0), {G}(深0)

轮次 2：
合并 {A,B}(深1) 与 {C}(深0) ⇒ 新集合 {A,B,C} 深度= max(深1,深0)+1= 2
每个元素路径长度+1 ⇒ A,B: 原1→2, C: 0→1（不对，这样会乱）

最好直接记住：每轮合并，把两个集合所有元素深度+1（因为在新子树里多了一层）。

---

我们还是直接画合并树：

用数字表示，假设每个节点存 (权重, 深度) 对叶子：

Huffman 合并树（按层或按生成过程反向求深度）：

用构建过程的逆过程算深度（更易算 WPL）：

---

最终树是二合并，所有原始节点是叶子，其路径长度就是从根到该叶子的边数。

构造过程完全记录（列表法）：

初始： (0.5,深0),(1,深0),(2,深0),(3.5,深0),(4,深0),(5,深0),(6,深0)

合并 0.5(A) 和 1(B)：新节点 P1=1.5，深1。A、B 的深度变为 1（原0 +1）。

合并 P1(1.5, 深1) 和 2(C)：新节点 P2=3.5， 深度 2。
对 A：在原P1里，深度=1，现在加一层⇒2
对 B：同 A ⇒ 2
对 C：原深度0，在 P2 中 ⇒ 深度1？不对——等待，这里要理解：当 P1(深1) 与 C(深0) 合并时，我们创建一个新节点 P2，那么 P1 的子树的所有叶子深度+1（因为多了一边到 P2），C 的深度从 0 到 1，所以：
A: 2
B: 2
C: 1

当前叶子集合深度：
A:2,B:2,C:1,D:0,E:0,F:0,G:0
权重表：P2=3.5(含A,B,C), D=3.5, E=4, F=5, G=6。

合并 P2(深2) 与 D(深0)： 新节点 P3=7.0， 深度 3。
A: 原2 → 3
B: 原2 → 3
C: 原1 → 2
D: 原0 → 1

当前：P3(7,深3), E:4(深0), F:5(深0), G:6(深0)
合并 E 和 F ⇒ P4=9.0， 深1 （E:1, F:1）。

当前：P3(7,深3), G(6,深0), P4(9,深1)
合并 G(6,0) 和 P4(9,1) ⇒ P5=15, 深2
G: 0→1? 需要仔细：合并 G 和 P4，则 G 的深度+1 ⇒ 1，P4的每个元素深度+1 ⇒ E:1→2, F:1→2。P3暂时未变。

当前：P3(7,深3) 和 P5(15,深2) 合并 ⇒ 根=22, 深4
P3 的每个叶子深度+1 ⇒ A:3→4, B:3→4, C:2→3, D:1→2
P5 的每个叶子深度+1 ⇒ G:1→2, E:2→3, F:2→3

最终深度（路径长度）：
A:4, B:4, C:3, D:2, E:3, F:3, G:2

---

3. 计算 WPL

$$WPL = 0.5\times4 + 1\times4 + 2\times3 + 3.5\times2 + 4\times3 + 5\times3 + 6\times2$$$$= 2 + 4 + 6 + 7 + 12 + 15 + 12$$$$= (2+4)=6, +6=12, +7=19, +12=31, +15=46, +12=58$$

---

最终 WPL = 58

---

答：

$$\boxed{58}$$