以二叉链表作为二叉树的存储结构,编写递归算法,统计二叉树度为2的结点个数
时间: 2024-12-05 16:07:55 浏览: 23
头歌数据结构二叉树的二叉链表存储及基本操作
5星 · 资源好评率100%
二叉链表表示的二叉树中,每个节点除了保存自身的信息外,还包含了两个指向其左右子节点的指针。要计算度为2(即有两个子节点)的节点个数,我们可以使用递归的方式遍历整个二叉树。下面是Python的一种实现方式:
```python
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def count_nodes_of_degree_two(root):
# 基本情况:如果节点为空,返回0
if root is None:
return 0
# 对左子树和右子树递归地计数
left_count = count_nodes_of_degree_two(root.left)
right_count = count_nodes_of_degree_two(root.right)
# 如果节点有两个子节点,则返回1,否则返回0
if root.left and root.right:
return left_count + right_count + 1
else:
return left_count + right_count
# 使用示例
root = Node(1) # 构造任意二叉树
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
print(count_nodes_of_degree_two(root)) # 输出: 2,因为节点2和4各有2个子节点
```
这个函数会返回整个二叉树中度为2的节点总数。
阅读全文