二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和,给定一棵二叉树T,采用二叉链表存储,节点结构为:
left | weight | right |
其中叶节点的weight域保存该结点的非负权值。设root为指向T的根节点的指针,设计求T的WPL的算法。要求:
(1)给出算法的基本设计思想;
(2)使用C或C++语言,给出二叉树结点的数据类型定义;
(3)根据设计思想,采用C或C++语言描述算法,关键之处给出注释。
(1) 算法的设计思想:
递归遍历二叉树,利用一个参数同时对深度进行计数。叶结点的带权路径长度=该结点的 weigth 值*该结点的深度。
每个叶结点的带权路径长度都可以求出, 二叉树的 WPL 值=树
中
全部叶结点的带权路径长度之和=根结点左子树中全部叶结点的带权路径长度之和+根结点右子树中全部叶结点的带权路径长度之和。
递归进行求和, 即可求出二叉树的带权路径长
度。
(2) 算法中使用的二叉树结点的数据类型定义如下:
typedef struct BTnode { unsigned int weight; //结点的非负权值 struct BTnode * lchild, * rchild; //左右指针 }BTnode;(3) 算法实现:
int main() { return WPL(root,0); //初始化深度,调用 WPL 函数 } int WPL(BTnode * root,int d) //其中 d 为结点深度 { if(root->lchild==NULL&&root->rchild==NULL)//root 为叶子结点 return (root->weight * d); //返回该叶子结点的带权路径长度 else return(WPL(root-> lchild,d+1)+WPL(root->rchild,d+1)); /*返回左右子树中全部叶结点的带权路径长度之和*/ }
public Class Tree{ class Node{ int weight; Node left,right; } public int getWPL(Node root, int depth){ if(root == null){ return 0; } if(root.left == null && root.right == null){ return root.weight * depth; } return getWPL(root.left, depth + 1) + getWPL(root.right, depth + 1) } }
typedef struct TreeNode { struct TreeNode *left, *right; int weight; } *Tree; int WPL(Tree tree, int depth) { if (tree == NULL) { return 0; } if (tree->left == NULL && tree->right == NULL) { return (tree->weight * depth);//已经到叶子结点了:返回本层的wpl } else { return (tree->weight * depth) + (WPL(tree->left, depth + 1) + WPL(tree->right, depth + 1));//返回本层wpl+左右子树的wpl } }
(1) 算法的设计思想:
递归遍历二叉树,利用一个参数同时对深度进行计数。叶结点的带权路径长度=该结点的 weigth 值*该结点的深度。 每个叶结点的带权路径长度都可以求出, 二叉树的 WPL 值=树 中 全部叶结点的带权路径长度之和=根结点左子树中全部叶结点的带权路径长度之和+根结点右子树中全部叶结点的带权路径长度之和。 递归进行求和, 即可求出二叉树的带权路径长 度。
(2) 算法中使用的二叉树结点的数据类型定义如下:
1 2 3 4 5 | typedefstructBTnode { unsignedintweight;//结点的非负权值 structBTnode * lchild, * rchild;//左右指针 }BTnode; |
1 2 3 4 5 6 7 8 9 10 11 12 | intmain() { returnWPL(root,0);//初始化深度,调用 WPL 函数 } intWPL(BTnode * root,intd)//其中 d 为结点深度 { if(root->lchild==NULL&&root->rchild==NULL)//root 为叶子结点 return(root->weight * d);//返回该叶子结点的带权路径长度 else return(WPL(root-> lchild,d+1)+WPL(root->rchild,d+1)); /*返回左右子树中全部叶结点的带权路径长度之和*/ } |