题目来源于王道论坛 二叉树的带权路径长度（W

解答：

1）算法的基本设计思想：

① 基于先序递归遍历的算法思想是用一个static变量记录wpl，把每个结点的深度作为递归函数的一个参数传递，算法步骤如下：

若该结点是叶子结点，那么变量wpl加上该结点的深度与权值之积；

若该结点非叶子结点，那么若左子树不为空，对左子树调用递归算法，若右子树不为空，对右子树调用递归算法，深度参数均为本结点的深度参数加1；

最后返回计算出的wpl即可。

② 基于层次遍历的算法思想是使用队列进行层次遍历，并记录当前的层数，

当遍历到叶子结点时，累计wpl；

当遍历到非叶子结点时对该结点的把该结点的子树加入队列；

当某结点为该层的最后一个结点时，层数自增1；

队列空时遍历结束，返回wpl。

2）二叉树结点的数据类型定义如下：

typedef struct BiTNode{
 int weight;
 struct BiTNode *lchild,*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->rchild == 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和深度
 BiTree lastNode;             //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;
 }
 if(t == lastNode){       //若该结点为本层最后一个结点，更新lastNode
 lastNode = newlastNode;
 deep += 1;            //层数加1
 }
 } //while
 return wpl;                  //返回wpl
}

【评分说明】

= 1 \* GB3 ① 若考生给出能够满足题目要求的其他算法，且正确，可同样给分。

= 2 \* GB3 ② 考生答案无论使用C或者C++语言，只要正确同样给分。

= 3 \* GB3 ③ 若对算法的基本设计思想和主要数据结构描述不十分准确，但在算法实现中能够清晰反映出算法思想且正确，参照 = 1 \* GB3 ①的标准给分。

= 4 \* GB3 ④ 若考生给出的二叉树结点的数据类型定义和算法实现中，使用的是除整型之外的其他数值，可视同使用整型类型。

= 5 \* GB3 ⑤ 若考生给出的答案中算法主要设计思想或算法中部分正确，可酌情给分。

注意：上述两个算法一个为递归的先序遍历，一个为非递归的层次遍历，读者应当选取自己最擅长的书写方式。直观看去，先序遍历代码行数少，不用运用其他工具，书写也更容易，希望读者能掌握。

在先序遍历的算法中，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==NULL) //若为叶子结点，累积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)modM，采用的是2014年真题选择题中第三题的队列形式。同时，考生也可以尝试使用记录每层的第一个结点来进行层次遍历的算法，这里不再给出代码，请考生自行练习。