Bài 8: Thực hành cây tìm kiếm nhị phân - Chuyên đề Tin học 12 Kết nối tri thức
Câu 1
Trả lời câu hỏi Khởi động trang 37 Chuyên đề Tin học 12 Kết nối tri thức
Trong Bài 7, cây tìm tìm kiếm nhị phân được cài đặt bằng mảng một chiều và mỗi nút của cây có khoá là một thuộc tính. Trong thực tế, một đối tượng có thể có nhiều thuộc tính. Ví dụ, với bài toán quản lí các món trong thực đơn, mỗi món có hai thuộc tính là tên và giá tiền. Trong trường hợp này, cây tìm kiếm nhị phân biểu diễn danh sách các món được cài đặt bằng mảng như thế nào và làm thế nào để mỗi nút của cây chứa hai thuộc tính là tên và giá tiền?
Lời giải chi tiết:
Trong trường hợp mỗi nút của cây tìm kiếm nhị phân cần chứa nhiều hơn một thuộc tính, có thể sử dụng một lớp đại diện cho nút của cây, và mỗi đối tượng của lớp này sẽ chứa các thuộc tính tương ứng với mỗi nút.
Dưới đây là một cách để triển khai sử dụng lớp để đại diện cho nút của cây tìm kiếm nhị phân trong trường hợp mỗi nút chứa hai thuộc tính là tên và giá tiền của món ăn:
class MenuItem:
def __init__(self, name, price):
self.name = name
self.price = price
self.left = None
self.right = None
def insert(root, name, price):
if root is None:
return MenuItem(name, price)
if name < root.name:
root.left = insert(root.left, name, price)
elif name > root.name:
root.right = insert(root.right, name, price)
return root
def search(root, name):
if root is None or root.name == name:
return root
if name < root.name:
return search(root.left, name)
return search(root.right, name)
# Ví dụ minh họa
root = None
root = insert(root, "Pho", 35)
root = insert(root, "Banh Mi", 25)
root = insert(root, "Bun Cha", 40)
# Tìm kiếm một món trong cây
search_result = search(root, "Pho")
if search_result:
print(f"Tên món: {search_result.name}, Giá: {search_result.price}")
else:
print("Không tìm thấy món.")
search_result = search(root, "Banh Xeo")
if search_result:
print(f"Tên món: {search_result.name}, Giá: {search_result.price}")
else:
print("Không tìm thấy món.")
Chú thích trong mã này:
- Lớp MenuItem đại diện cho nút của cây, mỗi đối tượng của lớp này chứa hai thuộc tính là tên và giá tiền của món ăn, cũng như hai con trỏ left và right để tham chiếu đến các nút con bên trái và bên phải.
- Hàm insert được sử dụng để chèn một món ăn mới vào cây tìm kiếm nhị phân.
- Hàm search được sử dụng để tìm kiếm một món ăn trong cây tìm kiếm nhị phân.
Luyện tập Câu 1
Trả lời câu hỏi Luyện tập 1 trang 40 Chuyên đề Tin học 12 Kết nối tri thức
Vẽ cây tìm kiếm nhị phân ứng với tệp menu.inp trong nhiệm vụ thực hành, lưu ý mỗi nút gồm hai thuộc tính name và price.
Lời giải chi tiết:
Để vẽ cây tìm kiếm nhị phân ứng với dữ liệu từ tệp menu.inp, trước tiên chúng ta cần đọc dữ liệu từ tệp và chèn mỗi mục vào cây. Sau đó, chúng ta có thể sử dụng các công cụ vẽ đồ thị để hiển thị cây.
Dưới đây là mã Python mẫu để thực hiện điều này:
import matplotlib.pyplot as plt
from queue import Queue
class MenuItem:
def __init__(self, name, price):
self.name = name
self.price = price
self.left = None
self.right = None
def insert(root, name, price):
if root is None:
return MenuItem(name, price)
if name < root.name:
root.left = insert(root.left, name, price)
elif name > root.name:
root.right = insert(root.right, name, price)
return root
def build_binary_search_tree(filename):
root = None
with open(filename, 'r') as file:
for line in file:
name, price = line.strip().split(', ')
price = int(price)
root = insert(root, name, price)
return root
def plot_binary_search_tree(root):
if root is None:
return
node_queue = Queue()
node_queue.put(root)
while not node_queue.empty():
current_level_size = node_queue.qsize()
for _ in range(current_level_size):
node = node_queue.get()
if node.left:
node_queue.put(node.left)
plt.plot([node.val, node.left.val], [node.price, node.left.price], color='black')
if node.right:
node_queue.put(node.right)
plt.plot([node.val, node.right.val], [node.price, node.right.price], color='black')
plt.scatter(node.val, node.price, color='red')
plt.text(node.val, node.price, node.name, fontsize=9, ha='center')
plt.xlabel('Name')
plt.ylabel('Price')
plt.title('Binary Search Tree Representation of Menu')
plt.grid()
plt.show()
# Tạo cây tìm kiếm nhị phân từ tệp menu.inp
root = build_binary_search_tree('menu.inp')
# Vẽ cây tìm kiếm nhị phân
plot_binary_search_tree(root)
Chú thích trong chương trình này:
- Chúng ta định nghĩa lớp MenuItem để đại diện cho các nút trong cây. Mỗi nút có hai thuộc tính là name và price.
- Hàm insert được sử dụng để chèn một mục vào cây tìm kiếm nhị phân.
- Hàm build_binary_search_tree đọc dữ liệu từ tệp menu.inp và xây dựng cây tìm kiếm nhị phân từ các mục đó.
- Hàm plot_binary_search_tree được sử dụng để vẽ cây tìm kiếm nhị phân bằng cách sử dụng thư viện matplotlib.
Luyện tập Câu 2
Trả lời câu hỏi Luyện tập 2 trang 40 Chuyên đề Tin học 12 Kết nối tri thức
Trả lời câu hỏi Luyện tập 2 trang 40 Chuyên đề Tin học 12 Kết nối tri thức
Lời giải chi tiết:
Quá trình tra cứu giá tiền của món "Bún chả" trên cây tìm kiếm nhị phân đã vẽ có thể được mô tả như sau:
1. Bắt đầu từ nút gốc của cây.
2. So sánh tên của nút gốc với "Bún chả":
- Nếu tên của nút gốc là "Bún chả", chúng ta đã tìm thấy món "Bún chả". Lúc này, chúng ta lấy giá tiền của món "Bún chả" từ nút này.
- Nếu tên của nút gốc lớn hơn "Bún chả", chúng ta di chuyển sang cây con bên trái của nút gốc và tiếp tục tìm kiếm.
- Nếu tên của nút gốc nhỏ hơn "Bún chả", chúng ta di chuyển sang cây con bên phải của nút gốc và tiếp tục tìm kiếm.
3. Quá trình này lặp lại cho đến khi chúng ta tìm thấy món "Bún chả" hoặc điều kiện dừng được kích hoạt (không có nút nào chứa tên "Bún chả").
Nếu món "Bún chả" được tìm thấy, chúng ta sẽ biết được giá tiền của món này. Nếu không, chúng ta sẽ biết rằng món "Bún chả" không có trong danh sách thực đơn và không có thông tin về giá tiền.
Vận dụng Câu 1
Trả lời câu hỏi Vận dụng 1 trang 40 Chuyên đề Tin học 12 Kết nối tri thức
Sử dụng cây tìm kiếm nhị phân để viết ứng dụng quản lí tài khoản ngân hàng. Mỗi một tài khoản gồm mã tài khoản (duy nhất) và số dư tài khoản. Ứng dụng cho phép thêm tài khoản, sửa số dư tài khoản, tìm kiếm tài khoản theo mã tài khoản.
Lời giải chi tiết:
Hướng dẫn gợi ý về cách sử dụng cây tìm kiếm nhị phân để viết ứng dụng quản lí tài khoản ngân hàng thông qua một chương trình mẫu sau:
class Account:
def __init__(self, account_id, balance):
self.account_id = account_id
self.balance = balance
self.left = None
self.right = None
class BankAccountManager:
def __init__(self):
self.root = None
def insert(self, root, account_id, balance):
if root is None:
return Account(account_id, balance)
if account_id < root.account_id:
root.left = self.insert(root.left, account_id, balance)
elif account_id > root.account_id:
root.right = self.insert(root.right, account_id, balance)
return root
def add_account(self, account_id, balance):
self.root = self.insert(self.root, account_id, balance)
def search(self, root, account_id):
if root is None or root.account_id == account_id:
return root
if account_id < root.account_id:
return self.search(root.left, account_id)
return self.search(root.right, account_id)
def find_account(self, account_id):
return self.search(self.root, account_id)
def update_balance(self, account_id, new_balance):
account = self.find_account(account_id)
if account:
account.balance = new_balance
else:
print("Account not found.")
# Sử dụng ứng dụng
bank_manager = BankAccountManager()
# Thêm tài khoản
bank_manager.add_account(1001, 50000)
bank_manager.add_account(1002, 100000)
bank_manager.add_account(1003, 75000)
# Tìm kiếm tài khoản
account = bank_manager.find_account(1002)
if account:
print(f"Account found - Account ID: {account.account_id}, Balance: {account.balance}")
else:
print("Account not found.")
# Cập nhật số dư tài khoản
bank_manager.update_balance(1001, 60000)
# Kiểm tra lại số dư sau khi cập nhật
account = bank_manager.find_account(1001)
if account:
print(f"Updated balance - Account ID: {account.account_id}, Balance: {account.balance}")
else:
print("Account not found.")
Chú thích trong chương trình này:
- Lớp Account được sử dụng để đại diện cho mỗi tài khoản, với hai thuộc tính là account_id (mã tài khoản) và balance (số dư tài khoản).
- Lớp BankAccountManager chứa các phương thức để thêm tài khoản, tìm kiếm tài khoản và cập nhật số dư tài khoản. Mỗi tài khoản được lưu trữ trong một cây tìm kiếm nhị phân, với account_id làm khóa.
Vận dụng Câu 2
Trả lời câu hỏi Vận dụng 2 trang 40 Chuyên đề Tin học 12 Kết nối tri thức
Sử dụng cây tìm kiếm nhị phân để viết chương trình quản lí danh sách học sinh của một trường trung học phổ thông. Mỗi một học sinh gồm các thông tin: mã học sinh (duy nhất), họ tên, ngày sinh. Chương trình cho phép thêm một học sinh vào danh sách với các trường thông tin kể trên, tìm kiếm học sinh theo mã và sửa đổi họ tên và ngày sinh ứng với một mã học sinh.
Lời giải chi tiết:
Gợi ý chương trình mẫu về cách sử dụng cây tìm kiếm nhị phân để quản lí danh sách học sinh của một trường trung học phổ thông:
class Student:
def __init__(self, student_id, name, date_of_birth):
self.student_id = student_id
self.name = name
self.date_of_birth = date_of_birth
self.left = None
self.right = None
class StudentManager:
def __init__(self):
self.root = None
def insert(self, root, student_id, name, date_of_birth):
if root is None:
return Student(student_id, name, date_of_birth)
if student_id < root.student_id:
root.left = self.insert(root.left, student_id, name, date_of_birth)
elif student_id > root.student_id:
root.right = self.insert(root.right, student_id, name, date_of_birth)
return root
def add_student(self, student_id, name, date_of_birth):
self.root = self.insert(self.root, student_id, name, date_of_birth)
def search(self, root, student_id):
if root is None or root.student_id == student_id:
return root
if student_id < root.student_id:
return self.search(root.left, student_id)
return self.search(root.right, student_id)
def find_student(self, student_id):
return self.search(self.root, student_id)
def update_student(self, student_id, new_name, new_date_of_birth):
student = self.find_student(student_id)
if student:
student.name = new_name
student.date_of_birth = new_date_of_birth
else:
print("Student not found.")
# Sử dụng chương trình
student_manager = StudentManager()
# Thêm học sinh
student_manager.add_student(1001, "Nguyen Van A", "2005-03-15")
student_manager.add_student(1002, "Tran Thi B", "2004-08-22")
student_manager.add_student(1003, "Le Van C", "2006-01-10")
# Tìm kiếm học sinh
student = student_manager.find_student(1002)
if student:
print(f"Student found - Student ID: {student.student_id}, Name: {student.name}, Date of Birth: {student.date_of_birth}")
else:
print("Student not found.")
# Cập nhật thông tin học sinh
student_manager.update_student(1001, "Pham Thi D", "2005-05-20")
# Kiểm tra lại thông tin sau khi cập nhật
student = student_manager.find_student(1001)
if student:
print(f"Updated student - Student ID: {student.student_id}, Name: {student.name}, Date of Birth: {student.date_of_birth}")
else:
print("Student not found.")
Lưu ý trong mã chương trình này:
- Lớp Student đại diện cho mỗi học sinh, với các thuộc tính là student_id (mã học sinh), name (họ tên) và date_of_birth (ngày sinh).
- Lớp StudentManager chứa các phương thức để thêm học sinh vào danh sách, tìm kiếm học sinh theo mã và cập nhật thông tin học sinh. Mỗi học sinh được lưu trữ trong một cây tìm kiếm nhị phân, với student_id làm khóa.