假设一个文本使用的字符集为{a,b,c,d,e,f,g}，字符的曼哈顿编码依次为{0110，10，110，111，00，0111，010}。 （1）请根据哈夫曼编码画出此哈夫曼树，并在叶节点中标注相应的字符。C语言实现

以下是哈夫曼树的构建过程：

1. 将所有字符作为叶子节点，按照出现频率从小到大排列。初始状态下，每个节点的权重即为该字符出现的频率。

a: 1
b: 1
c: 1
d: 1
e: 2
f: 2
g: 2

2. 选取权重最小的两个节点作为左右子节点，构建一个新的父节点，其权重为左右子节点的权重之和。将父节点的权重加入队列中，并将父节点插入到节点列表中，保持节点列表有序。重复此步骤直到队列中只有一个元素。

a,b: 2
c: 1
d: 1
e: 2
f: 2
g: 2

a,b,c,d: 4
e: 2
f: 2
g: 2

a,b,c,d,e,f,g: 8

3. 从叶子节点开始，向上遍历哈夫曼树，标记左子节点为0，右子节点为1，直到根节点。得到每个字符的哈夫曼编码。

a: 000
b: 001
c: 0100
d: 0101
e: 11
f: 100
g: 101

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

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

#define MAX_NODES 100

struct node {
    char c;
    int weight;
    int parent;
    int left_child;
    int right_child;
};

int find_min(struct node nodes[], int n, int exclude[]) {
    int i, min = -1;
    for (i = 0; i < n; i++) {
        if (exclude[i]) {
            continue;
        }
        if (min == -1 || nodes[i].weight < nodes[min].weight) {
            min = i;
        }
    }
    return min;
}

void build_huffman_tree(struct node nodes[], int n) {
    int i, j, k, q;
    int exclude[MAX_NODES];
    memset(exclude, 0, sizeof(exclude));
    for (i = 0; i < n - 1; i++) {
        j = find_min(nodes, n, exclude);
        exclude[j] = 1;
        k = find_min(nodes, n, exclude);
        exclude[k] = 1;
        nodes[j].parent = nodes[k].parent = i + n;
        nodes[i + n].left_child = j;
        nodes[i + n].right_child = k;
        nodes[i + n].weight = nodes[j].weight + nodes[k].weight;
        exclude[i + n] = 0;
    }
}

void traverse_huffman_tree(struct node nodes[], int n, char codes[][MAX_NODES], int code_len) {
    int i, j, k;
    for (i = 0; i < n; i++) {
        k = i;
        j = 0;
        while (nodes[k].parent != -1) {
            if (k == nodes[nodes[k].parent].left_child) {
                codes[i][j++] = '0';
            } else {
                codes[i][j++] = '1';
            }
            k = nodes[k].parent;
        }
        codes[i][j] = '\0';
        strrev(codes[i]);
    }
}

void print_huffman_tree(struct node nodes[], int n) {
    int i;
    printf("char\tweight\tparent\tleft\tright\n");
    for (i = 0; i < n * 2 - 1; i++) {
        printf("%c\t%d\t%d\t%d\t%d\n", nodes[i].c, nodes[i].weight, nodes[i].parent, nodes[i].left_child, nodes[i].right_child);
    }
}

int main() {
    char charset[] = "abcdefg";
    char codes[7][MAX_NODES];
    struct node nodes[MAX_NODES];
    int i, n = strlen(charset);
    for (i = 0; i < n; i++) {
        nodes[i].c = charset[i];
        nodes[i].weight = 0;
        nodes[i].parent = -1;
        nodes[i].left_child = -1;
        nodes[i].right_child = -1;
    }
    for (i = 0; i < strlen(charset); i++) {
        switch (charset[i]) {
            case 'a':
                nodes[i].weight = 1;
                break;
            case 'b':
                nodes[i].weight = 1;
                break;
            case 'c':
                nodes[i].weight = 1;
                break;
            case 'd':
                nodes[i].weight = 1;
                break;
            case 'e':
                nodes[i].weight = 2;
                break;
            case 'f':
                nodes[i].weight = 2;
                break;
            case 'g':
                nodes[i].weight = 2;
                break;
        }
    }
    build_huffman_tree(nodes, n);
    traverse_huffman_tree(nodes, n, codes, 0);
    printf("char\tcode\n");
    for (i = 0; i < n; i++) {
        printf("%c\t%s\n", nodes[i].c, codes[i]);
    }
    print_huffman_tree(nodes, n);
    return 0;
}