数据结构题，求助，

Question

假设通信电文使用的字符集为{a，b，c，d，e，f，g，h}，各字符在电文中出现的频度分别为：7，19，2，6，32，3，21，10，试为这8
个字符设计哈夫曼树。要求：
(1) 构造哈夫曼树；
(2) 求哈夫曼树中的结点总数。

Answer 1

为了设计哈夫曼树，我们首先需要按照字符出现的频度进行排序。给定的字符及其频度如下：

字符：a, b, c, d, e, f, g, h
频度：7, 19, 2, 6, 32, 3, 21, 10

将这些频度从小到大排序：

2, 3, 6, 7, 10, 19, 21, 32

接下来，我们根据排序后的频度构建哈夫曼树：

选择最小的两个频度2和3，构造一个内部结点，其频度为两者之和5，作为这两个字符的父结点。

接着，从剩下的频度中选择最小的两个，即6和7，构造另一个内部结点，频度为13。

将步骤1和步骤2中得到的两个内部结点（频度分别为5和13）作为新的节点，与下一个最小的频度10进行组合，构造一个频度为18的内部结点。

重复上述过程，依次将剩下的频度与已构造的内部结点进行组合，直到所有字符都被包含在树中。

最终得到的哈夫曼树是一个完全二叉树，其叶子结点为给定的字符，内部结点的频度为子结点频度之和。由于哈夫曼树是完全二叉树，其结点总数等于叶子结点数目（即字符数）的两倍减一。因此，对于8个字符，结点总数为：

结点总数 = 2 * 叶子结点数目 - 1 = 2 * 8 - 1 = 16 - 1 = 15

所以，哈夫曼树中的结点总数为15个。由于哈夫曼树的构造过程涉及具体的树形结构，这里无法用文字完整描述整个树的结构，但通过上述方法，您可以手动绘制出完整的哈夫曼树，并验证结点总数。

Answer 2

哈夫曼树如图，有15个节点

本回答被提问者采纳

Answer 3

构造哈夫曼树的步骤如下：
1. 将所有字符按照出现频度从小到大排序。
2. 选取频度最小的两个字符，构造一个新的二叉树，根节点的频度为这两个字符的频度之和。
3. 将新构造的二叉树插入到频度列表中，删除原来的两个字符。
4. 重复步骤2和3，直到列表中只剩下一个节点，即哈夫曼树的根节点。
按照上述步骤，我们来构造哈夫曼树：
第一步：将字符按频度排序：{c(2), f(3), h(6), a(7), d(10), g(19), b(21), e(32)}
第二步：选取频度最小的两个字符c和f，构造二叉树，根节点频度为2+3=5。
第三步：更新字符列表：{h(6), a(7), d(10), g(19), b(21), e(32), cf(5)}
第四步：选取频度最小的两个字符h和cf，构造二叉树，根节点频度为6+5=11。
第五步：更新字符列表：{a(7), d(10), g(19), b(21), e(32), hcf(11)}
继续重复以上步骤，直到只剩下一个节点为止。
最终得到的哈夫曼树如下所示：
```
111
/ \
e(32) 110
/ \
h(6) 011
/ \
g(19) 010
/ \
b(21) 001
/ \
d(10) a(7)
```
在这个哈夫曼树中，共有8个叶子节点，代表了8个字符，加上内部节点，总共有15个节点。