题目
假设用于通信的电文仅由8个字母组成,字母在电文中出现的频率分别为0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10。构造相应的哈夫曼树,并计算它的带权路径长度。
假设用于通信的电文仅由8个字母组成,字母在电文中出现的频率分别为0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10。构造相应的哈夫曼树,并计算它的带权路径长度。
题目解答
答案
WPL=2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61
解析
哈夫曼树的构造核心是每次合并当前权值最小的两个节点，生成新节点并重复此过程，直到只剩一个根节点。带权路径长度（WPL）是各叶子节点的权值与其到根节点路径长度乘积之和。本题需通过排序、合并、计算路径长度三步骤求解。
哈夫曼树构造过程
- 初始排序：将频率从小到大排列：
$0.02, 0.03, 0.06, 0.07, 0.10, 0.19, 0.21, 0.32$ - 合并步骤：
- 第一次合并：$0.02 + 0.03 = 0.05$
剩余节点：$0.05, 0.06, 0.07, 0.10, 0.19, 0.21, 0.32$ - 第二次合并：$0.05 + 0.06 = 0.11$
剩余节点：$0.11, 0.07, 0.10, 0.19, 0.21, 0.32$ - 第三次合并：$0.07 + 0.10 = 0.17$
剩余节点：$0.11, 0.17, 0.19, 0.21, 0.32$ - 第四次合并：$0.11 + 0.17 = 0.28$
剩余节点：$0.19, 0.21, 0.28, 0.32$ - 第五次合并：$0.19 + 0.21 = 0.40$
剩余节点：$0.28, 0.32, 0.40$ - 第六次合并：$0.28 + 0.32 = 0.60$
剩余节点：$0.40, 0.60$ - 第七次合并：$0.40 + 0.60 = 1.00$（根节点）
- 第一次合并：$0.02 + 0.03 = 0.05$
路径长度计算
- 路径长度为2：$0.19, 0.21, 0.32$（直接连接到根节点的子节点）
- 路径长度为4：$0.07, 0.06, 0.10$（经过四层合并）
- 路径长度为5：$0.02, 0.03$（经过五层合并）
WPL计算
$\begin{aligned}WPL &= 2 \times (0.19 + 0.21 + 0.32) + 4 \times (0.07 + 0.06 + 0.10) + 5 \times (0.02 + 0.03) \\&= 2 \times 0.72 + 4 \times 0.23 + 5 \times 0.05 \\&= 1.44 + 0.92 + 0.25 \\&= 2.61\end{aligned}$