哈夫曼树的构造c语言代码
时间: 2023-07-09 07:24:01 浏览: 54
下面是哈夫曼树的构造C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
typedef struct node {
int weight;
int parent, left, right;
} Node;
Node huffTree[MAX * 2];
void huff(int n) {
int i, j, x1, x2, y1, y2;
for (i = 0; i < 2 * n - 1; i++) {
huffTree[i].parent = huffTree[i].left = huffTree[i].right = -1;
}
for (i = 0; i < n; i++) {
printf("Enter weight of node %d: ", i);
scanf("%d", &huffTree[i].weight);
}
for (i = 0; i < n - 1; i++) {
x1 = x2 = -1;
y1 = y2 = MAX;
for (j = 0; j < n + i; j++) {
if (huffTree[j].parent == -1) {
if (huffTree[j].weight < y1) {
y2 = y1;
y1 = huffTree[j].weight;
x2 = x1;
x1 = j;
} else if (huffTree[j].weight < y2) {
y2 = huffTree[j].weight;
x2 = j;
}
}
}
huffTree[x1].parent = n + i;
huffTree[x2].parent = n + i;
huffTree[n + i].left = x1;
huffTree[n + i].right = x2;
huffTree[n + i].weight = huffTree[x1].weight + huffTree[x2].weight;
}
}
int main() {
int n;
printf("Enter the number of nodes: ");
scanf("%d", &n);
huff(n);
return 0;
}
```
这个代码实现了哈夫曼树的构造,首先输入节点的权值,然后根据哈夫曼树的构造规则构造哈夫曼树。其中,huffTree数组存储了哈夫曼树的每个节点的信息,包括权值、父节点、左子节点和右子节点。在构造哈夫曼树的过程中,我们需要找到权值最小的两个节点,将它们作为新节点的左右子节点,然后将新节点加入到哈夫曼树中。最终得到的哈夫曼树的根节点就是huffTree数组中的最后一个元素。