引言
树是数据结构中一种非常重要的结构，广泛应用于计算机科学、数据库、网络等多个领域。掌握树的相关知识对于学习计算机科学的学生来说至关重要。本文将介绍一些实战练习题，帮助你更好地理解和应用树这一数据结构。
实战练习题
1. 二叉树的遍历
题目描述： 实现二叉树的先序、中序和后序遍历。
代码示例：
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def preorder_traversal(root):
if root is None:
return []
return [root.val] + preorder_traversal(root.left) + preorder_traversal(root.right)
def inorder_traversal(root):
if root is None:
return []
return inorder_traversal(root.left) + [root.val] + inorder_traversal(root.right)
def postorder_traversal(root):
if root is None:
return []
return postorder_traversal(root.left) + postorder_traversal(root.right) + [root.val]
2. 二叉搜索树（BST）的插入和删除
题目描述： 实现二叉搜索树的插入和删除操作。
代码示例：
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def insert_into_bst(root, val):
if root is None:
return TreeNode(val)
if val < root.val:
root.left = insert_into_bst(root.left, val)
else:
root.right = insert_into_bst(root.right, val)
return root
def delete_from_bst(root, val):
if root is None:
return None
if val < root.val:
root.left = delete_from_bst(root.left, val)
elif val > root.val:
root.right = delete_from_bst(root.right, val)
else:
if root.left is None:
return root.right
elif root.right is None:
return root.left
else:
min_larger_node = find_min_value(root.right)
root.val = min_larger_node.val
root.right = delete_from_bst(root.right, min_larger_node.val)
return root
def find_min_value(root):
while root.left is not None:
root = root.left
return root
3. 平衡二叉树（AVL树）
题目描述： 实现平衡二叉树（AVL树）的插入和删除操作。
代码示例：
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
self.height = 1
def get_height(root):
if root is None:
return 0
return root.height
def update_height(root):
root.height = max(get_height(root.left), get_height(root.right)) + 1
def get_balance(root):
if root is None:
return 0
return get_height(root.left) - get_height(root.right)
def rotate_right(y):
x = y.left
T2 = x.right
x.right = y
y.left = T2
update_height(y)
update_height(x)
return x
def rotate_left(x):
y = x.right
T2 = y.left
y.left = x
x.right = T2
update_height(x)
update_height(y)
return y
def insert_into_avl(root, val):
if root is None:
return TreeNode(val)
if val < root.val:
root.left = insert_into_avl(root.left, val)
else:
root.right = insert_into_avl(root.right, val)
update_height(root)
balance = get_balance(root)
if balance > 1 and val < root.left.val:
return rotate_right(root)
if balance < -1 and val > root.right.val:
return rotate_left(root)
if balance > 1 and val > root.left.val:
root.left = rotate_left(root.left)
return rotate_right(root)
if balance < -1 and val < root.right.val:
root.right = rotate_right(root.right)
return rotate_left(root)
return root
def delete_from_avl(root, val):
if root is None:
return root
if val < root.val:
root.left = delete_from_avl(root.left, val)
elif val > root.val:
root.right = delete_from_avl(root.right, val)
else:
if root.left is None:
temp = root.right
root = None
return temp
elif root.right is None:
temp = root.left
root = None
return temp
temp = get_min_value_node(root.right)
root.val = temp.val
root.right = delete_from_avl(root.right, temp.val)
if root is None:
return root
update_height(root)
balance = get_balance(root)
if balance > 1 and get_balance(root.left) >= 0:
return rotate_right(root)
if balance > 1 and get_balance(root.left) < 0:
root.left = rotate_left(root.left)
return rotate_right(root)
if balance < -1 and get_balance(root.right) <= 0:
return rotate_left(root)
if balance < -1 and get_balance(root.right) > 0:
root.right = rotate_right(root.right)
return rotate_left(root)
return root
def get_min_value_node(node):
current = node
while current.left is not None:
current = current.left
return current
def get_max_value_node(node):
current = node
while current.right is not None:
current = current.right
return current
4. 红黑树
题目描述： 实现红黑树的插入和删除操作。
代码示例：
class Node:
def __init__(self, data, color):
self.data = data
self.color = color
self.parent = None
self.left = None
self.right = None
def left_rotate(node):
right_child = node.right
node.right = right_child.left
if right_child.left:
right_child.left.parent = node
right_child.parent = node.parent
if not node.parent:
root = right_child
elif node == node.parent.left:
node.parent.left = right_child
else:
node.parent.right = right_child
right_child.left = node
node.parent = right_child
return root
def right_rotate(node):
left_child = node.left
node.left = left_child.right
if left_child.right:
left_child.right.parent = node
left_child.parent = node.parent
if not node.parent:
root = left_child
elif node == node.parent.right:
node.parent.right = left_child
else:
node.parent.left = left_child
left_child.right = node
node.parent = left_child
return root
def insert_into_rbt(root, data):
node = Node(data, "RED")
parent = None
current = root
while current:
parent = current
if node.data < current.data:
current = current.left
else:
current = current.right
node.parent = parent
if parent is None:
root = node
elif node.data < parent.data:
parent.left = node
else:
parent.right = node
node.color = "BLACK"
fix_violation(root, node)
def fix_violation(root, node):
while node != root and node.parent.color == "RED":
if node.parent == node.parent.parent.left:
uncle = node.parent.parent.right
if uncle and uncle.color == "RED":
node.parent.color = "BLACK"
uncle.color = "BLACK"
node.parent.parent.color = "RED"
node = node.parent.parent
else:
if node == node.parent.right:
node = node.parent
left_rotate(node)
node.parent.color = "BLACK"
node.parent.parent.color = "RED"
right_rotate(node.parent.parent)
else:
uncle = node.parent.parent.left
if uncle and uncle.color == "RED":
node.parent.color = "BLACK"
uncle.color = "BLACK"
node.parent.parent.color = "RED"
node = node.parent.parent
else:
if node == node.parent.left:
node = node.parent
right_rotate(node)
node.parent.color = "BLACK"
node.parent.parent.color = "RED"
left_rotate(node.parent.parent)
root.color = "BLACK"
def delete_from_rbt(root, data):
node = get_node(root, data)
if not node:
return
if node.left and node.right:
successor = get_successor(node)
node.data = successor.data
node = successor
original_parent_color = node.parent.color
if not node.left:
temp = node.right
if not node.parent:
root = temp
elif node == node.parent.left:
node.parent.left = temp
else:
node.parent.right = temp
if not temp:
return
temp.parent = node.parent
if original_parent_color == "BLACK":
fix_violation(root, temp)
return
if not node.right:
temp = node.left
if not node.parent:
root = temp
elif node == node.parent.left:
node.parent.left = temp
else:
node.parent.right = temp
if not temp:
return
temp.parent = node.parent
if original_parent_color == "BLACK":
fix_violation(root, temp)
return
temp = node.right
while temp.left:
temp = temp.left
node.data = temp.data
if temp.right:
node = temp.right
original_parent_color = node.parent.color
else:
node = temp
original_parent_color = "BLACK"
if not node.left and not node.right:
if original_parent_color == "BLACK":
if node == node.parent.left:
node.parent.left = None
else:
node.parent.right = None
fix_violation(root, node.parent)
return
if original_parent_color == "BLACK":
if node == node.parent.left:
node.parent.left = None
else:
node.parent.right = None
fix_violation(root, node.parent)
return
def get_node(root, data):
current = root
while current:
if current.data == data:
return current
elif data < current.data:
current = current.left
else:
current = current.right
return None
def get_successor(node):
if node.right:
return get_min_value_node(node.right)
current = node.parent
while current and current.left == node:
node = current
current = current.parent
return current
5. 树的深度优先搜索（DFS）和广度优先搜索（BFS）
题目描述： 实现树的深度优先搜索（DFS）和广度优先搜索（BFS）。
代码示例：
from collections import deque
def dfs(root):
if root is None:
return
stack = [root]
while stack:
node = stack.pop()
print(node.val, end=" ")
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
def bfs(root):
if root is None:
return
queue = deque([root])
while queue:
node = queue.popleft()
print(node.val, end=" ")
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
总结
以上实战练习题涵盖了树的各种操作，包括二叉树的遍历、二叉搜索树的插入和删除、平衡二叉树（AVL树）和红黑树的插入和删除、以及树的深度优先搜索（DFS）和广度优先搜索（BFS）。通过这些练习题，你可以更好地理解和应用树这一数据结构。在实际编程过程中，根据具体需求和场景选择合适的树结构非常重要。希望这些练习题对你有所帮助！