利用二叉树的递归遍历算法,编写函数,实现二叉树的结点数、叶子结点数、树的高度、以及每层结点数的计算。 算法设计思路:
时间: 2024-03-23 10:39:54 浏览: 11
好的,下面是二叉树的递归遍历算法实现:
```python
# 定义二叉树节点类
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
# 定义二叉树类
class BinaryTree:
def __init__(self, root):
self.root = TreeNode(root)
# 计算二叉树结点数
def count_nodes(self, node):
if node is None:
return 0
else:
return 1 + self.count_nodes(node.left) + self.count_nodes(node.right)
# 计算二叉树叶子结点数
def count_leaves(self, node):
if node is None:
return 0
elif node.left is None and node.right is None:
return 1
else:
return self.count_leaves(node.left) + self.count_leaves(node.right)
# 计算二叉树高度
def get_height(self, node):
if node is None:
return 0
else:
left_height = self.get_height(node.left)
right_height = self.get_height(node.right)
return max(left_height, right_height) + 1
# 计算每层结点数
def level_count(self, node, level, result):
if node is None:
return
if level == 1:
result[0] += 1
elif level > 1:
self.level_count(node.left, level-1, result)
self.level_count(node.right, level-1, result)
def get_level_count(self):
total_levels = self.get_height(self.root)
result = [0] * total_levels
for level in range(1, total_levels+1):
self.level_count(self.root, level, result)
return result
```
以上是用 Python 实现的二叉树的递归遍历算法,实现了二叉树结点数、叶子结点数、树的高度、以及每层结点数的计算。