以二叉链表作为二叉树的存储结构,编写以下算法:(1)统计二叉树的叶结点个数。(2)用按层次顺序遍历二叉树的方法,统计树中具有度为1的结点数目。
时间: 2024-11-23 16:13:34 浏览: 50
头歌数据结构二叉树的二叉链表存储及基本操作
5星 · 资源好评率100%
使用二叉链表存储二叉树,我们可以利用递归或层次遍历来实现这两个算法。
### (1)统计二叉树的叶节点个数
```python
class Node:
def __init__(self, value=None, left=None, right=None):
self.value = value
self.left = left
self.right = right
def count_leaf_nodes(root):
if root is None:
return 0
else:
if root.left is None and root.right is None:
return 1
else:
return count_leaf_nodes(root.left) + count_leaf_nodes(root.right)
```
这个函数会递归地检查每个节点,如果节点的左右子节点都为空,则认为它是叶节点,并返回1;否则继续向下搜索。
### (2)统计树中具有度为1的结点数目
```python
def count_degree_one_nodes(root):
if root is None:
return 0
else:
# 度为1的节点要么只有左子节点,要么只有右子节点
# 因此,我们只需分别计算左子节点为非空的情况和右子节点为非空的情况
count_left = 1 if root.left else 0
count_right = 1 if root.right else 0
return count_left + count_right
```
这里假设根节点本身也被视作具有度1的节点。如果你想要排除这种情况,可以在函数开始时添加`return count_left + count_right - 1`。
阅读全文