题目来源于王道论坛
二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T,采用二叉链表存储,结点结构为:
left | weight | right |
其中叶结点的weight域保存该结点的非负权值。设root为指向T的根结点的指针,请设计求T的WPL的算法,要求:
1)给出算法的基本设计思想;
2)使用C或C++语言,给出二叉树结点的数据类型定义;
3)根据设计思想,采用C或C++语言描述算法,关键之处给出注释。
解答:
1)算法的基本设计思想:
① 基于先序递归遍历的算法思想是用一个static变量记录wpl,把每个结点的深度作为递归函数的一个参数传递,算法步骤如下:
若该结点是叶子结点,那么变量wpl加上该结点的深度与权值之积;
若该结点非叶子结点,那么若左子树不为空,对左子树调用递归算法,若右子树不为空,对右子树调用递归算法,深度参数均为本结点的深度参数加1;
最后返回计算出的wpl即可。
② 基于层次遍历的算法思想是使用队列进行层次遍历,并记录当前的层数,
当遍历到叶子结点时,累计wpl;
当遍历到非叶子结点时对该结点的把该结点的子树加入队列;
当某结点为该层的最后一个结点时,层数自增1;
队列空时遍历结束,返回wpl。
2)二叉树结点的数据类型定义如下:
3)算法代码如下:
① 基于先序遍历的算法:
② 基于层次遍历的算法:
【评分说明】
= 1 \* GB3 ① 若考生给出能够满足题目要求的其他算法,且正确,可同样给分。
= 2 \* GB3 ② 考生答案无论使用C或者C++语言,只要正确同样给分。
= 3 \* GB3 ③ 若对算法的基本设计思想和主要数据结构描述不十分准确,但在算法实现中能够清晰反映出算法思想且正确,参照 = 1 \* GB3 ①的标准给分。
= 4 \* GB3 ④ 若考生给出的二叉树结点的数据类型定义和算法实现中,使用的是除整型之外的其他数值,可视同使用整型类型。
= 5 \* GB3 ⑤ 若考生给出的答案中算法主要设计思想或算法中部分正确,可酌情给分。
注意:上述两个算法一个为递归的先序遍历,一个为非递归的层次遍历,读者应当选取自己最擅长的书写方式。直观看去,先序遍历代码行数少,不用运用其他工具,书写也更容易,希望读者能掌握。
在先序遍历的算法中,static是一个静态变量,只在首次调用函数时声明wpl并赋值为0,以后的递归调用并不会使得wpl为0,具体用法请参考相关资料中的static关键字说明,也可以在函数之外预先设置一个全局变量,并初始化。不过考虑到历年真题算法答案通常都直接仅仅由一个函数构成,所以参考答案使用static。若对static不熟悉的同学可以使用以下形式的递归:
C/C++语言基础好的同学可以使用以下更简便的形式:
这个形式只是上面方法的简化而已,本质是一样的,而这个形式的代码更短,在时间有限的情况下更具优势,相比写层次遍历能节约很多时间,所以读者应当在保证代码正确的情况下,尽量写一些较短的算法,为其他题目赢得更多的时间。但是,对于基础不扎实的考生,还是建议使用把握更大的方法,否则可能会得不偿失。例如在上面的代码中,考生容易忘记三元式(x?y:z)两端的括号,若不加括号,则答案就会是错误的。
在层次遍历的算法中,读者要理解lastNode和newlastNode的区别,lastNode指的是当前遍历层的最后一个结点,而newlastNode指的是下一层的最后一个结点,是动态变化的,直到遍历到本层的最后一个结点,才能确认下层真正的最后一个结点是哪个结点,而函数中入队操作并没有判断队满,若考试时用到,读者最好加上队满条件,这里队列的队满条件为end1==(end2+1)modM,采用的是2014年真题选择题中第三题的队列形式。同时,考生也可以尝试使用记录每层的第一个结点来进行层次遍历的算法,这里不再给出代码,请考生自行练习。