c语言求哈夫曼树的带权路径长度

要求哈夫曼树的带权路径长度，需要先构建哈夫曼树，然后对树中每个叶子节点求出它与根节点的路径长度，再将每个叶子节点的路径长度乘上它的权值，最后把所有叶子节点的乘积相加即可得到带权路径长度。

以下是 C 语言实现哈夫曼树带权路径长度的代码示例：

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

typedef struct node {
    int weight;
    struct node *left;
    struct node *right;
} Node;

typedef struct heap {
    int size;
    int capacity;
    Node **nodes;
} Heap;

Node* create_node(int weight) {
    Node* node = (Node*) malloc(sizeof(Node));
    node->weight = weight;
    node->left = NULL;
    node->right = NULL;
    return node;
}

Heap* create_heap(int capacity) {
    Heap* heap = (Heap*) malloc(sizeof(Heap));
    heap->size = 0;
    heap->capacity = capacity;
    heap->nodes = (Node**) malloc(sizeof(Node*) * capacity);
    return heap;
}

void swap_node(Node **a, Node **b) {
    Node *temp = *a;
    *a = *b;
    *b = temp;
}

void heapify(Heap *heap, int index) {
    int smallest = index;
    int left = 2 * index + 1;
    int right = 2 * index + 2;

    if (left < heap->size && heap->nodes[left]->weight < heap->nodes[smallest]->weight) {
        smallest = left;
    }
    if (right < heap->size && heap->nodes[right]->weight < heap->nodes[smallest]->weight) {
        smallest = right;
    }
    if (smallest != index) {
        swap_node(&heap->nodes[smallest], &heap->nodes[index]);
        heapify(heap, smallest);
    }
}

void build_heap(Heap *heap) {
    int n = heap->size;
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(heap, i);
    }
}

Node* extract_min(Heap *heap) {
    Node* min_node = heap->nodes[0];
    heap->nodes[0] = heap->nodes[heap->size - 1];
    heap->size--;
    heapify(heap, 0);
    return min_node;
}

void insert(Heap *heap, Node *node) {
    if (heap->size == heap->capacity) {
        printf("Heap is full!\n");
        return;
    }
    heap->size++;
    int i = heap->size - 1;
    while (i > 0 && node->weight < heap->nodes[(i - 1) / 2]->weight) {
        heap->nodes[i] = heap->nodes[(i - 1) / 2];
        i = (i - 1) / 2;
    }
    heap->nodes[i] = node;
}

Node* build_huffman_tree(int *weights, int n) {
    Heap* heap = create_heap(n);
    for (int i = 0; i < n; i++) {
        Node* node = create_node(weights[i]);
        insert(heap, node);
    }
    build_heap(heap);
    while (heap->size > 1) {
        Node* left = extract_min(heap);
        Node* right = extract_min(heap);
        Node* parent = create_node(left->weight + right->weight);
        parent->left = left;
        parent->right = right;
        insert(heap, parent);
    }
    Node* root = extract_min(heap);
    free(heap->nodes);
    free(heap);
    return root;
}

void calculate_wpl(Node* node, int depth, int *wpl) {
    if (node == NULL) {
        return;
    }
    if (node->left == NULL && node->right == NULL) {
        *wpl += node->weight * depth;
        return;
    }
    calculate_wpl(node->left, depth + 1, wpl);
    calculate_wpl(node->right, depth + 1, wpl);
}

int huffman_wpl(int *weights, int n) {
    Node* root = build_huffman_tree(weights, n);
    int wpl = 0;
    calculate_wpl(root, 0, &wpl);
    return wpl;
}

int main() {
    int weights[] = {1, 3, 2, 7, 5};
    int n = sizeof(weights) / sizeof(weights[0]);
    int wpl = huffman_wpl(weights, n);
    printf("Huffman tree WPL = %d\n", wpl);
    return 0;
}

在以上示例中，`build_huffman_tree` 函数用于构建哈夫曼树，`calculate_wpl` 函数用于计算带权路径长度，`huffman_wpl` 函数用于将二者结合起来计算哈夫曼树的带权路径长度。最后，在 `main` 函数中，我们定义了一个权值数组，并调用 `huffman_wpl` 函数计算哈夫曼树的带权路径长度，然后输出结果。