已知下列字符A、B、C、D、E、F、G的权值分别为3、12、7、4、2、8,11,试填写出其对应哈夫曼树HT的存储结构的初态和终态。
时间: 2023-09-17 18:07:45 浏览: 34
初态:
```
struct HTNode {
int weight;
int parent;
int lchild;
int rchild;
};
HTNode HT[MAX_SIZE];
// 初始化HT
for (int i = 0; i < MAX_SIZE; i++) {
HT[i].weight = 0;
HT[i].parent = 0;
HT[i].lchild = 0;
HT[i].rchild = 0;
}
```
终态:
```
45
/ \
/ \
22 23
/ \ / \
C(7) F(8) G(11)
/ \
A(3) B(12)
D(4)
E(2)
// HT[1] ~ HT[7] 存储的是 A、B、C、D、E、F、G 结点对应的哈夫曼树结构
HT[1].weight = 7;
HT[2].weight = 12;
HT[3].weight = 3;
HT[4].weight = 4;
HT[5].weight = 2;
HT[6].weight = 8;
HT[7].weight = 11;
HT[1].parent = 8;
HT[2].parent = 8;
HT[3].parent = 6;
HT[4].parent = 7;
HT[5].parent = 7;
HT[6].parent = 8;
HT[7].parent = 8;
HT[3].lchild = 1;
HT[3].rchild = 2;
HT[6].lchild = 3;
HT[6].rchild = 5;
HT[7].lchild = 4;
HT[7].rchild = 6;
// 其它结点的 parent、lchild、rchild 均为0,表示没有父结点、左结点、右结点
```