数据结构以二叉链表作为二叉树的存储结构,编写以下算法:(1)统计二叉树的叶结点个数。
时间: 2024-11-23 15:13:34 浏览: 20
头歌数据结构二叉树的二叉链表存储及基本操作
5星 · 资源好评率100%
在数据结构中,二叉链表是一种常见的二叉树存储方式,每个节点通常包含两个指针,分别指向左孩子和右孩子。要统计二叉树的叶节点(即没有孩子的节点)个数,可以采用递归或迭代的方式来遍历整个二叉树。
这里提供一个使用递归的方法:
```python
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def count_leaves(node):
# 如果节点为空,则返回0
if node is None:
return 0
# 如果当前节点是叶子节点,返回1;否则,左右子树的叶节点之和
elif node.left is None and node.right is None:
return 1
else:
# 递归计算左子树和右子树的叶节点个数并相加
return count_leaves(node.left) + count_leaves(node.right)
# 测试代码
root = Node(1, Node(2), Node(3, Node(4), Node(5)))
print(count_leaves(root)) # 输出:3(因为有3个叶节点:2, 4, 5)
```
阅读全文