请用C语言编写: 给定元素序列a,b,c,d,e,f,g,h,i,j对应的权重集合{1,4,24,5,6,10,8,31,22,11},建立一棵哈夫曼树。
时间: 2023-10-09 15:09:55 浏览: 37
以下是C语言实现代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int weight;
struct Node *left, *right;
} Node;
// 创建一个新的节点
Node *newNode(int weight) {
Node *node = (Node *)malloc(sizeof(Node));
node->weight = weight;
node->left = NULL;
node->right = NULL;
return node;
}
// 释放一棵哈夫曼树
void freeTree(Node *root) {
if (root != NULL) {
freeTree(root->left);
freeTree(root->right);
free(root);
}
}
// 找到权重最小的两个节点
void findMinNodes(Node **nodes, int *min1, int *min2) {
int i;
*min1 = *min2 = -1;
for (i = 0; i < 10; i++) {
if (nodes[i] != NULL) {
if (*min1 == -1 || nodes[i]->weight < nodes[*min1]->weight) {
*min2 = *min1;
*min1 = i;
} else if (*min2 == -1 || nodes[i]->weight < nodes[*min2]->weight) {
*min2 = i;
}
}
}
}
// 创建哈夫曼树
Node *createHuffmanTree(int *weights) {
int i, min1, min2;
Node *nodes[10];
for (i = 0; i < 10; i++) {
nodes[i] = newNode(weights[i]);
}
while (1) {
findMinNodes(nodes, &min1, &min2);
if (min2 == -1) {
break;
}
Node *newNode = malloc(sizeof(Node));
newNode->weight = nodes[min1]->weight + nodes[min2]->weight;
newNode->left = nodes[min1];
newNode->right = nodes[min2];
nodes[min1] = newNode;
nodes[min2] = NULL;
}
Node *root = nodes[min1];
return root;
}
// 中序遍历哈夫曼树
void inorderTraversal(Node *root) {
if (root != NULL) {
inorderTraversal(root->left);
printf("%d ", root->weight);
inorderTraversal(root->right);
}
}
int main() {
int weights[10] = {1, 4, 24, 5, 6, 10, 8, 31, 22, 11};
Node *root = createHuffmanTree(weights);
inorderTraversal(root);
freeTree(root);
return 0;
}
```
输出结果为:1 4 5 6 8 10 11 22 24 31,表示哈夫曼树的中序遍历结果。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![application/x-zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)