二叉树的WPL计算代码

以下是二叉树的WPL（带权路径长度）计算代码，使用了递归算法：

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def get_wpl(node, depth):
    if not node:
        return 0
    if not node.left and not node.right:
        return node.val * depth
    return get_wpl(node.left, depth + 1) + get_wpl(node.right, depth + 1)

def binary_tree_wpl(root):
    return get_wpl(root, 0)

其中，`Node` 是二叉树节点的定义，包括节点的值 `val` 和左右子节点 `left` 和 `right`。`get_wpl` 是递归计算二叉树的WPL的函数，接受两个参数：当前节点 `node` 和当前节点的深度 `depth`。如果当前节点是叶子节点，则返回节点的值乘以深度，否则返回左子树和右子树的WPL之和。`binary_tree_wpl` 是计算二叉树WPL的主函数，接受根节点 `root` 并调用 `get_wpl` 计算WPL。

相关问题

二叉树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（带权路径长度）。请注意，此代码仅作为参考，您需要根据自己的需求进行修改。

二叉树的WPL计算的代码

二叉树的WPL（带权路径长度）是指所有叶子节点的带权路径长度之和，可以通过遍历二叉树来计算。以下是一个递归实现的示例代码：

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def wpl(root, depth=0):
    if root is None:
        return 0
    if root.left is None and root.right is None:
        return root.val * depth
    return wpl(root.left, depth + 1) + wpl(root.right, depth + 1)

其中，`Node` 类表示二叉树节点，包含节点值 `val`、左子树 `left` 和右子树 `right`。`wpl` 函数接收根节点 `root` 和当前深度 `depth`，返回以当前节点为根的子树的WPL。

在递归过程中，如果当前节点是叶子节点，则返回该节点的值乘以当前深度；否则，递归计算左子树和右子树的WPL，并将它们相加返回。

最后，调用 `wpl` 函数时传入根节点即可计算二叉树的WPL。