1、必做题 (1) 建立一棵二叉树。对此树进行前序遍历、中序遍历及后序遍历,输出遍历序列。 (2) 在第一题基础上,求二叉树中叶结点的个数。 (3) 在第一题基础上,求二叉树中结点总数。 (4) 在第一题基础上,求二叉树的深度。
时间: 2023-06-26 08:10:14 浏览: 152
好的,下面是代码实现和注释解释:
```python
# 定义二叉树的结点类
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
# 建立一棵二叉树
def build_tree():
root = TreeNode(1) # 根结点
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)
return root
# 前序遍历二叉树
def preorder_traversal(root):
if not root:
return
print(root.val, end=' ')
preorder_traversal(root.left)
preorder_traversal(root.right)
# 中序遍历二叉树
def inorder_traversal(root):
if not root:
return
inorder_traversal(root.left)
print(root.val, end=' ')
inorder_traversal(root.right)
# 后序遍历二叉树
def postorder_traversal(root):
if not root:
return
postorder_traversal(root.left)
postorder_traversal(root.right)
print(root.val, end=' ')
# 求二叉树中叶结点的个数
def count_leaves(root):
if not root:
return 0
if not root.left and not root.right:
return 1
return count_leaves(root.left) + count_leaves(root.right)
# 求二叉树中结点总数
def count_nodes(root):
if not root:
return 0
return count_nodes(root.left) + count_nodes(root.right) + 1
# 求二叉树的深度
def max_depth(root):
if not root:
return 0
left_depth = max_depth(root.left)
right_depth = max_depth(root.right)
return max(left_depth, right_depth) + 1
# 测试
root = build_tree()
print('前序遍历:', end='')
preorder_traversal(root)
print()
print('中序遍历:', end='')
inorder_traversal(root)
print()
print('后序遍历:', end='')
postorder_traversal(root)
print()
print('叶结点个数:', count_leaves(root))
print('结点总数:', count_nodes(root))
print('深度:', max_depth(root))
```
输出结果为:
```
前序遍历:1 2 4 5 3 6 7
中序遍历:4 2 5 1 6 3 7
后序遍历:4 5 2 6 7 3 1
叶结点个数: 4
结点总数: 7
深度: 3
```
阅读全文