实验内容:能够使用创建二叉树,并使用先序、中序、后序、层序的方法遍历二叉树中所有结点,输出二叉树的高度,统计二叉树叶子结点的个数。写代码
时间: 2024-12-20 13:29:39 浏览: 11
实验内容涉及到编程中常见的数据结构——二叉树的操作。首先,你需要了解二叉树的基本构建,通常通过递归或迭代的方式来创建节点。每个节点包含两个指针,指向左孩子和右孩子。
下面是使用Python语言创建基本二叉树并遍历的示例:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def create_tree(values): # 创建二叉树函数,传入一个值列表
if not values:
return None
mid = len(values) // 2
root = TreeNode(values[mid])
root.left = create_tree(values[:mid]) # 递归左子树
root.right = create_tree(values[mid+1:]) # 递归右子树
return root
# 遍历方法:
def pre_order_traversal(node):
if node is not None:
print(node.val)
pre_order_traversal(node.left)
pre_order_traversal(node.right)
def in_order_traversal(node):
if node is not None:
in_order_traversal(node.left)
print(node.val)
in_order_traversal(node.right)
def post_order_traversal(node):
if node is not None:
post_order_traversal(node.left)
post_order_traversal(node.right)
print(node.val)
def level_order_traversal(node):
if node is not None:
queue = [node]
while queue:
node = queue.pop(0)
print(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
# 计算高度和叶节点数:
def height(node):
if node is None:
return 0
else:
left_height = height(node.left)
right_height = height(node.right)
return max(left_height, right_height) + 1
def count_leaves(node):
if node is None:
return 0
elif node.left is None and node.right is None:
return 1
else:
return count_leaves(node.left) + count_leaves(node.right)
```
阅读全文