【题目】
41.(13分)二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T，采用二叉链表存储，结点结构为：
，其中叶结点的weight域保存该结点的非负权值。设root为指向T的根结点的指针，请设计求T的WPL的算法。要求：
(1)给出算法的基本设计思想;
(2)使用C或C++语言，给出二叉树结点的数据类型定义;
(3)根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
【答案参考】：
【答案一】
(1)算法的设计思想：
本问题可采用递归算法实现。根据定义：
二叉树的WPL值=树中全部叶结点的带权路径长度之和
=根结点左子树中全部叶结点的带权路径长度之和+根结点右子树中全部叶结点的带权路
径长度之和
叶结点的带权路径长度=该结点的weight域的值×该结点的深度
设根结点的深度为0，若某结点的深度为d时，则其孩子结点的深度为d+1。
(2)算法中使用的二叉树结点的数据类型定义如下：
typedef struct node
{
int weight：
struct node * left，* right;
} BTree;
(3)算法实现：
int WPL(BTree * root) //根据WPL的定义采用递归算法实现
{ return WPL1(root，0);
}
int WPLl (BTree * root，int d) //d为结点深度
{ if(root->left==NULL && root->right==NULL)
return(root->weight * d);
else
return(WPL1(root->left，d+1)+WPLl (root->right，d+1));
}
【答案二】
(1)算法的设计思想：
若借用非叶结点的weight域保存其孩子结点中weight域值的和，则树的WPL等于树中所有非叶结点weight域值之和。
采用后序遍历策略，在遍历二叉树T时递归计算每个非叶结点的weight域的值，则树T的WPL等于根结点左子树的WPL加上右子树的WPL，再加上根结点中weight域的值。
(2)算法中使用的二叉树结点的数据类型定义同【答案一】。
(3)算法实现：
int WPL(BTree*root) //基于递归的后序遍历算法实现
{ int w_l，w_r;
if(root->left==NULL && root->right==NULL)
return 0：
else
{ w_l=WPL(root->left); //计算左子树的WPL
w_r=WPL(root->right); //计算右子树的WPL
root->weight=root->left->weight + root->right->weight;//填写非叶结点的weight域
return(w_l+w_r + root->weight);//返回WPL值
}
}