KHỞI ĐỘNG

Trong Bài 9, chúng ta đã học thao tác duyệt cây. Với bài toán thực tế quản lí danh bạ điện thoại, làm thế nào để sử dụng các thao tác đó vào cây tìm kiếm nhị phân để thêm, tìm kiếm, hiển thị toàn bộ các liên hệ theo thứ tự sắp xếp của tên liên hệ trong danh bạ?

Giải chi tiết:

Để quản lý danh bạ điện thoại bằng cây tìm kiếm nhị phân (BST), chúng ta có thể sử dụng các thao tác cơ bản của BST như chèn, tìm kiếm và duyệt cây để thực hiện các chức năng như thêm liên hệ mới, tìm kiếm liên hệ theo tên và hiển thị toàn bộ danh sách liên hệ theo thứ tự sắp xếp của tên.

Dưới đây là một phác thảo về cách triển khai các chức năng này:

1. Chèn liên hệ mới:
   • Mỗi liên hệ được đại diện bởi một nút trong cây BST, với tên liên hệ là khóa.
   • Khi thêm một liên hệ mới, ta chèn nút tương ứng vào cây sao cho thứ tự tên liên hệ được duy trì.
2. Tìm kiếm liên hệ theo tên:
   • Sử dụng phương pháp tìm kiếm trong BST để tìm kiếm liên hệ theo tên.
   • Bắt đầu từ nút gốc, so sánh tên cần tìm với tên của nút hiện tại và di chuyển xuống theo hướng phù hợp để tiếp tục tìm kiếm.
3. Hiển thị toàn bộ danh sách liên hệ theo thứ tự sắp xếp của tên:
   • Duyệt cây theo thứ tự tăng dần (in-order traversal).
   • Khi duyệt, mỗi nút được duyệt sẽ tương ứng với một liên hệ và ta có thể hiển thị thông tin của liên hệ đó.

LUYỆN TẬP

Câu 1. Hãy vẽ cây tìm kiếm nhị phân ứng với:

a) Dữ liệu tệp contacts.inp ở trong phần thực hành.

b) Từ cây nhận được ở ý a, thêm liên hệ “Anh, Nguyễn Văn Tùng, 0982 000 134”.

Giải chi tiết:

Để vẽ cây tìm kiếm nhị phân ứng với dữ liệu từ tệp contacts.inp, chúng ta cần đọc dữ liệu từ tệp và thêm các liên hệ vào cây tương ứng. Sau đó, chúng ta có thể vẽ cây đó.

Dưới đây là một phác thảo Python cho cách thực hiện điều này:

class Contact:

def __init__(self, name, phone_number):

self.name = name

self.phone_number = phone_number

class TreeNode:

def __init__(self, contact):

self.contact = contact

self.left = None

self.right = None

class PhoneBook:

def __init__(self):

self.root = None

def insert(self, contact):

self.root = self._insert_recursive(self.root, contact)

def _insert_recursive(self, root, contact):

if root is None:

return TreeNode(contact)

if contact.name < root.contact.name:

root.left = self._insert_recursive(root.left, contact)

elif contact.name > root.contact.name:

root.right = self._insert_recursive(root.right, contact)

return root

def display_contacts(self):

self._in_order_traversal(self.root)

def _in_order_traversal(self, root):

if root:

self._in_order_traversal(root.left)

print("Name:", root.contact.name, "- Phone:", root.contact.phone_number)

self._in_order_traversal(root.right)

# Đọc dữ liệu từ tệp contacts.inp và thêm liên hệ vào danh bạ điện thoại

phone_book = PhoneBook()

with open("contacts.inp", "r") as file:

for line in file:

parts = line.strip().split(", ")

name = parts[0]

phone_number = parts[1]

phone_book.insert(Contact(name, phone_number))

# Hiển thị toàn bộ danh sách liên hệ trước khi thêm liên hệ mới

print("Contacts before adding new contact:")

phone_book.display_contacts()

# Thêm liên hệ mới

new_contact = Contact("Anh, Nguyễn Văn Tùng", "0982 000 134")

phone_book.insert(new_contact)

# Hiển thị toàn bộ danh sách liên hệ sau khi thêm liên hệ mới

print("\nContacts after adding new contact:")

phone_book.display_contacts()

• Lưu ý thêm:

Sau khi chạy mã này, chúng ta sẽ có cây tìm kiếm nhị phân chứa tất cả các liên hệ từ tệp contacts.inp, và sau đó sẽ thêm một liên hệ mới vào cây. Tuy nhiên, để vẽ cây như bạn yêu cầu, chúng ta cần một số thư viện hỗ trợ vẽ đồ thị. Bạn có thể sử dụng thư viện như matplotlib hoặc graphviz để vẽ cây

