题目
已知下列字符A、B、C、D、E、F、G的权值分别为3、12、7、4、2、8，11，试填写出其对应哈夫曼树[1]HT存储结构的初态和终态。
已知下列字符A、B、C、D、E、F、G的权值分别为3、12、7、4、2、8，11，试填写出其对应哈夫曼树[1]HT存储结构的初态和终态。
题目解答
答案
首先将字符A、B、C、D、E、F、G按照权值从小到大排序，得到对应权值为2、3、4、7、8、11、12。然后按照哈夫曼树的构建方法，先选取权值最小的两个节点E和A，构建一个新的子树，其根节点的权值为两个节点权值之和，即10。用该子树替换原来的两个节点，形成新的待选列表。再次从中选取权值最小的两个节点，分别为C和D，构建新的子树，并将其替换原来的两个节点，得到新的待选列表。重复上述操作，直到所有节点都被纳入到哈夫曼树中。最终得到如下初态和终态：
初态：
待选列表：E 2、A 3、D 4、C 7、F 11、G 12
已选列表：空
终态：
待选列表：空
已选列表：根节点10（E的父节点）→左孩子3（A）→左孩子2（E）、右孩子7（C的父节点）→左孩子4（D）→左孩子12（G）、右孩子11（F）、右孩子8（B的父节点）→左孩子4（C）、右孩子4（D）
解析
步骤 1：排序字符的权值
将字符A、B、C、D、E、F、G的权值从小到大排序，得到：E 2、A 3、D 4、C 7、F 11、G 12、B 12。
步骤 2：构建哈夫曼树
1. 选取权值最小的两个节点E和A，构建新的子树，其根节点的权值为5（2+3）。
2. 用该子树替换原来的两个节点，形成新的待选列表：D 4、C 7、F 11、G 12、B 12、根节点5（E的父节点）。
3. 选取权值最小的两个节点D和C，构建新的子树，其根节点的权值为11（4+7）。
4. 用该子树替换原来的两个节点，形成新的待选列表：F 11、G 12、B 12、根节点5（E的父节点）、根节点11（D的父节点）。
5. 选取权值最小的两个节点F和根节点5，构建新的子树，其根节点的权值为16（11+5）。
6. 用该子树替换原来的两个节点，形成新的待选列表：G 12、B 12、根节点11（D的父节点）、根节点16（F的父节点）。
7. 选取权值最小的两个节点G和B，构建新的子树，其根节点的权值为24（12+12）。
8. 用该子树替换原来的两个节点，形成新的待选列表：根节点11（D的父节点）、根节点16（F的父节点）、根节点24（G的父节点）。
9. 选取权值最小的两个节点根节点11和根节点16，构建新的子树，其根节点的权值为27（11+16）。
10. 用该子树替换原来的两个节点，形成新的待选列表：根节点24（G的父节点）、根节点27（D的父节点）。
11. 选取权值最小的两个节点根节点24和根节点27，构建新的子树，其根节点的权值为51（24+27）。
12. 用该子树替换原来的两个节点，形成新的待选列表：根节点51（G的父节点）。
步骤 3：确定初态和终态
初态：待选列表：E 2、A 3、D 4、C 7、F 11、G 12、B 12；已选列表：空。
终态：待选列表：空；已选列表：根节点51（G的父节点）→左孩子27（D的父节点）→左孩子16（F的父节点）→左孩子11（E的父节点）→左孩子3（A）、右孩子2（E）、右孩子11（D的父节点）→左孩子4（D）、右孩子7（C）、右孩子24（G的父节点）→左孩子12（G）、右孩子12（B）。
将字符A、B、C、D、E、F、G的权值从小到大排序，得到：E 2、A 3、D 4、C 7、F 11、G 12、B 12。
步骤 2：构建哈夫曼树
1. 选取权值最小的两个节点E和A，构建新的子树，其根节点的权值为5（2+3）。
2. 用该子树替换原来的两个节点，形成新的待选列表：D 4、C 7、F 11、G 12、B 12、根节点5（E的父节点）。
3. 选取权值最小的两个节点D和C，构建新的子树，其根节点的权值为11（4+7）。
4. 用该子树替换原来的两个节点，形成新的待选列表：F 11、G 12、B 12、根节点5（E的父节点）、根节点11（D的父节点）。
5. 选取权值最小的两个节点F和根节点5，构建新的子树，其根节点的权值为16（11+5）。
6. 用该子树替换原来的两个节点，形成新的待选列表：G 12、B 12、根节点11（D的父节点）、根节点16（F的父节点）。
7. 选取权值最小的两个节点G和B，构建新的子树，其根节点的权值为24（12+12）。
8. 用该子树替换原来的两个节点，形成新的待选列表：根节点11（D的父节点）、根节点16（F的父节点）、根节点24（G的父节点）。
9. 选取权值最小的两个节点根节点11和根节点16，构建新的子树，其根节点的权值为27（11+16）。
10. 用该子树替换原来的两个节点，形成新的待选列表：根节点24（G的父节点）、根节点27（D的父节点）。
11. 选取权值最小的两个节点根节点24和根节点27，构建新的子树，其根节点的权值为51（24+27）。
12. 用该子树替换原来的两个节点，形成新的待选列表：根节点51（G的父节点）。
步骤 3：确定初态和终态
初态：待选列表：E 2、A 3、D 4、C 7、F 11、G 12、B 12；已选列表：空。
终态：待选列表：空；已选列表：根节点51（G的父节点）→左孩子27（D的父节点）→左孩子16（F的父节点）→左孩子11（E的父节点）→左孩子3（A）、右孩子2（E）、右孩子11（D的父节点）→左孩子4（D）、右孩子7（C）、右孩子24（G的父节点）→左孩子12（G）、右孩子12（B）。