c语言哈夫曼树的译码程序

以下是C语言实现哈夫曼树的译码程序：

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

#define MAX_TREE_SIZE 100

typedef struct {
    int weight;
    int parent;
    int lchild;
    int rchild;
} HTNode, *HuffmanTree;

void CreateHuffmanTree(HuffmanTree *HT, int *w, int n) {
    if (n <= 1) return;
    int m = 2 * n - 1;
    *HT = (HuffmanTree) malloc(m * sizeof(HTNode));
    for (int i = 0; i < n; i++) {
        (*HT)[i].weight = w[i];
        (*HT)[i].parent = -1;
        (*HT)[i].lchild = -1;
        (*HT)[i].rchild = -1;
    }
    for (int i = n; i < m; i++) {
        (*HT)[i].weight = 0;
        (*HT)[i].parent = -1;
        (*HT)[i].lchild = -1;
        (*HT)[i].rchild = -1;
    }
    for (int i = n; i < m; i++) {
        int s1 = -1, s2 = -1;
        for (int j = 0; j < i; j++) {
            if ((*HT)[j].parent == -1) {
                if (s1 == -1 || (*HT)[j].weight < (*HT)[s1].weight) {
                    s2 = s1;
                    s1 = j;
                } else if (s2 == -1 || (*HT)[j].weight < (*HT)[s2].weight) {
                    s2 = j;
                }
            }
        }
        (*HT)[s1].parent = i;
        (*HT)[s2].parent = i;
        (*HT)[i].lchild = s1;
        (*HT)[i].rchild = s2;
        (*HT)[i].weight = (*HT)[s1].weight + (*HT)[s2].weight;
    }
}

void HuffmanDecode(HuffmanTree HT, int n, char *str) {
    int p = 2 * n - 2;
    for (int i = 0; str[i]; i++) {
        if (str[i] == '0') {
            p = HT[p].lchild;
        } else if (str[i] == '1') {
            p = HT[p].rchild;
        } else {
            printf("Invalid input\n");
            return;
        }
        if (HT[p].lchild == -1 && HT[p].rchild == -1) {
            putchar((char) HT[p].weight);
            p = 2 * n - 2;
        }
    }
}

int main() {
    int w[] = {5, 29, 7, 8, 14, 23, 3, 11};
    char str[] = "1101101010100100110110110110011110011111010100101011101111110101";
    HuffmanTree HT;
    CreateHuffmanTree(&HT, w, 8);
    HuffmanDecode(HT, 8, str);
    free(HT);
    return 0;
}

程序中的 `CreateHuffmanTree` 函数用于构建哈夫曼树，其中 `w` 数组存储了每个字符出现的频率，`n` 表示字符个数。函数中使用了贪心的思想，每次找到权值最小的两个节点，将其合并为一个新节点，直到只剩下一个根节点。

`HuffmanDecode` 函数用于译码，其中 `HT` 是已经构建好的哈夫曼树，`n` 是字符个数，`str` 是二进制编码，函数从根节点开始，按照编码一步一步走到叶子节点，如果遇到叶子节点，就输出对应的字符。如果遇到了无效的输入，函数会输出错误信息。

在 `main` 函数中，我们定义了一个字符串 `str`，它是通过哈夫曼编码得到的二进制编码，我们使用 `CreateHuffmanTree` 函数构建哈夫曼树，然后使用 `HuffmanDecode` 函数对二进制编码进行译码，输出原来的字符串。

以上是一个基本的哈夫曼树译码程序，可以根据实际需要进行修改和扩展。