已知下列字符 A、B、C、D、E、F、G 的权值分别为 3、12、7、4、2、8,11,试 填写出其对应哈夫曼树 HT 的存储结构的初态和终态
时间: 2023-07-04 18:19:21 浏览: 181
初态:
```
struct HTNode {
int weight;
int parent;
int leftChild;
int rightChild;
};
HTNode HT[2 * n - 1]; // n为叶子节点数目,即7
// 初始化叶子节点
for (int i = 0; i < n; i++) {
HT[i].weight = w[i];
HT[i].parent = -1;
HT[i].leftChild = -1;
HT[i].rightChild = -1;
}
```
终态:
```
// 构造哈夫曼树
for (int i = n; i < 2 * n - 1; i++) {
HT[i].weight = 0;
HT[i].parent = -1;
HT[i].leftChild = -1;
HT[i].rightChild = -1;
}
for (int i = n; i < 2 * n - 1; i++) {
int min1 = INT_MAX, min2 = INT_MAX;
int x1 = -1, x2 = -1;
for (int j = 0; j < i; j++) {
if (HT[j].parent == -1) {
if (HT[j].weight < min1) {
min2 = min1;
x2 = x1;
min1 = HT[j].weight;
x1 = j;
} else if (HT[j].weight < min2) {
min2 = HT[j].weight;
x2 = j;
}
}
}
HT[x1].parent = i;
HT[x2].parent = i;
HT[i].leftChild = x1;
HT[i].rightChild = x2;
HT[i].weight = HT[x1].weight + HT[x2].weight;
}
```
阅读全文