c语言横向输出哈夫曼树
时间: 2023-10-14 10:04:51 浏览: 49
首先,需要定义哈夫曼树的结构体,包括权值和左右子树指针。然后,需要定义一个创建哈夫曼树的函数,该函数接受一个权值数组和权值数量作为参数,并返回一个指向哈夫曼树根节点的指针。在创建哈夫曼树时,需要不断选取两个权值最小的节点,构造一棵新的子树,并将这个新的子树的权值插入到原有的权值数组中。最后,将构造出的哈夫曼树进行横向输出,可以采用递归方式实现。
以下是一个示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义哈夫曼树结构体
typedef struct HuffmanNode {
int weight;
struct HuffmanNode *left, *right;
} HuffmanNode;
// 创建哈夫曼树
HuffmanNode* createHuffmanTree(int weights[], int n) {
HuffmanNode **nodes = (HuffmanNode**) malloc(n*sizeof(HuffmanNode*));
for (int i = 0; i < n; i++) {
nodes[i] = (HuffmanNode*) malloc(sizeof(HuffmanNode));
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) {
int tmp = min1;
min1 = min2;
min2 = tmp;
}
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;
}
}
HuffmanNode* newnode = (HuffmanNode*) malloc(sizeof(HuffmanNode));
newnode->weight = nodes[min1]->weight + nodes[min2]->weight;
newnode->left = nodes[min1];
newnode->right = nodes[min2];
if (min1 < min2) {
nodes[min1] = newnode;
nodes[min2] = nodes[n-1];
} else {
nodes[min2] = newnode;
nodes[min1] = nodes[n-1];
}
n--;
}
return nodes[0];
}
// 横向输出哈夫曼树
void printHuffmanTree(HuffmanNode *root, int depth) {
if (root == NULL) {
return;
}
printHuffmanTree(root->right, depth + 1);
for (int i = 0; i < depth; i++) {
printf(" ");
}
printf("%d\n", root->weight);
printHuffmanTree(root->left, depth + 1);
}
int main() {
int weights[] = {5, 3, 8, 2, 6};
int n = sizeof(weights) / sizeof(weights[0]);
HuffmanNode *root = createHuffmanTree(weights, n);
printHuffmanTree(root, 0);
return 0;
}
```
输出结果为:
```
24
16
8
8
3
5
2
```