2024年3月30日发(作者：)

c语言实现构造哈夫曼树代码

一、哈夫曼树简介

哈夫曼树是一种特殊的二叉树，其每个叶子节点都对应一个权值，而

非叶子节点则没有权值。哈夫曼树的构造过程中，将权值较小的节点

放在左子树，权值较大的节点放在右子树，这使得哈夫曼树的带权路

径最短。哈夫曼编码就是利用这种特性实现对数据进行压缩。

二、C语言实现构造哈夫曼树

1. 定义结构体

首先需要定义一个结构体来表示哈夫曼树中的节点。结构体中包含了

该节点的权值以及指向左右子节点的指针。

```

typedef struct TreeNode {

int weight;

struct TreeNode *left;

struct TreeNode *right;

} TreeNode;

```

2. 构造哈夫曼树

接下来需要实现构造哈夫曼树的函数。该函数接收一个数组作为输入，

数组中存储了每个叶子节点的权值。首先需要将数组中所有元素转化

为TreeNode类型，并将它们存储在一个链表中。

```

TreeNode *createTreeNodes(int weights[], int size) {

TreeNode *nodes[size];

for (int i = 0; i < size; i++) {

nodes[i] = (TreeNode *)malloc(sizeof(TreeNode));

nodes[i]->weight = weights[i];

nodes[i]->left = NULL;

nodes[i]->right = NULL;

}

return nodes;

}

```

接下来，需要实现一个函数来找到权值最小的两个节点。该函数接收

一个链表作为输入，并返回该链表中权值最小的两个节点。