用c++写一个哈夫曼树
时间: 2024-02-18 07:37:07 浏览: 21
以下是用C语言实现哈夫曼树的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义哈夫曼树结点
typedef struct huffman_node {
int weight; // 权值
struct huffman_node *left, *right; // 左子树和右子树
} huffman_node;
// 创建哈夫曼树
huffman_node* create_huffman_tree(int weights[], int n) {
// 初始化哈夫曼树结点数组
huffman_node* nodes[n];
for (int i = 0; i < n; i++) {
nodes[i] = (huffman_node*)malloc(sizeof(huffman_node));
nodes[i]->weight = weights[i];
nodes[i]->left = nodes[i]->right = NULL;
}
// 构建哈夫曼树
while (n > 1) {
// 找到最小的两个结点
int min1 = 0, min2 = 1;
if (nodes[min1]->weight > nodes[min2]->weight) {
min1 = 1;
min2 = 0;
}
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;
}
}
// 创建新的结点
huffman_node* parent = (huffman_node*)malloc(sizeof(huffman_node));
parent->weight = nodes[min1]->weight + nodes[min2]->weight;
parent->left = nodes[min1];
parent->right = nodes[min2];
// 从数组中删除旧的结点,添加新的结点
if (min1 < min2) {
nodes[min1] = parent;
nodes[min2] = nodes[n-1];
} else {
nodes[min2] = parent;
nodes[min1] = nodes[n-1];
}
n--;
}
// 返回根结点
return nodes[0];
}
// 打印哈夫曼树
void print_huffman_tree(huffman_node* root, int level) {
if (root == NULL) {
return;
}
for (int i = 0; i < level; i++) {
printf(" ");
}
printf("%d\n", root->weight);
print_huffman_tree(root->left, level+1);
print_huffman_tree(root->right, level+1);
}
int main() {
int weights[] = {5, 3, 8, 2, 4};
int n = sizeof(weights) / sizeof(int);
huffman_node* root = create_huffman_tree(weights, n);
print_huffman_tree(root, 0);
return 0;
}
```
该程序可以创建一个哈夫曼树并打印出来,权值可以根据需要进行修改。