Viết hàm chèn khoá v vào cây tìm kiếm nhị phân T sử dụng kĩ thuật đệ quy
Viết hàm chèn khoá v vào cây tìm kiếm nhị phân T sử dụng kĩ thuật đệ quy.
Giải Chuyên đề Tin 12 Bài 7: Cây tìm kiếm nhị phân - Kết nối tri thức
Vận dụng 2 trang 36 Chuyên đề Tin học 12: Viết hàm chèn khoá v vào cây tìm kiếm nhị phân T sử dụng kĩ thuật đệ quy.
Lời giải:
Để viết hàm chèn khoá v vào cây tìm kiếm nhị phân T sử dụng kỹ thuật đệ quy, chương trình sẽ cần một phương thức đệ quy để thực hiện việc chèn. Dưới đây là cách triển khai mẫu:
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def insert_recursive(root, key):
# Nếu cây là rỗng, tạo một nút mới và trả về
if root is None:
return Node(key)
# Nếu khoá nhỏ hơn khoá của nút hiện tại, chèn vào cây con bên trái
if key < root.key:
root.left = insert_recursive(root.left, key)
# Nếu khoá lớn hơn hoặc bằng khoá của nút hiện tại, chèn vào cây con bên phải
else:
root.right = insert_recursive(root.right, key)
return root
# Hàm chèn khoá v vào cây tìm kiếm nhị phân T sử dụng kỹ thuật đệ quy
def insert_into_binary_search_tree(T, v):
T = insert_recursive(T, v)
return T
# Ví dụ minh họa
if __name__ == "__main__":
# Tạo một cây tìm kiếm nhị phân
root = Node(5)
root.left = Node(3)
root.right = Node(8)
root.left.left = Node(2)
root.left.right = Node(4)
root.right.left = Node(6)
root.right.right = Node(9)
# In cây tìm kiếm nhị phân trước khi chèn
print("Cây tìm kiếm nhị phân trước khi chèn:")
def inorder_traversal(node):
if node:
inorder_traversal(node.left)
print(node.key, end=" ")
inorder_traversal(node.right)
inorder_traversal(root)
print()
# Chèn khoá 7 vào cây tìm kiếm nhị phân
insert_into_binary_search_tree(root, 7)
# In cây tìm kiếm nhị phân sau khi chèn
print("Cây tìm kiếm nhị phân sau khi chèn:")
inorder_traversal(root)
* Chú thích:
- Node là lớp biểu diễn một nút trong cây tìm kiếm nhị phân.
- insert_recursive là hàm đệ quy để chèn một khoá mới vào cây tìm kiếm nhị phân.
- insert_into_binary_search_tree là hàm chèn khoá v vào cây tìm k iếm nhị phân T sử dụng kỹ thuật đệ quy.
Lời giải bài tập Chuyên đề Tin 12 Bài 7: Cây tìm kiếm nhị phân hay, ngắn gọn khác: