用Python解决:假设二叉树采用二叉链存储结构存储,设计一个算法求该树中总的结点数。加注释
时间: 2024-03-21 13:39:29 浏览: 30
设二叉树采用链式存储结构,试设计一个算法计算一颗给定二叉树叶子节点的数目
5星 · 资源好评率100%
当二叉树采用二叉链存储结构时,每个结点包含了指向左孩子和右孩子的指针。因此,我们可以通过遍历二叉树并计数来求出该树中总的结点数。
以下是用Python实现的算法:
```python
class Node:
def __init__(self, val=None, left=None, right=None):
self.val = val
self.left = left
self.right = right
def count_nodes(root: Node) -> int:
if not root: # 如果根节点为空,返回0
return 0
left_count = count_nodes(root.left) # 递归计算左子树结点数
right_count = count_nodes(root.right) # 递归计算右子树结点数
return left_count + right_count + 1 # 根节点加上左右子树结点数,即为总结点数
```
使用示例:
```python
# 构造一棵二叉树
root = Node(1, Node(2, Node(4), Node(5)), Node(3, Node(6), Node(7)))
# 求出结点数
node_count = count_nodes(root)
print(node_count) # 输出结果为 7
```
注:该算法的时间复杂度为O(n),其中n为二叉树中结点的个数。
阅读全文