用c语言编写一个哈夫曼树

哈夫曼树是一种用于数据压缩的树形结构，它的构建过程是先将所有待压缩的数据按照出现频率从小到大排序，然后选取出现频率最小的两个数据作为新节点，将它们的出现频率相加得到新节点的出现频率，再将新节点加入待排序的序列中，重复以上操作直到只剩下一个节点，此时构建完毕的树形结构就是哈夫曼树。

以下是用C语言实现哈夫曼树的示例代码：

#include <stdio.h>
#include <stdlib.h>

// 定义哈夫曼树节点
typedef struct huff_node {
    int weight;  // 节点权值
    int parent;  // 父节点下标
    int lchild;  // 左子节点下标
    int rchild;  // 右子节点下标
} huff_node;

// 初始化哈夫曼树
void init_huff_tree(huff_node *tree, int n) {
    int i;
    for (i = 0; i < 2 * n - 1; i++) {
        tree[i].weight = 0;
        tree[i].parent = -1;
        tree[i].lchild = -1;
        tree[i].rchild = -1;
    }
}

// 选择权值最小的两个节点
void select_min(huff_node *tree, int n, int *s1, int *s2) {
    int i;
    *s1 = *s2 = -1;
    for (i = 0; i < n; i++) {
        if (tree[i].parent == -1) {
            if (*s1 == -1 || tree[i].weight < tree[*s1].weight) {
                *s2 = *s1;
                *s1 = i;
            } else if (*s2 == -1 || tree[i].weight < tree[*s2].weight) {
                *s2 = i;
            }
        }
    }
}

// 构建哈夫曼树
void create_huff_tree(huff_node *tree, int *w, int n) {
    int i, s1, s2;
    init_huff_tree(tree, n);
    for (i = 0; i < n; i++) {
        tree[i].weight = w[i];
    }
    for (i = n; i < 2 * n - 1; i++) {
        select_min(tree, i, &s1, &s2);
        tree[s1].parent = i;
        tree[s2].parent = i;
        tree[i].lchild = s1;
        tree[i].rchild = s2;
        tree[i].weight = tree[s1].weight + tree[s2].weight;
    }
}

// 打印哈夫曼编码
void print_huff_code(huff_node *tree, int n) {
    char *code;
    int i, j, parent, child;
    code = (char *)malloc(n * sizeof(char));
    for (i = 0; i < n; i++) {
        code[n - 1] = '\0';
        parent = tree[i].parent;
        child = i;
        while (parent != -1) {
            if (tree[parent].lchild == child) {
                code[--n] = '0';
            } else {
                code[--n] = '1';
            }
            child = parent;
            parent = tree[child].parent;
        }
        printf("data[%d]: %d, code: %s\n", i, tree[i].weight, &code[n]);
    }
    free(code);
}

int main() {
    int w[] = {5, 6, 7, 8, 9};
    int n = sizeof(w) / sizeof(int);
    huff_node *tree;
    tree = (huff_node *)malloc((2 * n - 1) * sizeof(huff_node));
    create_huff_tree(tree, w, n);
    print_huff_code(tree, n);
    free(tree);
    return 0;
}

以上代码中，我们定义了一个huff_node结构体作为哈夫曼树的节点，并且实现了哈夫曼树的初始化、选择最小权值节点、构建哈夫曼树和打印哈夫曼编码等函数，最后在main函数中调用这些函数进行测试。

在实现哈夫曼树时，我们使用了一个数组来存储所有的节点，并且按照出现频率从小到大的顺序依次将节点插入到数组中，因此在构建哈夫曼树时，我们只需要从数组中选择权值最小的两个节点作为新节点进行连接即可。最终形成的哈夫曼树是一棵二叉树，每个节点都有一个权值，表示该节点代表的数据出现的频率。在打印哈夫曼编码时，我们使用了一个栈来存储每个节点的编码，并且从叶子节点开始向上遍历，直到根节点，将每个节点的编码存储在一个字符数组中，最后输出各个节点的编码即可。