构造哈夫曼树 代码 C语言
时间: 2023-11-29 22:45:36 浏览: 110
C语言实现哈夫曼树的构建
5星 · 资源好评率100%
以下是用C语言实现构造哈夫曼树的代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义哈夫曼树结点的结构体
typedef struct Node {
int weight;
struct Node *left;
struct Node *right;
} Node;
// 创建一个新的哈夫曼树结点
Node* createNode(int weight) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->weight = weight;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// 构造哈夫曼树
Node* buildHuffmanTree(int weights[], int n) {
// 创建一个存放哈夫曼树结点的数组
Node** nodes = (Node**)malloc(n * sizeof(Node*));
for (int i = 0; i < n; i++) {
nodes[i] = createNode(weights[i]);
}
// 不断合并权重最小的两个结点,直到只剩下一个结点,即根结点
while (n > 1) {
// 找到权重最小的两个结点
int min1 = 0, min2 = 1;
if (nodes[min1]->weight > nodes[min2]->weight) {
int temp = min1;
min1 = min2;
min2 = temp;
}
for (int i = 2; i < n; i++) {
if (nodes[i]->weight < nodes[min1]->weight) {
min2 = min1;
min1 = i;
} else if (nodes[i]->weight < nodes[min2]->weight) {
min2 = i;
}
}
// 创建一个新的结点,权重为两个最小结点的权重之和
Node* newNode = createNode(nodes[min1]->weight + nodes[min2]->weight);
newNode->left = nodes[min1];
newNode->right = nodes[min2];
// 将新结点放入数组中
nodes[min1] = newNode;
// 删除已合并的两个结点
for (int i = min2; i < n - 1; i++) {
nodes[i] = nodes[i + 1];
}
n--;
}
// 返回根结点
return nodes[0];
}
// 打印哈夫曼树的编码
void printHuffmanCodes(Node* root, int code[], int top) {
// 如果是叶子结点,则打印编码
if (root->left == NULL && root->right == NULL) {
printf("Character: %c, Code: ", root->weight);
for (int i = 0; i < top; i++) {
printf("%d", code[i]);
}
printf("\n");
}
// 左子树添加0,右子树添加1
code[top] = 0;
printHuffmanCodes(root->left, code, top + 1);
code[top] = 1;
printHuffmanCodes(root->right, code, top + 1);
}
int main() {
int weights[] = {5, 9, 12, 13, 16, 45};
int n = sizeof(weights) / sizeof(weights[0]);
Node* root = buildHuffmanTree(weights, n);
int code[100];
int top = 0;
printHuffmanCodes(root, code, top);
return 0;
}
```
阅读全文