Câu 2. Tiếp tục với ứng dụng quản lí danh bạ, chức năng hiển thị danh sách liên hệ theo thứ tự từ điển. Do hạn chế của màn hình, mỗi trang chỉ hiển thị được 20 liên hệ. Hãy thêm tính năng in các liên hệ ở trang n bất kì do người dùng nhập vào, điều kiện n nguyên, lớn hơn 0 và nhỏ hơn hoặc bằng tổng số trang có thể hiển thị.

Giải chi tiết:

Để thực hiện chức năng in các liên hệ ở trang n bất kỳ trong danh sách liên hệ theo thứ tự từ điển, chúng ta cần tính toán và hiển thị chỉ một phần của danh sách liên hệ tùy thuộc vào trang được yêu cầu. Dưới đây là một cách để thực hiện điều này:

class PhoneBook:

def __init__(self):

self.contacts = []

self.page_size = 20

def insert(self, contact):

self.contacts.append(contact)

self.contacts.sort(key=lambda x: x.name)

def display_contacts(self, page_number):

total_pages = (len(self.contacts) + self.page_size - 1) // self.page_size

if page_number < 1 or page_number > total_pages:

print("Invalid page number. Please enter a number between 1 and {}.".format(total_pages))

return

start_index = (page_number - 1) * self.page_size

end_index = min(start_index + self.page_size, len(self.contacts))

print("Contacts - Page", page_number, "/", total_pages)

for i in range(start_index, end_index):

print("Name:", self.contacts[i].name, "- Phone:", self.contacts[i].phone_number)

# Sử dụng

phone_book = PhoneBook()

# Thêm các liên hệ

phone_book.insert(Contact("Anh An", "0901.000.159"))

phone_book.insert(Contact("Bố", "0983 000 131"))

phone_book.insert(Contact("Mẹ", "0962 000 481"))

phone_book.insert(Contact("ICTLab Station", "024 124 000 313"))

phone_book.insert(Contact("John Doe", "123456789"))

phone_book.insert(Contact("Alice Smith", "987654321"))

phone_book.insert(Contact("Bob Johnson", "456789123"))

phone_book.insert(Contact("Anh, Nguyễn Văn Tùng", "0982 000 134"))

# Hiển thị danh sách liên hệ theo trang

page_number = int(input("Enter page number: "))

phone_book.display_contacts(page_number)

VẬN DỤNG

Câu 1. 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 chi tiết:

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.")

Câu 2. Sử dụng cây tìm kiếm nhị phân để hiển thị các món trong tệp menu.inp ở Bài 8 theo thứ tự giá tiền tăng dần. Mỗi dòng in ra gồm tên món và giá tiền. Nếu có hai hoặc nhiều món cùng giá tiền thì các món đó được hiển thị theo thứ tự xuất hiện trong tệp menu.inp.

Giải chi tiết:

Để hiển thị các món trong tệp menu.inp theo thứ tự giá tiền tăng dần bằng cây tìm kiếm nhị phân, chúng ta cần đọc dữ liệu từ tệp, sau đó chèn mỗi món vào cây tìm kiếm nhị phân dựa trên giá tiền của món. Nếu có nhiều món có cùng giá tiền, chúng ta có thể sử dụng danh sách liên kết hoặc danh sách kết hợp để lưu trữ các món có cùng giá tiền. Dưới đây là một cách để thực hiện điều này:

class MenuItem:

def __init__(self, name, price):

self.name = name

self.price = price

class TreeNode:

def __init__(self, menu_item):

self.menu_item = menu_item

self.left = None

self.right = None

self.same_price = [] # Danh sách các món có cùng giá tiền

class MenuDatabase:

def __init__(self):

self.root = None

def insert(self, menu_item):

self.root = self._insert_recursive(self.root, menu_item)

def _insert_recursive(self, root, menu_item):

if root is None:

return TreeNode(menu_item)

if menu_item.price < root.menu_item.price:

root.left = self._insert_recursive(root.left, menu_item)

elif menu_item.price > root.menu_item.price:

root.right = self._insert_recursive(root.right, menu_item)

else:

root.same_price.append(menu_item)

return root

def display_menu_by_price(self, root):

if root:

self.display_menu_by_price(root.left)

print("Name:", root.menu_item.name, "- Price:", root.menu_item.price)

for item in root.same_price:

print("Name:", item.name, "- Price:", item.price)

self.display_menu_by_price(root.right)

# Đọc dữ liệu từ tệp menu.inp và chèn mỗi món vào cây tìm kiếm nhị phân

menu_db = MenuDatabase()

with open("menu.inp", "r") as file:

for line in file:

name, price = line.strip().split(", ")

menu_item = MenuItem(name, float(price))

menu_db.insert(menu_item)

# In danh sách món theo thứ tự giá tiền tăng dần

print("Menu sorted by price (ascending):")

menu_db.display_menu_by_price(menu_db.root)