c++代码实现哈夫曼树
时间: 2023-10-16 12:15:23 浏览: 41
以下是 C 代码实现哈夫曼树的示例:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int weight;
struct node *left, *right;
} Node;
typedef struct heap {
int size;
Node **array;
} Heap;
Node *create_node(int weight) {
Node *node = (Node *) malloc(sizeof(Node));
node->weight = weight;
node->left = node->right = NULL;
return node;
}
Heap *create_heap(int capacity) {
Heap *heap = (Heap *) malloc(sizeof(Heap));
heap->size = 0;
heap->array = (Node **) malloc(capacity * sizeof(Node *));
return heap;
}
void swap(Node **a, Node **b) {
Node *temp = *a;
*a = *b;
*b = temp;
}
void min_heapify(Heap *heap, int idx) {
int smallest = idx;
int left = 2 * idx + 1;
int right = 2 * idx + 2;
if (left < heap->size && heap->array[left]->weight < heap->array[smallest]->weight) {
smallest = left;
}
if (right < heap->size && heap->array[right]->weight < heap->array[smallest]->weight) {
smallest = right;
}
if (smallest != idx) {
swap(&heap->array[idx], &heap->array[smallest]);
min_heapify(heap, smallest);
}
}
Node *extract_min(Heap *heap) {
Node *min_node = heap->array[0];
heap->array[0] = heap->array[heap->size - 1];
heap->size--;
min_heapify(heap, 0);
return min_node;
}
void insert(Heap *heap, Node *node) {
heap->size++;
int i = heap->size - 1;
while (i > 0 && node->weight < heap->array[(i - 1) / 2]->weight) {
heap->array[i] = heap->array[(i - 1) / 2];
i = (i - 1) / 2;
}
heap->array[i] = node;
}
Node *build_huffman_tree(int *weights, int n) {
Heap *heap = create_heap(n);
for (int i = 0; i < n; i++) {
insert(heap, create_node(weights[i]));
}
while (heap->size > 1) {
Node *left = extract_min(heap);
Node *right = extract_min(heap);
Node *parent = create_node(left->weight + right->weight);
parent->left = left;
parent->right = right;
insert(heap, parent);
}
Node *root = extract_min(heap);
free(heap->array);
free(heap);
return root;
}
void print_huffman_codes(Node *root, int *code, int idx) {
if (root->left) {
code[idx] = 0;
print_huffman_codes(root->left, code, idx + 1);
}
if (root->right) {
code[idx] = 1;
print_huffman_codes(root->right, code, idx + 1);
}
if (!root->left && !root->right) {
printf("Weight: %d, Code: ", root->weight);
for (int i = 0; i < idx; i++) {
printf("%d", code[i]);
}
printf("\n");
}
}
int main() {
int n = 6;
int weights[] = {5, 9, 12, 13, 16, 45};
Node *root = build_huffman_tree(weights, n);
int code[n];
printf("Huffman Codes:\n");
print_huffman_codes(root, code, 0);
return 0;
}
```
该代码实现了一个最小堆和哈夫曼树的构建,以及打印哈夫曼树编码的功能。该示例中使用了一个包含 6 个权重值的数组,根据这些权重值构建了一个哈夫曼树,并打印出了每个叶子节点的编码。在实际应用中,可以根据具体需求修改该示例代码。