c 语言 建立霍夫曼树

好的，我可以为您解答关于C语言建立霍夫曼树的问题。

首先，霍夫曼树是一种用于数据压缩的树形结构，它的构建是通过贪心算法实现的。在C语言中，我们可以用数组和结构体来实现霍夫曼树的构建。

以下是一个基本的C语言程序，用于实现霍夫曼树的构建：

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

struct node {
    int freq;
    char data;
    struct node *left;
    struct node *right;
};

typedef struct node node;

node* create_node(int freq, char data) {
    node *new_node = (node*)malloc(sizeof(node));
    new_node->freq = freq;
    new_node->data = data;
    new_node->left = NULL;
    new_node->right = NULL;
    return new_node;
}

void swap(node **a, node **b) {
    node *temp = *a;
    *a = *b;
    *b = temp;
}

void heapify(node **heap, int i, int n) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if(left < n && heap[left]->freq > heap[largest]->freq) {
        largest = left;
    }

    if(right < n && heap[right]->freq > heap[largest]->freq) {
        largest = right;
    }

    if(largest != i) {
        swap(&heap[i], &heap[largest]);
        heapify(heap, largest, n);
    }
}

node* build_huffman_tree(char *data, int *freq, int n) {
    node **heap = (node**)malloc(sizeof(node*) * n);

    for(int i = 0; i < n; i++) {
        heap[i] = create_node(freq[i], data[i]);
    }

    for(int i = n/2 - 1; i >= 0; i--) {
        heapify(heap, i, n);
    }

    while(n > 1) {
        node *left = heap[0];
        swap(&heap[0], &heap[n-1]);
        n--;
        heapify(heap, 0, n);
        node *right = heap[0];
        swap(&heap[0], &heap[n-1]);
        n--;
        heapify(heap, 0, n);
        node *parent = create_node(left->freq + right->freq, '-');
        parent->left = left;
        parent->right = right;
        heap[n] = parent;
        n++;
        heapify(heap, n-1, n);
    }

    node *root = heap[0];
    free(heap);

    return root;
}

void print_huffman_codes(node *root, int arr[], int top) {
    if(root->left) {
        arr[top] = 0;
        print_huffman_codes(root->left, arr, top+1);
    }

    if(root->right) {
        arr[top] = 1;
        print_huffman_codes(root->right, arr, top+1);
    }

    if(!root->left && !root->right) {
        printf("%c: ", root->data);
        for(int i = 0; i < top; i++) {
            printf("%d", arr[i]);
        }
        printf("\n");
    }
}

int main() {
    char data[] = {'a', 'b', 'c', 'd', 'e', 'f'};
    int freq[] = {5, 9, 12, 13, 16, 45};
    int n = sizeof(data)/sizeof(data[0]);

    node *root = build_huffman_tree(data, freq, n);

    int arr[100], top = 0;
    print_huffman_codes(root, arr, top);

    return 0;
}

此程序使用了一个结构体来表示霍夫曼树的节点。`create_node` 函数创建一个新节点，`swap` 函数交换两个节点，`heapify` 函数将一个节点和它的子节点进行比较，以保持堆的性质。`build_huffman_tree` 函数实现了霍夫曼树的构建过程。`print_huffman_codes` 函数用于打印每个字符的霍夫曼编码。

这是一个基本的C语言程序，用于实现霍夫曼树的构建。