41.（13分）二叉树的带权路径长度（WPL）是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T，采用二叉链表存储，结点结构如下∶ Lef、weight、right 其中叶结点的weight域保存该结点的非负权值。设root为指向T的根结点的指针，请设计求T 的WPL的算法，要求∶ 1）给出算法的基本设计思想。 2）使用C或 C++语言，给出二叉树结点的数据类型定义。 3）根据设计思想，采用C或 C++语言描述算法，关键之处给出注释。
【参考答案及解析】
考查二叉树的带权路径长度，二叉树的带权路径长度为每个叶子结点的深度与权值之积的总和，可以使用先序遍历或层次遍历解决问题。 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年真题选择题中第二题的队列形式。同时，考牛也可以尝试使用记录每层的第一个结点来进行层次遍历的算法，这里不再给出代码，请考生自行练习。
正在整理中,欢迎在文下评论区提供答案解析,谢谢！
考查二叉树的带权路径长度，二叉树的带权路径长度为每个叶子结点的深度与权值之积的总和，可以使用先序遍历或层次遍历解决问题。 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年真题选择题中第二题的队列形式。同时，考牛也可以尝试使用记录每层的第一个结点来进行层次遍历的算法，这里不再给出代码，请考生自行练习。
正在整理中,欢迎在文下评论区提供答案解析,谢谢！