二叉树WPL计算的完整c++代码

以下是二叉树WPL计算的完整C代码：

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

typedef struct node {
    int freq;
    struct node *left, *right;
} Node;

typedef struct minHeap {
    int size;
    Node **nodes;
} MinHeap;

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

MinHeap* createMinHeap(int capacity) {
    MinHeap *minHeap = (MinHeap *) malloc(sizeof(MinHeap));
    minHeap->size = 0;
    minHeap->nodes = (Node **) malloc(capacity * sizeof(Node *));
    return minHeap;
}

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

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

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

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

    if (smallest != index) {
        swapNode(&minHeap->nodes[smallest], &minHeap->nodes[index]);
        heapify(minHeap, smallest);
    }
}

int isSizeOne(MinHeap *minHeap) {
    return (minHeap->size == 1);
}

Node* extractMin(MinHeap *minHeap) {
    Node *node = minHeap->nodes[0];
    minHeap->nodes[0] = minHeap->nodes[minHeap->size - 1];
    --minHeap->size;
    heapify(minHeap, 0);
    return node;
}

void insertMinHeap(MinHeap *minHeap, Node *node) {
    ++minHeap->size;
    int index = minHeap->size - 1;
    while (index && node->freq < minHeap->nodes[(index - 1) / 2]->freq) {
        minHeap->nodes[index] = minHeap->nodes[(index - 1) / 2];
        index = (index - 1) / 2;
    }
    minHeap->nodes[index] = node;
}

void buildMinHeap(MinHeap *minHeap) {
    int n = minHeap->size - 1;
    for (int i = (n - 1) / 2; i >= 0; --i) {
        heapify(minHeap, i);
    }
}

int calculateWPL(Node *node, int depth) {
    if (!node) {
        return 0;
    }
    if (!node->left && !node->right) {
        return node->freq * depth;
    }
    return calculateWPL(node->left, depth + 1) + calculateWPL(node->right, depth + 1);
}

int main() {
    int n;
    printf("Enter the number of nodes in the binary tree: ");
    scanf("%d", &n);

    MinHeap *minHeap = createMinHeap(n);

    for (int i = 0; i < n; ++i) {
        int freq;
        printf("Enter frequency of node %d: ", i + 1);
        scanf("%d", &freq);
        Node *node = newNode(freq);
        insertMinHeap(minHeap, node);
    }

    buildMinHeap(minHeap);

    while (!isSizeOne(minHeap)) {
        Node *left = extractMin(minHeap);
        Node *right = extractMin(minHeap);

        Node *node = newNode(left->freq + right->freq);
        node->left = left;
        node->right = right;

        insertMinHeap(minHeap, node);
    }

    printf("The WPL of the binary tree is: %d", calculateWPL(minHeap->nodes[0], 0));

    return 0;
}

此代码实现了最小堆数据结构，其中每个节点都有一个权重值。代码构造了一棵二叉树并计算了其WPL（带权路径长度）。请注意，此代码仅作为参考，您需要根据自己的需求进行修改。