首页 26考研 在职考研 直播好课 大纲冲刺

新东方在线 > 考研 > 计算机 > 考研计算机真题 > 正文

扫码加入训练营

牢记核心词

学习得礼盒

41.(13分)二叉树的带权路径长度(WPL)是二叉树中所有叶结点的

2021-07-20 07:15:00来源：

　　【题目】

　　41.(13分)二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T，采用二叉链表存储，结点结构为：，其中叶结点的weight域保存该结点的非负权值。设root为指向T的根结点的指针，请设计求T的WPL的算法。要求：

　　(1)给出算法的基本设计思想;

　　(2)使用C或C++语言，给出二叉树结点的数据类型定义;

　　(3)根据设计思想，采用C或C++语言描述算法，关键之处给出注释。

　　【答案参考】：

　　【答案一】

　　(1)算法的设计思想：

　　本问题可采用递归算法实现。根据定义：

　　二叉树的WPL值=树中全部叶结点的带权路径长度之和

　　 =根结点左子树中全部叶结点的带权路径长度之和+根结点右子树中全部叶结点的带权路

　　 径长度之和

　　叶结点的带权路径长度=该结点的weight域的值×该结点的深度

　　设根结点的深度为0，若某结点的深度为d时，则其孩子结点的深度为d+1。

　　(2)算法中使用的二叉树结点的数据类型定义如下：

　　typedef struct node

　　{

　　int weight：

　　struct node * left，* right;

　　} BTree;

　　(3)算法实现：

　　int WPL(BTree * root) //根据WPL的定义采用递归算法实现

　　{ return WPL1(root，0);

　　}

　　int WPLl (BTree * root，int d) //d为结点深度

　　{ if(root->left==NULL && root->right==NULL)

　　return(root->weight * d);

　　else

　　return(WPL1(root->left，d+1)+WPLl (root->right，d+1));

　　}

　　【答案二】

　　(1)算法的设计思想：

　　若借用非叶结点的weight域保存其孩子结点中weight域值的和，则树的WPL等于树中所有非叶结点weight域值之和。

　　采用后序遍历策略，在遍历二叉树T时递归计算每个非叶结点的weight域的值，则树T的WPL等于根结点左子树的WPL加上右子树的WPL，再加上根结点中weight域的值。

　　(2)算法中使用的二叉树结点的数据类型定义同【答案一】。

　　(3)算法实现：

　　int WPL(BTree*root) //基于递归的后序遍历算法实现

　　{ int w_l，w_r;

　　if(root->left==NULL && root->right==NULL)

　　return 0：

　　else

　　{ w_l=WPL(root->left); //计算左子树的WPL

　　w_r=WPL(root->right); //计算右子树的WPL

　　root->weight=root->left->weight + root->right->weight;//填写非叶结点的weight域

　　return(w_l+w_r + root->weight);//返回WPL值

　　}

　　}


考研公开课小程序

本文关键字: 二叉树的带权路径长度(WPL)

考研英语核心词汇营

背词+听课+练习+督学，学习得礼盒

更多资料

添加班主任领资料

添加考研班主任
免费领取考研历年真题等复习干货资料

  • 1.打开手机微信【扫一扫】，识别上方二维码；
  • 2.添加班主任，可领取学习资料。
更多>>
更多内容
看课程 MBA 优惠券 0元学 领资料

关注新东方在线考研服务号

获得21考研真题及答案解析

1. 打开手机微信【扫一扫】，识别上方二维码；
2.点击【关注公众号】，获取资料大礼包。

名师试听

历年考研真题及答案解析下载

英语一 英语二 政治 数学一 数学二 数学三 西医综合 教育综合 心理学综合
立即下载
近10年考研真题及答案免费下载
更多>>
更多公开课>>
更多>>
更多资料
我要
反馈 返回
首页
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10