创建哈夫曼树,用c++
时间: 2024-03-23 21:15:46 浏览: 15
好的,下面是一个简单的用C语言实现哈夫曼树的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_TREE_HT 100
// 哈夫曼树节点
struct Node {
char data;
int freq;
struct Node *left, *right;
};
// 哈夫曼编码表
struct Code {
char data;
char *code;
};
// 创建一个新节点
struct Node* newNode(char data, int freq) {
struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
temp->left = temp->right = NULL;
temp->data = data;
temp->freq = freq;
return temp;
}
// 交换两个节点
void swapNodes(struct Node** a, struct Node** b) {
struct Node* t = *a;
*a = *b;
*b = t;
}
// 堆排序
void heapify(struct Node** nodes, int n, int i) {
int smallest = i;
int l = 2*i + 1;
int r = 2*i + 2;
if (l < n && nodes[l]->freq < nodes[smallest]->freq)
smallest = l;
if (r < n && nodes[r]->freq < nodes[smallest]->freq)
smallest = r;
if (smallest != i) {
swapNodes(&nodes[i], &nodes[smallest]);
heapify(nodes, n, smallest);
}
}
// 构建哈夫曼树
struct Node* buildHuffmanTree(char data[], int freq[], int n) {
struct Node *left, *right, *top;
// 创建节点数组并初始化
struct Node** nodes = (struct Node**)malloc(n * sizeof(struct Node*));
for (int i = 0; i < n; i++) {
nodes[i] = newNode(data[i], freq[i]);
}
// 构建最小堆
for (int i = n/2 - 1; i >= 0; i--)
heapify(nodes, n, i);
// 构建哈夫曼树
while (n > 1) {
left = nodes[0];
right = nodes[n-1];
nodes[0] = newNode('$', left->freq + right->freq);
nodes[0]->left = left;
nodes[0]->right = right;
n--;
heapify(nodes, n, 0);
}
top = nodes[0];
free(nodes);
return top;
}
// 打印哈夫曼编码
void printCodes(struct Node* root, int arr[], int top, struct Code codes[]) {
if (root->left) {
arr[top] = 0;
printCodes(root->left, arr, top+1, codes);
}
if (root->right) {
arr[top] = 1;
printCodes(root->right, arr, top+1, codes);
}
if (!root->left && !root->right) {
codes[root->data].data = root->data;
codes[root->data].code = (char*)malloc((top+1) * sizeof(char));
for (int i = 0; i < top; i++) {
codes[root->data].code[i] = arr[i] + '0';
}
codes[root->data].code[top] = '\0';
}
}
int main() {
char data[] = {'a', 'b', 'c', 'd', 'e', 'f'};
int freq[] = {5, 9, 12, 13, 16, 45};
int n = sizeof(data) / sizeof(data[0]);
struct Node* root = buildHuffmanTree(data, freq, n);
int arr[MAX_TREE_HT], top = 0;
struct Code codes[256];
printCodes(root, arr, top, codes);
printf("哈夫曼编码表:\n");
for (int i = 0; i < 256; i++) {
if (codes[i].code != NULL) {
printf("%c: %s\n", codes[i].data, codes[i].code);
}
}
return 0;
}
```
以上代码是基于给定的字符及其出现频率,构建哈夫曼树,并输出哈夫曼编码表。你可以根据自己的需求进行修改。