Tin học 12 · SGK Chuyên đề Khoa học máy tính

Bài 8. Thực hành cây tìm kiếm nhị phân

THỰC HÀNH CÂY TÌM KIẾM NHỊ PHÂN

Sau bài học này em sẽ:

Trong Bài 7, cây 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?

Nhiệm vụ: Viết chương trình quản lí thực đơn

Em có nhiệm vụ quản lí thực đơn các món ăn hoặc uống (gọi chung là món) của một nhà hàng. Mỗi món đều có tên (không trùng nhau) và giá tiền. Dữ liệu được nhập từ tệp văn bản menu.inp, mỗi dòng ứng với một món, có tên và giá tiền cách nhau bởi dấu phẩy.

Em hãy viết chương trình nhập thực đơn từ tệp menu.inp và lưu trữ vào cây tìm kiếm nhị phân được cài đặt bằng mảng, sau đó cho phép người dùng:

menu.inp

Cơm suất cá thu sốt, 50000
Cơm suất cá trắm, 40000
Cơm sườn cốt lết, 85000
Phở xào bò, 35000
Phở tái chín, 40000
Bún chả, 60000
Cà phê đen, 30000
Cà phê nâu, 35000
Nước ngọt, 15000

Hướng dẫn

Chương trình gồm hai bước: (1) cài đặt cây tìm kiếm nhị phân bằng mảng và (2) xây dựng chương trình đọc dữ liệu từ tệp, lưu trữ dữ liệu vào cây tìm kiếm nhị phân; cho phép người dùng tra cứu, bổ sung, cập nhật các món.

Bước 1. Cài đặt cây tìm kiếm nhị phân.

Phân tích: Mỗi món có hai thuộc tính là tên món và giá tiền. Mỗi nút của cây tìm kiếm nhị phân ứng với một món. Do đó, cấu trúc dữ liệu của nút gồm hai phần tử [tên món, giá tiền]. Trong bài toán này, cây tìm kiếm nhị phân được cài đặt bằng một mảng, mỗi phần tử lại là một mảng gồm [tên món, giá tiền]. Ví dụ, nếu danh sách món trong tệp menu.inp gồm hai món Bún chả, 60000 và Cà phê đen, 30000 thì mảng biểu diễn cây tìm kiếm nhị phân là mảng T; T[k] biểu diễn nút có chỉ số k; T[k][0] là tên món; T[k][1] là giá tiền. Hàm Tree_Insert(T, name, price) dùng để thêm món (name, price) vào cây tìm kiếm nhị phân; hàm search(T, k, name) dùng để tìm chỉ số của nút có tên là name, bắt đầu từ chỉ số k trong mảng T. Để thuận tiện cho việc bổ sung món hoặc cập nhật giá tiền, cần thêm hàm Tree_Insert_Update(T, name, price) gọi hàm search để kiểm tra xem món ăn đó đã tồn tại chưa, nếu đã tồn tại thì cập nhật giá, nếu chưa thì gọi hàm Tree_Insert. Các hàm Tree_Insert, search và Tree_Insert_Update được viết trong tệp BST_menu.py như sau:

def left(k):
return 2 * k + 1
def right(k):
return 2 * k + 2
def Tree():
return []
def Tree_Insert(T, name, price):
k = 0
while k < len(T) and T[k] != None:
if name < T[k][0]:
k = left(k)
elif name > T[k][0]:
k = right(k)
else:
return
if k >= len(T):
T.extend([None] * (k - len(T) + 1))
T[k] = [name, price]  # Chèn một mảng vào phần tử k
def search(T, k, name):
if k >= len(T) or T[k] == None:
return -1
else:
if name == T[k][0]:
return k
elif name < T[k][0]:
return search(T, left(k), name)
else:
return search(T, right(k), name)
def Insert_Update(T, name, price):
k = search(T, 0, name)
if k == -1:
Tree_Insert(T, name, price)
return False  # Thể hiện đã thêm món mới
else:
T[k][1] = price  # Cập nhật giá món
return True  # Thể hiện đã cập nhật

Bước 2. Xây dựng chương trình hoàn chỉnh.

Chương trình có bảng chọn ba chức năng tương ứng với thoát chương trình; tra cứu giá theo tên món; cập nhật giá tiền hoặc bổ sung món mới như sau:

0: Thoát chương trình
1: Tra cứu
2: Cập nhật hoặc thêm món

Để thực hiện tính năng này, em có thể dùng một vòng lặp trong đó mỗi vòng lặp thực hiện hỏi người dùng lựa chọn, sau đó ứng với số được chọn, thực hiện các đoạn mã gọi các chức năng tương ứng. Mã nguồn chương trình như sau:

from BST_menu import *  # Khai báo thư viện cây tìm kiếm nhị phân
T = Tree()
f = open("menu.inp", "r", encoding="utf8")
lines = f.readlines()
for line in lines:
l = line.strip()
l = l.split(",", maxsplit=2)
Tree_Insert(T, l[0], l[1])
f.close()
options = ["Thoát chương trình", "Tra cứu", "Cập nhật hoặc thêm món"]
selected = 1
while selected != 0:
for choice in range(len(options)):
print(choice, options[choice])
selected = int(input("Chọn chức năng: "))
if selected < 0 or selected > 2:
print("Chức năng không hợp lệ, hãy nhập số 0, 1 hoặc 2")
continue
if selected == 1:
item = input("Nhập tên món: ")
k = search(T, 0, item)
if k != -1:
print("Giá", item, T[k][1])  # T[k][1] là giá của phần tử thứ k
else:
print("Món", item, "không có trong thực đơn")
elif selected == 2:
key = input("Nhập tên món: ")
price = int(input("Nhập giá tiền (số nguyên dương): "))
if Insert_Update(T, key, price):
print("Đã cập nhật giá", key)
else:
print("Đã thêm món", key, "vào thực đơn")