考查二叉树的带权路径长度，二叉树的带权路径长度为每个叶子结点的深度与权值之积的总和，可以使用先序遍历或层次遍历解决问题。
1）算法的基本设计用想∶
①基于先序递归遍历的算法思想是用一个 static 变量记录 wpl，把每个结点的深度作为递归函数的一个参数传递，算法步骤如下∶
若该结点是叶子结点，那么变量wpl加上该结点的深度与权值之积;
若该结点非叶子结点，那么若左子树不为空，对左子树调用递归算法，若右子树不为空，对右子树调用递归算法，深度参数均为本结点的深度参数加一;
最后返回计算出的 wpl即可。
②基于层次遍历的算法思想是使用队列进行层次遍历，并记录当前的层数，当遍历到叶子结点时，累计wpl;
当遍历到非叶子结点时对该结点的把该结点的子树加入队列;
当某结点为该层的最后一个结点时，层数自增1;
队列空时遍历结束，返回 wpl
2）二叉树结点的数据类型定义如下∶
typedef struct BiTNode{
int weight;
struct BiTNode *Ichild,*rchild;
}BiTNode,*BiTree;
3）算法代码如下∶
①基于先序遍历的算法∶
int WPL(BiTree root){
return wpl_PreOrder(root, 0);
}
int wpl_PreOrder(BiTree root, int deep){
static int wpl =0; //定义一个static 变量存储 wpl
if(root->lchild= NULL&& root->lchild== NULL) //若为叶子结点，累积 wpl
wpl += deep*root->weight;
if(root->lchild != NULL) //若左子树不空，对左子树递归遍历
Wpl_PreOrder(root->lchild, deep+1);
if(root->rchild != NULL) //若右子树不空，对右子树递归遍历
Wpl_PreOrder(root->rchild, deep+1);
return wpl;
}
②基于层次遍历的算法∶
#define MaxSize 100 //设置队列的最大容量
int wpl LevelOrder(BiTree root){
BiTree q[MaxSize]; //声明队列，end1为头指针，end2为尾指针
int end1, end2; //队列最多容纳 MaxSize-1个元素
end1 =end2=0; //头指针指向队头元素，尾指针指向队尾的后一个元素
int wpl = 0, deep = 0; //初始化 wpl和深度
BiTreelastNode; //lastNode 用来记录当前层的最后一个结点
BiTree newlastNode; //newlastNode 用来记录下一层的最后一个结点
lastNode = root; //lastNode 初始化为根节点
newlastNode = NULL; //newlastNode 初始化为空
q[end2++] = root; //根节点入队
while(end1!= end2){ //层次遍历，若队列不空则循环
BiTree t = q[end1++]; //拿出队列中的头一个元素
if(t->lchild == NULL&t->lchild = NULL){
wpl += deep*t->weight;
} //若为叶子结点，统计 wpl
if（t->lchild!=NULL）{ //若非叶子结点把左结点入队
q[end2++] = t->lchild;
newlastNode = t->lchild;
} //并设下一层的最后一个结点为该结点的左结点
if（t->rchild != NULL）{//处理叶节点
q[end2++] = t->rchild;
newlastNode = t->rchild;
}
ift== lastNode){ //若该结点为本层最后一个结点，更新 lastNode
lastNode = newlastNode;
deep += 1; //层数加1
}
}
return wpl; //返回 wpl
}
【评分说明】
①若考生给出能够满足题目要求的其他算法，且正确，可同样给分。
②考生答案无论使用C或者C++语言，只要正确同样给分。
③若对算法的基本设计思想和主要数据结构描述不十分准确，但在算法实现中能够清晰反映出算法思想且正确，参照①的标准给分。
④若考生给出的二叉树结点的数据类型定义和算法实现中，使用的是除整型之外的其他数值，可视同使用整型类型。
⑤若考生给出的答案中算法主要设计思想或算法中部分正确，可酌情给分。
注意∶上述两个算法一个为递归的先序遍历，一个为非递归的层次遍历，读者应当选取日口最擅长的书与方式。百观看天。先序漏力什码马行数。不用运用其他工且。书写也更容易，希望读者能掌握。
在先序遍历的算法中，static 是一个静态变量，只在首次调用函数时声明 wpl 并赋值为0，以后的递归调用并不会使得 wpl为0，具体用法请参考相关资料中的 static 关键字说明，也可以在函数之外预先设置一个全局变量，并初始化。不过考虑到历年真题算法答案通常都直接仅仅由一个函数构成，所以参考答案使用 static。若对 static 不熟悉的同学可以使用以下形式的递归∶
int wpl_PreOrder(BiTree root, int deep){
int lwpl, rwpl; //用于存储左子树和右子树的产生的 wpl
lwpl= rwpl = 0;
if(root->lchild == NULL&& root->lchild = NULL) //若为叶子结点，计算当前叶子结点的 wpl
return deep*root->weight;
if(root->lchild != NULL) //若左子树不空，对左子树递归遍历
lwpl= wpl_PreOrder(root->lchild, deep+1);
if(root->rchild != NULL) //若右子树不空，对右子树递归遍历
rwpl = wpl PreOrder(root->rchild, deep+1);
return lwpl+ rwpl;
}
C/C++语言基础好的同学可以使用更简便的以下形式∶
int wpl PreOrder(BiTree root, int deep){
if（root->lchild == NULL&& root->lchild = NUL） //若为叶子结点，累积 wpl
return deep*root->weight;
return (root->lchild != NULL ? wpl PreOrder(root->lchild, deep+1):0)
+(root->rchild != NULL? wpl PreOrder(root->rchild, deep+1):0);
}
这个形式只是上面方法的简化而已，本质是一样的，而这个形式代码更短，在时间有限的情况下更具优势，能比写层次遍历的考生节约很多时间，所以读者应当在保证代码正确的情况下，尽量写一些较短的算法，为其他题目赢得更多的时间。但是，对干基础不扎实的考生，还是建议使用写对把握更大的方法。否则可能会得不偿失。例如在上面的代码中。考生容易忘记三元式（x?y:z）两端的括号，若不加括号，则答案就会是错误的。
在层次遍历的算法中，读者要理解 lastNode 和 newlastNode 的区别，lastNode 指的是当前遍历层的最后一个结点。而 newlastNode指的是下一层的最后一个结点。是动态变化的直到遍历到本层的最后一个结点，才能确认下层真正的最后一个结点是哪个结点，而函数中入队操作并没有判断队满，若考试时用到，读者最好加 上队人满条件。这里队人列的人满条件为end1==（end2+1）%M，采用的是 2014年真题选择题中第二题的队列形式。同时，考牛也可以尝试使用记录每层的第一个结点来进行层次遍历的算法，这里不再给出代码，请考生自行练习。