编写一个函数,用递归算法求二叉树的结点总数,函数原型为:int node(BinTree T)
时间: 2024-10-24 21:09:54 浏览: 12
题目:编写递归算法,将二叉树中所有结点的左右子树相互交换 - READ.doc
5星 · 资源好评率100%
递归算法是一种通过将复杂问题分解成更小部分并逐一解决它们的方式来解决问题的方法。对于计算二叉树的节点总数,你可以创建一个名为`node`的函数,它接受一个二叉树的引用作为输入参数`T`。下面是一个基本的Python函数实现:
```python
class BinTree:
def __init__(self, value=None, left=None, right=None):
self.value = value
self.left = left
self.right = right
def node_count(T):
# 基本情况:如果树为空,返回0
if not T:
return 0
# 递归情况:节点数等于左子树节点数加上右子树节点数加1(根节点)
else:
return 1 + node_count(T.left) + node_count(T.right)
```
这个函数首先检查传入的二叉树是否为空,如果是,则返回0表示没有节点。如果不是空树,它会返回1(根节点)加上左子树和右子树的节点总数。这是典型的递归结构,每次调用都会缩小问题规模,直到遇到基本情况。
阅读全文