数据结构
2014-41
二叉树的带权路径长度（WPL）是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T，采用二叉链表存储，结点结构如下：
其中叶结点的weight域保存该结点的非负权值。设root为指向T的根结点的指针，请设计求T的WPL的算法，要求：
1）给出算法的基本设计思想。
2）使用C或C++语言，给出二叉树结点的数据类型定义。
3）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
答案
【答案】
（1）算法基本设计思想
方法一：基于先序递归遍历。定义递归函数，将当前结点的深度作为参数传递。若结点为叶子结点，则累加 深度 * 权值 到结果；否则，递归遍历其左右子树，并将深度参数加1。
方法二：基于层次遍历（BFS）。使用队列实现层次遍历，并记录当前层数 deep。利用指针 lastNode 标记当前层最后一个结点。当遍历到叶子结点时，累加 deep * 权值。每当处理完 lastNode 结点，就更新 lastNode 为下一层的最后一个结点，并将 deep 加1。
（2）二叉树结点的数据类型定义（C语言）
typedef struct BiTNode {
int weight; // 存储权值
struct BiTNode *lchild, *rchild; // 左、右孩子指针
} BiTNode, *BiTree;（3）算法描述（C语言）
方法一：先序递归
int wpl_PreOrder(BiTree root, int deep);
int wpl_LevelOrder(BiTree root);
int WPL(BiTree root) {
return wpl_PreOrder(root, 0); // 基于先序遍历
// 如需使用层次遍历，可改为：return wpl_LevelOrder(root);
}
int wpl_PreOrder(BiTree root, int deep) {
if (root == NULL) return 0; // 空树返回0
if (root->lchild == NULL && root->rchild == NULL)
return deep * root->weight;
return wpl_PreOrder(root->lchild, deep + 1)
+ wpl_PreOrder(root->rchild, deep + 1);
}方法二：层次遍历
int wpl_LevelOrder(BiTree root) {
BiTree q[MaxSize]; // 声明队列，end1为头指针，end2为尾指针
int end1, end2 = 0;
end1 = end2 = 0;
int wpl = 0, deep = 0;
BiTree lastNode;
BiTree newlastNode;
lastNode = root;
newlastNode = NULL;
q[end2++] = root;
while (end1 != end2) {
BiTree t = q[end1++];
if (t->lchild == NULL && t->rchild == NULL) {
wpl += deep * t->weight;
}
if (t->lchild != NULL) {
q[end2++] = t->lchild;
newlastNode = t->lchild;
}
if (t->rchild != NULL) {
q[end2++] = t->rchild;
newlastNode = t->rchild;
}
if (t == lastNode) {
lastNode = newlastNode;
deep += 1;
}
}
return wpl; // 返回wpl
}