二叉树带权路径长度 (WPL) 计算算法详解及 C 语言实现

定义：二叉树的带权路径长度 (WPL) 是二叉树中所有叶节点的带权路径长度之和。每个叶节点的带权路径长度定义为：该节点的权值乘以该节点到根节点的路径长度。

问题：给定一棵二叉树 T，采用二叉链表存储，结点结构如下:

left
weight
right

其中叶结点的 weight 域保存该结点的非负权值。设 root 为指向 T 的根结点的指针，请设计求 T 的 WPL 的算法，要求:

给出算法的基本设计思想。
使用 C 语言，给出二叉树结点的数据类型定义。
根据设计思想，采用 C 语言描述算法，关键之处给出注释。

算法设计思想:

遍历二叉树，计算每个叶节点的带权路径长度（叶节点的权值乘以叶节点到根节点的路径长度）；
将所有叶节点的带权路径长度相加，得到二叉树的 WPL。

二叉树结点的数据类型定义（使用 C 语言）:

struct TreeNode {
    struct TreeNode* left; // 左子节点指针
    int weight; // 非负权值
    struct TreeNode* right; // 右子节点指针
};
typedef struct TreeNode TreeNode;

C 语言描述算法:

// 计算二叉树的 WPL
int calculateWPL(TreeNode* root) {
    // 如果根节点为空，则 WPL 为 0
    if (root == NULL) {
        return 0;
    }
    // 如果是叶节点，则返回叶节点的权值
    if (root->left == NULL && root->right == NULL) {
        return root->weight;
    }
    // 递归计算左子树的 WPL 和右子树的 WPL
    int leftWPL = calculateWPL(root->left);
    int rightWPL = calculateWPL(root->right);
    // 返回左子树的 WPL 加上右子树的 WPL 加上根节点到叶节点的路径长度（根节点的权值乘以 2）
    return leftWPL + rightWPL + root->weight * 2;
}

注：以上算法假设叶节点到根节点的路径长度为叶节点的深度，即根节点的深度为 0，根节点的子节点的深度为 1，以此类推。

代码示例:

#include <stdio.h>

struct TreeNode {
    struct TreeNode* left;
    int weight;
    struct TreeNode* right;
};

int calculateWPL(struct TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    if (root->left == NULL && root->right == NULL) {
        return root->weight;
    }
    return calculateWPL(root->left) + calculateWPL(root->right) + root->weight * 2;
}

int main() {
    // 创建一个示例二叉树
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->weight = 1;
    root->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->left->weight = 2;
    root->left->left = NULL;
    root->left->right = NULL;
    root->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->right->weight = 3;
    root->right->left = NULL;
    root->right->right = NULL;

    // 计算 WPL
    int wpl = calculateWPL(root);
    printf("WPL: %d\n", wpl);
    return 0;
}

输出:

WPL: 10

总结

本文详细介绍了如何计算二叉树的带权路径长度 (WPL)，包括算法设计思想、数据结构定义以及 C 语言代码实现。文章还提供了代码注释，帮助读者更好地理解算法的逻辑。通过本文的学习，读者可以掌握 WPL 的概念以及计算方法，并能够运用 C 语言代码进行实际操作。