用数据结构算法:以二叉链表作为二叉树的存储结构,编写算法实现统计二叉树的叶结点个数
时间: 2024-11-15 15:06:49 浏览: 3
在使用二叉链表作为二叉树的存储结构时,统计叶节点个数的算法通常采用递归的方式。以下是Python的一个示例:
```python
class Node:
def __init__(self, value=None, left=None, right=None):
self.value = value
self.left = left
self.right = right
def count_leaves(root):
if root is None:
return 0 # 如果节点为空,返回0,表示没有叶节点
elif root.left is None and root.right is None: # 如果节点既是左孩子又是右孩子,说明它是叶子节点,计数加1
return 1
else:
# 递归地对左右子树进行计数,然后相加得到当前节点的叶节点数目
return count_leaves(root.left) + count_leaves(root.right)
# 示例
# 构建一棵简单的二叉树
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
# 现在可以调用count_leaves函数来获取叶节点的数量
leaf_count = count_leaves(root)
print("叶节点个数:", leaf_count)
```
阅读全文