C语言实现哈夫曼树

C语言实现哈夫曼树攻略

什么是哈夫曼树？

哈夫曼树是一种二叉树，将一组权值作为叶子结点，构造出一个有最小带权路径长度的树，被用于数据压缩和加密等领域。

实现哈夫曼树的基本思路

具体步骤如下：

1. 根据给定的权值序列，按照从小到大的顺序，将权值存入森林F中，森林F中的每棵树都是只含一个节点的哈夫曼树；
2. 从森林F中选出两棵根节点权值最小的树作为左右子树构造一棵新的二叉树，且这个新的二叉树根节点权值为两棵树根节点权值之和；
3. 将森林F中选出的两棵树删除，在森林F中添加新的二叉树；
4. 重复步骤2和3，直到森林F中只剩下一棵树为止，这棵树即为最终构造的哈夫曼树。

哈夫曼树的C语言实现

我们可以使用一个数组来保存森林，使用一个结构体作为树节点，具体实现请参考下面的示例代码。

typedef struct {
    int weight;      // 权值
    int lchild;      // 左子树下标
    int rchild;      // 右子树下标
    int parent;      // 父节点下标
} HTNode, *HuffmanTree;

void CreateHuffmanTree(HuffmanTree *HT, int n) {
    if (n <= 1) {
        return;
    }

    int m = 2 * n - 1;      // 哈夫曼树的总节点数
    (*HT) = (HuffmanTree)malloc((m + 1) * sizeof(HTNode));
    for (int i = 1; i <= m; i++) {
        (*HT)[i].lchild = 0;
        (*HT)[i].rchild = 0;
        (*HT)[i].parent = 0;
    }

    // 输入n个叶子节点的权值，存入HT的第1至n个节点的weight中
    for (int i = 1; i <= n; i++) {
        scanf("%d", &(*HT)[i].weight);
    }

    // 创建哈夫曼树
    for (int i = n + 1; i <= m; i++) {
        int min1 = 0, min2 = 0;
        for (int j = 1; j < i; j++) {
            if ((*HT)[j].parent == 0) {
                if ((*HT)[j].weight < (*HT)[min1].weight) {
                    min2 = min1;
                    min1 = j;
                } else if ((*HT)[j].weight < (*HT)[min2].weight) {
                    min2 = j;
                }
            }
        }
        (*HT)[min1].parent = i;
        (*HT)[min2].parent = i;
        (*HT)[i].lchild = min1;
        (*HT)[i].rchild = min2;
        (*HT)[i].weight = (*HT)[min1].weight + (*HT)[min2].weight;
    }
}

示例说明

假设有以下的节点权值，为了方便演示，我们使用简单的数组来保存这些值。

int weight[] = {5, 3, 7, 9, 2, 4, 8};
int n = 7;

我们调用函数CreateHuffmanTree构造哈夫曼树。

HuffmanTree HT;
CreateHuffmanTree(&HT, n);

构造完成后，可以通过遍历哈夫曼树来输出编码结果，具体实现方式可以参考先前的题解，这里不再赘述。

在本示例中，得到的哈夫曼树如下所示：

            38
           /  \
         15    23
        /  \  /  \
      6    9  11  12
     / \  / \
    2  4 5   3

总结

本文主要介绍了如何使用C语言来实现哈夫曼树的构建。实际上，学习数据结构和算法，不仅要掌握理论知识，也需要掌握如何将理论知识转化成代码实现。通过自己动手实现，不仅可以加深对知识的理解，还能提高自己的编程能力。