c语言哈夫曼树的构造及编码

哈夫曼树是一种用于数据压缩的重要数据结构，它可以根据一组权值构建出一棵具有最小带权路径长度的二叉树。在哈夫曼树中，权值较小的节点离根节点较近，权值较大的节点离根节点较远。因此，哈夫曼树的带权路径长度最小，可以用于数据压缩，减小数据存储空间。

在C语言中，我们可以使用数组来实现哈夫曼树的构造。首先，需要定义一个结构体来表示哈夫曼树的节点：

typedef struct huffman_node {
    int weight;                 // 权值
    int parent;                 // 父节点
    int left_child;             // 左孩子
    int right_child;            // 右孩子
} HuffmanNode;

接下来，我们可以定义一个函数来构造哈夫曼树：

void create_huffman_tree(HuffmanNode *huffman_tree, int n)
{
    int i, j, m1, m2, x1, x2;
    for (i = 0; i < 2 * n - 1; i++) {
        huffman_tree[i].weight = 0;
        huffman_tree[i].parent = -1;
        huffman_tree[i].left_child = -1;
        huffman_tree[i].right_child = -1;
    }
    for (i = 0; i < n; i++) {
        printf("请输入权值:");
        scanf("%d", &huffman_tree[i].weight);
    }
    for (i = 0; i < n - 1; i++) {
        m1 = m2 = MAX_WEIGHT;
        x1 = x2 = 0;
        for (j = 0; j < n + i; j++) {
            if (huffman_tree[j].weight < m1 && huffman_tree[j].parent == -1) {
                m2 = m1;
                x2 = x1;
                m1 = huffman_tree[j].weight;
                x1 = j;
            } else if (huffman_tree[j].weight < m2 && huffman_tree[j].parent == -1) {
                m2 = huffman_tree[j].weight;
                x2 = j;
            }
        }
        huffman_tree[x1].parent = n + i;
        huffman_tree[x2].parent = n + i;
        huffman_tree[n + i].weight = huffman_tree[x1].weight + huffman_tree[x2].weight;
        huffman_tree[n + i].left_child = x1;
        huffman_tree[n + i].right_child = x2;
    }
}

在这个函数中，我们首先初始化了哈夫曼树中的所有节点，然后依次读入每个节点的权值，接着使用贪心算法构造哈夫曼树。在每一次循环中，我们找出权值最小的两个节点，并将它们合并成一个新节点，新节点的权值为两个节点的权值之和，然后将两个节点的父节点设为新节点，直到构造出整棵哈夫曼树。

最后，我们可以定义一个函数来对数据进行编码：

void huffman_encoding(HuffmanNode *huffman_tree, int n)
{
    int i, j, c, k;
    char code[MAX_NODE];
    for (i = 0; i < n; i++) {
        code[n - 1] = '\0';
        c = i;
        k = n - 1;
        while (huffman_tree[c].parent != -1) {
            if (huffman_tree[huffman_tree[c].parent].left_child == c) {
                code[--k] = '0';
            } else {
                code[--k] = '1';
            }
            c = huffman_tree[c].parent;
        }
        printf("节点%d的编码为:", i);
        for (j = k; j < n - 1; j++) {
            printf("%c", code[j]);
        }
        printf("\n");
    }
}

在这个函数中，我们从哈夫曼树中的每个叶子节点开始，沿着从叶子节点到根节点的路径，将每个节点的编码保存在一个字符数组中，最后输出每个节点的编码。

通过以上代码，我们就可以实现C语言中的哈夫曼树的构造及编码。