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
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 lớp. Thông tin mỗi học sinh gồm mã (duy nhất), tên đầy đủ, ngày sinh. Chương trình cho phép thêm mới thông tin các học sinh, in danh sách sắp xếp theo mã từ nhỏ đến lớn và từ lớn đến nhỏ, tìm kiếm học sinh theo mã.
Giải Chuyên đề Tin 12 Bài 10: Thực hành tổng hợp với cây tìm kiếm nhị phân - Kết nối tri thức
Vận dụng 1 trang 48 Chuyên đề Tin học 12: 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 lớp. Thông tin mỗi học sinh gồm mã (duy nhất), tên đầy đủ, ngày sinh. Chương trình cho phép thêm mới thông tin các học sinh, in danh sách sắp xếp theo mã từ nhỏ đến lớn và từ lớn đến nhỏ, tìm kiếm học sinh theo mã.
Lời giải:
Bản phác thảo Python mẫu cho chương trình quản lí danh sách học sinh của một lớp sử dụng cây tìm kiếm nhị phân:
class Student:
def __init__(self, student_id, full_name, date_of_birth):
self.student_id = student_id
self.full_name = full_name
self.date_of_birth = date_of_birth
class TreeNode:
def __init__(self, student):
self.student = student
self.left = None
self.right = None
class StudentDatabase:
def __init__(self):
self.root = None
def insert(self, student):
self.root = self._insert_recursive(self.root, student)
def _insert_recursive(self, root, student):
if root is None:
return TreeNode(student)
if student.student_id < root.student.student_id:
root.left = self._insert_recursive(root.left, student)
elif student.student_id > root.student.student_id:
root.right = self._insert_recursive(root.right, student)
return root
def search(self, student_id):
return self._search_recursive(self.root, student_id)
def _search_recursive(self, root, student_id):
if root is None or root.student.student_id == student_id:
return root.student if root else None
if student_id < root.student.student_id:
return self._search_recursive(root.left, student_id)
else:
return self._search_recursive(root.right, student_id)
def display_students_in_order(self, root):
if root:
self.display_students_in_order(root.left)
print("ID:", root.student.student_id, "- Name:", root.student.full_name, "- Date of Birth:", root.student.date_of_birth)
self.display_students_in_order(root.right)
def display_students_in_reverse_order(self, root):
if root:
self.display_students_in_reverse_order(root.right)
print("ID:", root.student.student_id, "- Name:", root.student.full_name, "- Date of Birth:", root.student.date_of_birth)
self.display_students_in_reverse_order(root.left)
# Sử dụng
student_db = StudentDatabase()
# Thêm học sinh mới
student_db.insert(Student(101, "John Doe", "2005-01-15"))
student_db.insert(Student(102, "Alice Smith", "2004-08-20"))
student_db.insert(Student(103, "Bob Johnson", "2005-03-10"))
# In danh sách học sinh theo thứ tự mã từ nhỏ đến lớn
print("Students sorted by ID (ascending):")
student_db.display_students_in_order(student_db.root)
# In danh sách học sinh theo thứ tự mã từ lớn đến nhỏ
print("\nStudents sorted by ID (descending):")
student_db.display_students_in_reverse_order(student_db.root)
# Tìm kiếm học sinh theo mã
search_id = 102
found_student = student_db.search(search_id)
if found_student:
print("\nStudent found - ID:", found_student.student_id, "- Name:", found_student.full_name, "- Date of Birth:", found_student.date_of_birth)
else:
print("\nStudent with ID", search_id, "not found.")
Lời giải bài tập Chuyên đề Tin 12 Bài 10: Thực hành tổng hợp với cây tìm kiếm nhị phân hay, ngắn gọn khác: