哈夫曼树的构造c语言代码

以下是哈夫曼树的构造 C 语言代码：

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

#define MAX_SIZE 100

typedef struct HTNode {
    int weight;
    int parent, leftChild, rightChild;
} HTNode;

typedef char* HuffmanCode;

void initHT(HTNode ht[], int n) {
    for (int i = 0; i < 2 * n - 1; ++i) {
        ht[i].weight = 0;
        ht[i].parent = -1;
        ht[i].leftChild = -1;
        ht[i].rightChild = -1;
    }
}

void selectMin(const HTNode ht[], int n, int* min1, int* min2) {
    *min1 = -1;
    *min2 = -1;
    for (int i = 0; i < n; ++i) {
        if (ht[i].parent == -1) {
            if (*min1 == -1 || ht[i].weight < ht[*min1].weight) {
                *min2 = *min1;
                *min1 = i;
            } else if (*min2 == -1 || ht[i].weight < ht[*min2].weight) {
                *min2 = i;
            }
        }
    }
}

void createHT(HTNode ht[], int w[], int n) {
    initHT(ht, n);
    for (int i = 0; i < n; ++i) {
        ht[i].weight = w[i];
    }
    for (int i = n; i < 2 * n - 1; ++i) {
        int min1, min2;
        selectMin(ht, i, &min1, &min2);
        ht[i].weight = ht[min1].weight + ht[min2].weight;
        ht[min1].parent = i;
        ht[min2].parent = i;
        ht[i].leftChild = min1;
        ht[i].rightChild = min2;
    }
}

void initHC(HuffmanCode hc[], int n) {
    for (int i = 0; i < n; ++i) {
        hc[i] = (char*)malloc(sizeof(char) * n);
        hc[i][n - 1] = '\0';
    }
}

void generateHC(const HTNode ht[], HuffmanCode hc[], int n) {
    initHC(hc, n);
    for (int i = 0; i < n; ++i) {
        int p = i;
        int k = n - 1;
        while (ht[p].parent != -1) {
            int parent = ht[p].parent;
            if (ht[parent].leftChild == p) {
                hc[i][--k] = '0';
            } else {
                hc[i][--k] = '1';
            }
            p = parent;
        }
    }
}

void printHC(const HuffmanCode hc[], const HTNode ht[], const int w[], int n) {
    printf("Huffman Code:\n");
    for (int i = 0; i < n; ++i) {
        printf("%d: %d %s\n", i, w[i], hc[i]);
    }
}

int main() {
    int n = 5;
    int w[] = { 5, 1, 6, 3, 4 };
    HTNode ht[MAX_SIZE];
    createHT(ht, w, n);
    HuffmanCode hc[MAX_SIZE];
    generateHC(ht, hc, n);
    printHC(hc, ht, w, n);
    return 0;
}

该代码首先定义了一个哈夫曼树的结构体 HTNode，包含了权重、父节点、左孩子节点和右孩子节点等信息。然后定义了一个 HuffmanCode 的类型，它是一个指向 char 类型的指针，用于存储哈夫曼编码。

initHT 函数用于初始化哈夫曼树，将所有节点的权重、父节点、左孩子节点和右孩子节点等信息均设置为初始值。selectMin 函数用于选择两个权值最小的节点。createHT 函数用于创建哈夫曼树，首先将初始权重存储在前 n 个节点中，然后循环 n 次，每次选出两个权值最小的节点，将它们合并成一个新的节点，并将新节点的权重设置为两个节点的权重之和，并将新节点的左孩子节点和右孩子节点设置为两个权值最小的节点。

initHC 函数用于初始化哈夫曼编码，将每个字符的哈夫曼编码字符串都初始化为空。generateHC 函数用于生成哈夫曼编码，对于每个字符，从它的叶子节点出发，沿着它的父节点一直向上找到根节点，记录下每个节点是其父节点的左孩子节点还是右孩子节点，直到找到根节点为止，然后将记录下来的每个节点是其父节点的左孩子节点还是右孩子节点拼接起来，就得到了该字符的哈夫曼编码。

printHC 函数用于打印哈夫曼编码。在 main 函数中，定义了一个数组 w，表示每个字符的权重，然后调用 createHT 函数创建哈夫曼树，再调用 generateHC 函数生成哈夫曼编码，最后调用 printHC 函数打印哈夫曼编码。