二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T, 采用二叉链表存储,结点结构为:left weight right,其中叶结点的weight域保存该结点的非负权值。设root为指向T的根结点的指针,请设计求T的WPL的算法
时间: 2023-11-28 22:49:28 浏览: 165
第六章 树和二叉树作业及答案(100分).docx
可以采用递归的方式来求解二叉树的带权路径长度(WPL)。具体步骤如下:
1. 如果当前结点为叶子结点,则返回该结点的权值。
2. 否则,分别递归计算左子树和右子树的WPL,并将它们的和加上当前结点的权值作为当前子树的WPL。
3. 最终,递归返回根结点的WPL作为整棵二叉树的WPL。
下面是该算法的实现代码:
```python
def calc_wpl(root):
if root is None:
return 0
if root.left is None and root.right is None:
return root.weight
left_wpl = calc_wpl(root.left)
right_wpl = calc_wpl(root.right)
return left_wpl + right_wpl + root.weight
```
其中,root.left和root.right分别表示左子树和右子树的根结点,root.weight表示当前结点的权值。
阅读全文