二叉树的wpl怎么算
时间: 2023-11-13 10:02:52 浏览: 115
二叉树的带权路径长度(WPL)是指所有叶子节点的带权路径长度之和。下面是两种计算二叉树WPL的方法:
1. 非递归算法
算法思想:根据公式,需要记录每个结点到根结点的分支个数,这个过程通过对树进行广度遍历(借助队列)进行记录。在非叶子结点weight初值为-1,叶子结点初值设为非负权值。最后对队列进行逐个访问,如果weight != -1,那就计算该点。
```python
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
self.weight = -1
def wpl(root):
if not root:
return 0
wpl_sum = 0
queue = [root]
while queue:
node = queue.pop(0)
if not node.left and not node.right:
wpl_sum += node.weight * node.depth
if node.left:
node.left.depth = node.depth + 1
node.left.weight = node.weight + 1
queue.append(node.left)
if node.right:
node.right.depth = node.depth + 1
node.right.weight = node.weight + 1
queue.append(node.right)
return wpl_sum
```
2. 递归算法
算法思想:递归计算左右子树的WPL,然后将左右子树的WPL加上左右子树的权值之和,即可得到整棵树的WPL。
```python
class Node:
def __init__(self, value, left=None, right=None, weight=0):
self.value = value
self.left = left
self.right = right
self.weight = weight
def wpl(root):
if not root:
return 0
if not root.left and not root.right:
return root.weight
left_wpl = wpl(root.left)
right_wpl = wpl(root.right)
return left_wpl + right_wpl + root.weight
```
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)