请用C语言创建哈夫曼树
时间: 2024-04-05 22:10:30 浏览: 21
好的,以下是用C语言创建哈夫曼树的代码:
```
#include <stdio.h>
#include <stdlib.h>
struct node {
int freq;
char c;
struct node *left;
struct node *right;
};
struct node *createNode(char c, int freq) {
struct node *newNode = (struct node *)malloc(sizeof(struct node));
newNode->c = c;
newNode->freq = freq;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
struct node *buildHuffmanTree(char chars[], int freq[], int size) {
struct node *left, *right, *top;
int i;
struct node **heap = (struct node **)malloc(size * sizeof(struct node *));
for (i = 0; i < size; i++)
heap[i] = createNode(chars[i], freq[i]);
for (i = 1; i < size; i++) {
left = heap[i-1];
right = heap[i];
top = createNode('$', left->freq + right->freq);
top->left = left;
top->right = right;
heap[i] = top;
}
return heap[size-1];
}
void printCodes(struct node *root, int arr[], int top) {
if (root->left) {
arr[top] = 0;
printCodes(root->left, arr, top+1);
}
if (root->right) {
arr[top] = 1;
printCodes(root->right, arr, top+1);
}
if (!root->left && !root->right) {
printf("%c: ", root->c);
int i;
for (i = 0; i < top; i++)
printf("%d", arr[i]);
printf("\n");
}
}
void HuffmanCodes(char chars[], int freq[], int size) {
struct node *root = buildHuffmanTree(chars, freq, size);
int arr[100], top = 0;
printCodes(root, arr, top);
}
int main() {
char chars[] = {'a', 'b', 'c', 'd', 'e', 'f'};
int freq[] = {5, 9, 12, 13, 16, 45};
int size = sizeof(chars)/sizeof(chars[0]);
HuffmanCodes(chars, freq, size);
return 0;
}
```
希望能够帮到您。关于前面说的笑话,这是我听到的一则很搞笑的程序员笑话:
为什么程序员总是搞不定情人节?
因为他们总是在看源代码,却看不见注释。