Giáo án điện tử chuyên đề Khoa học máy tính 12 kết nối Bài 8: Thực hành cây tìm kiếm nhị phân

CHÀO ĐÓN CẢ LỚP ĐẾN VỚI BÀI HỌC MỚI!

KHỞI ĐỘNG

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?

BÀI 8.

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

Viết chương trình quản lí thực đơn

Nhiệm vụ:

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.

Nhiệm vụ

Viết chương trình quản lí thực đơn

Nhiệm vụ:

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:

a) Tra cứu giá theo tên món

Ví dụ: khi nhập Bún chả thì chương trình thông báo giá 60 000.

b) Bổ sung thêm món hoặc cập nhật giá tiền

Ví dụ: nhập Cà phê đen, 35 000 thì chương trình hiểu là cập nhật lại giá Cà phê đen thành 35 000, nếu nhập Nước chanh, 20 000 thì chương trình sẽ bổ sung thêm món Nước chanh.

Viết chương trình quản lí thực đơn

Nhiệm vụ:

Cài đặt cây tìm kiếm nhị phân

Bước 1

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].

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 T.

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.

Xây dựng chương trình hoàn chỉnh

Bước 2

Chương trình có bảng chọn ba chức năng tương ứng

0: Thoát chương trình

1: Tra cứu giá

2: Cập nhật hoặc thêm nhóm

Để 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:

LUYỆN TẬP

Câu 1. 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.

Câu 2. Mô tả quá trình tra cứu giá tiền món Bún chả thực hiện trên cây tìm kiếm nhị phân đã vẽ ở Luyện tập 1.

CÂU HỎI

Trả lời Câu 1

Để vẽ lại cây tìm kiếm nhị phân ứng với tệp menu.inp, đầu tiên cần sắp xếp tên các món ăn theo thứ tự từ điển để dễ so sánh các khoá khi chèn các nút vào cây.

• Thứ tự như sau:

Lưu ý: Do cây được cài đặt bằng mảng nên cây nhị phân thu được có thể có nhiều nút giả None và thực tế không có con trỏ left và right từ mỗi nút tới các nút con của nó. Thực hiện thuật toán chèn sẽ thu được cây như sau:

Cây nhị phân thực sự sau khi bỏ các nút giả None có thể được hình dung sau:

Trả lời Câu 2

Quá trình tìm kiếm bắt đầu bằng lời gọi hàm search(T,k = 0, name = "Bún chả”). Vì:

“Bún chả" < T[0][0] = "Cơm suất cá thu sốt” nên theo thuật toán cần đi tìm theo nhánh trái. Thuật toán gọi hàm left(0) trả về giá trị 1 ứng với nút “Cơm sườn cốt lết.

• Ở lần gọi hàm search thứ hai: search (T, k = 1, name = "Bún chả”) do “Bún chả" < T[1][0] = “Cơm sườn cốt lết” nên lại đi theo nhánh bên trái, left(1) = 3 ứng với nút “Bún chả.
• Ở lần gọi hàm search thứ ba: search (T, k = 3, name = “Bún chả”) thì giá trị cần tìm “Bún chả” đã bằng với khoá của nút hiện tại nên giá trị k = 3 là chỉ số của nút cần tìm trong mảng T. Nút này có dữ liệu giá tiền T[3][1] là 60 000.

VẬN DỤNG

--------------- Còn tiếp ---------------