已知二叉树采用二叉链表存储结构,编写算法统计二叉树中的叶子结点树
时间: 2024-09-07 18:02:44 浏览: 47
在二叉链表存储结构中,二叉树的每个节点由一个数据域和两个分别指向左右子树的指针域组成。叶子节点是指没有子节点的节点。统计二叉树中叶子节点的数量可以通过递归遍历的方式实现。下面是一个统计叶子节点数量的算法示例:
```python
class TreeNode:
def __init__(self, value=0, left=None, right=None):
self.val = value
self.left = left
self.right = right
def countLeaves(node):
# 如果当前节点为空,返回叶子节点数为0
if node is None:
return 0
# 如果当前节点是叶子节点,返回叶子节点数为1
if node.left is None and node.right is None:
return 1
# 否则,递归计算左右子树的叶子节点数量,并返回它们的和
return countLeaves(node.left) + countLeaves(node.right)
# 示例使用:
# 创建一个二叉树的节点
# 1
# / \
# 2 3
# / / \
# 4 5 6
# /
# 7
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.right.left = TreeNode(5)
root.right.right = TreeNode(6)
root.left.left.left = TreeNode(7)
# 统计叶子节点数量
leaf_count = countLeaves(root)
print("叶子节点的数量是:", leaf_count)
```
在这个示例中,`countLeaves` 函数递归地遍历二叉树的每个节点,并统计叶子节点的数量。如果当前节点为空,则返回0,表示没有找到叶子节点;如果当前节点没有子节点,则返回1,表示找到了一个叶子节点;如果当前节点有子节点,则递归地对其左右子树调用 `countLeaves` 函数,并将结果相加,最后返回叶子节点的总数。
阅读全文