python求二叉树中求叶子结点总数算法(提示:可在某种遍历过程中统计遍历的结点数),并在主函数中补充相应的调用验证正确性。用二叉树类存储
时间: 2024-05-04 09:16:15 浏览: 10
可以通过递归遍历二叉树来求叶子结点总数。如果遇到空结点则返回0,如果当前结点的左右子节点都为NULL,则代表这是一个叶子结点,返回1。如果左右子树都不为NULL,则递归计算左右子树中叶子结点的个数,然后相加即可。
以下是示例代码:
```
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class BinaryTree:
def __init__(self, root):
self.root = root
def get_leaf_count(self):
return self._get_leaf_count(self.root)
def _get_leaf_count(self, node):
if node is None:
return 0
if node.left is None and node.right is None:
return 1
return self._get_leaf_count(node.left) + self._get_leaf_count(node.right)
# 测试代码
if __name__ == '__main__':
# 创建二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
tree = BinaryTree(root)
# 求叶子结点总数
leaf_count = tree.get_leaf_count()
print('叶子结点总数为:', leaf_count)
```
输出结果为:
```
叶子结点总数为: 3
```
请注意,这里使用了递归方式来遍历二叉树,考虑到可能会有大的二叉树,建议选择非递归方式,例如使用栈或者队列来保存待处理结点。