根据输入的字符串构建霍夫曼树c语言

好的，下面是一个用 C 语言实现的构建霍夫曼树的示例：

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

#define MAX_LEN 256

// 节点结构体
typedef struct node {
    char ch; // 字符
    int freq; // 频率
    struct node *left, *right; // 左右子节点
} Node;

// 堆结构体
typedef struct heap {
    Node **nodes; // 节点数组
    int size; // 堆大小
    int capacity; // 堆容量
} Heap;

// 创建节点
Node* create_node(char ch, int freq) {
    Node *node = (Node*)malloc(sizeof(Node));
    node->ch = ch;
    node->freq = freq;
    node->left = node->right = NULL;
    return node;
}

// 交换两个节点
void swap_node(Node **n1, Node **n2) {
    Node *temp = *n1;
    *n1 = *n2;
    *n2 = temp;
}

// 向下调整节点
void heapify(Heap *heap, int idx) {
    int smallest = idx;
    int left = 2 * idx + 1;
    int right = 2 * idx + 2;

    if (left < heap->size && heap->nodes[left]->freq < heap->nodes[smallest]->freq) {
        smallest = left;
    }

    if (right < heap->size && heap->nodes[right]->freq < heap->nodes[smallest]->freq) {
        smallest = right;
    }

    if (smallest != idx) {
        swap_node(&heap->nodes[idx], &heap->nodes[smallest]);
        heapify(heap, smallest);
    }
}

// 插入节点到堆中
void insert_node(Heap *heap, Node *node) {
    if (heap->size == heap->capacity) {
        printf("Heap is full\n");
        return;
    }

    int idx = heap->size;
    heap->nodes[idx] = node;
    heap->size++;

    while (idx > 0 && heap->nodes[(idx - 1) / 2]->freq > heap->nodes[idx]->freq) {
        swap_node(&heap->nodes[(idx - 1) / 2], &heap->nodes[idx]);
        idx = (idx - 1) / 2;
    }
}

// 从堆中取出最小节点
Node* extract_min(Heap *heap) {
    if (heap->size == 0) {
        printf("Heap is empty\n");
        return NULL;
    }

    Node *min_node = heap->nodes[0];
    heap->nodes[0] = heap->nodes[heap->size - 1];
    heap->size--;

    heapify(heap, 0);

    return min_node;
}

// 构建霍夫曼树
Node* build_huffman_tree(char *s) {
    int freq[MAX_LEN] = {0};
    int len = strlen(s);

    for (int i = 0; i < len; i++) {
        freq[s[i]]++;
    }

    Heap *heap = (Heap*)malloc(sizeof(Heap));
    heap->nodes = (Node**)malloc(sizeof(Node*) * len);
    heap->size = 0;
    heap->capacity = len;

    for (int i = 0; i < MAX_LEN; i++) {
        if (freq[i] > 0) {
            Node *node = create_node(i, freq[i]);
            insert_node(heap, node);
        }
    }

    while (heap->size > 1) {
        Node *left = extract_min(heap);
        Node *right = extract_min(heap);

        Node *parent = create_node('$', left->freq + right->freq);
        parent->left = left;
        parent->right = right;

        insert_node(heap, parent);
    }

    Node *root = extract_min(heap);
    free(heap->nodes);
    free(heap);

    return root;
}

// 打印霍夫曼树
void print_huffman_tree(Node *root, int level) {
    if (root == NULL) {
        return;
    }

    print_huffman_tree(root->right, level + 1);

    for (int i = 0; i < level; i++) {
        printf("    ");
    }

    if (root->ch == '$') {
        printf("*\n");
    } else {
        printf("%c\n", root->ch);
    }

    print_huffman_tree(root->left, level + 1);
}

int main() {
    char s[] = "Hello, world!";
    Node *root = build_huffman_tree(s);
    print_huffman_tree(root, 0);
    return 0;
}

这个代码示例中，使用了一个堆来存储节点，并按照节点的频率来维护堆的顺序。通过不断地取出频率最小的两个节点，构建出霍夫曼树。最后打印出来的霍夫曼树中，`$` 表示非叶子节点，其他字符表示叶子节点。