已知下列字符A、B、C、D、E、F、G的权值分别为3、12、7、4、2、8,11。按照A~G的顺序输入权值,采用双亲孩子法顺序存储这个哈夫曼树,试填写出其对应哈夫曼树HT的存储结构的终态。
时间: 2023-07-04 19:05:28 浏览: 430
霍夫曼编码,输入字符,然后给出对应字符的权值和编码,用窗口界面展现出来
5星 · 资源好评率100%
首先,根据哈夫曼树的构建规则,我们需要将权值从小到大排序,得到:A(3)、E(2)、D(4)、G(11)、C(7)、F(8)、B(12)。
接下来,我们按顺序构建哈夫曼树。具体步骤如下:
1. 将权值最小的两个节点A、E合并,得到新节点AE,权值为5。
2. 将权值第三小的节点D和AE合并,得到新节点DAE,权值为9。
3. 将权值第四小的节点G和DAE合并,得到新节点GDAE,权值为20。
4. 将权值第五小的节点C和GDAE合并,得到新节点CGDAE,权值为27。
5. 将权值第六小的节点F和CGDAE合并,得到新节点FCGDAE,权值为35。
6. 将权值最大的节点B和FCGDAE合并,得到新节点BFCGDAE,权值为47。
最终得到的哈夫曼树如下所示:
```
BFCGDAE
/ \
/ \
/ \
/ \
/ \
CGDAE F
/ \ |
/ \ |
/ \ |
C GDAE A E D
/ \ | | |
/ \ | | |
G D 7 11 4
```
根据双亲孩子法顺序存储,哈夫曼树的存储结构应该为一个数组,数组下标代表节点的编号,数组元素的值代表该节点的双亲节点编号。终态如下所示:
```
0 1 2 3 4 5 6 7 8 9
HT -1 0 1 2 3 4 4 5 5 5
```
其中,节点编号从0开始,-1表示该节点没有双亲节点(即为根节点)。
阅读全文