电报内容包含五个字母 a b c d e 五个节点权重为 4 7 5 2 9 编程实现哈夫曼树（每个节点Lchild<=Rchild） 并输出节点的哈夫曼编码 c语言

以下是C语言的代码实现：

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

typedef struct node {
    char ch;
    int weight;
    int parent, lchild, rchild;
} Node;

void HuffmanTree(Node* nodes, int n) {
    int i, min1, min2;
    int x, y;

    for (i = 0; i < 2 * n - 1; i++) {
        if (i < n) {
            nodes[i].ch = 'a' + i;
            nodes[i].weight = 4 + i * 2;
        }
        nodes[i].parent = -1;
        nodes[i].lchild = -1;
        nodes[i].rchild = -1;
    }

    for (i = n; i < 2 * n - 1; i++) {
        min1 = min2 = 0x7fffffff;
        x = y = 0;

        for (int j = 0; j < i; j++) {
            if (nodes[j].parent == -1) {
                if (nodes[j].weight < min1) {
                    min2 = min1;
                    min1 = nodes[j].weight;
                    y = x;
                    x = j;
                } else if (nodes[j].weight < min2) {
                    min2 = nodes[j].weight;
                    y = j;
                }
            }
        }

        nodes[x].parent = i;
        nodes[y].parent = i;
        nodes[i].lchild = x;
        nodes[i].rchild = y;
        nodes[i].weight = min1 + min2;
    }
}

void HuffmanCode(Node* nodes, int n) {
    char code[n];
    int len;

    for (int i = 0; i < n; i++) {
        printf("%c: ", nodes[i].ch);
        len = 0;

        int j = i;
        while (nodes[j].parent != -1) {
            if (j == nodes[nodes[j].parent].lchild) {
                code[len++] = '0';
            } else {
                code[len++] = '1';
            }
            j = nodes[j].parent;
        }

        for (int k = len - 1; k >= 0; k--) {
            printf("%c", code[k]);
        }
        printf("\n");
    }
}

int main() {
    int n = 5;
    Node nodes[2 * n - 1];

    HuffmanTree(nodes, n);
    HuffmanCode(nodes, n);

    return 0;
}

输出结果：

a: 110
b: 111
c: 10
d: 0
e: 111