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

CHÀO MỪNG CẢ LỚP

ĐẾN BUỔI HỌC NÀY!

KHỞI ĐỘNG

Cho cây tìm kiếm nhị phân ở Hình 1. Ở bài học trước, em đã được giới thiệu về việc giá trị các nút trong cây tìm kiếm nhị phân được sắp xếp theo một trình tự nhất định. Em hãy mô phỏng thuật toán để xuất giá trị các nút của cây tìm kiếm nhị phân trong Hình 1 theo thứ tự tăng dần.

Hình 1. Cây tìm kiếm nhị phân

KHỞI ĐỘNG

Sử dụng phép toán duyệt giữa để xuất giá trị các nút của cây tìm kiếm nhị phân trong Hình 1 theo thứ tự tăng dần.

BÀI 2.4:

THỰC HÀNH

CÂY TÌM KIẾM

NHỊ PHÂN

NỘI DUNG BÀI HỌC

Nhiệm vụ 1.

Ứng dụng cây tìm kiếm nhị phân để giải bài toán tìm kiếm

Nhiệm vụ 2.

Sắp xếp mảng dùng cây tìm kiếm nhị phân

Nhiệm vụ 1.

Ứng dụng cây tìm kiếm nhị phân để giải bài toán tìm kiếm

Nhiệm vụ 1. Ứng dụng cây tìm kiếm nhị phân

để giải bài toán tìm kiếm

Yêu cầu: Cho cây tìm kiếm nhị phân (Hình 2) biểu diễn tập hợp số nguyên dương A = {46, 49, 31, 45, 41, 50, 47, 28, 30, 48}.

Em hãy viết chương trình kiểm tra giá trị x = 41 có xuất hiện trong tập hợp A hay không.

Nhiệm vụ 1. Ứng dụng cây tìm kiếm nhị phân

để giải bài toán tìm kiếm

Hướng dẫn: Sử dụng chương trình tạo cây tìm kiếm nhị phân và chương trình con tìm kiếm ở Bài 2.3 để thực hiện yêu cầu trên.

Gợi ý: Mã nguồn tham khảo:

Kết quả chạy chương trình

Nhiệm vụ 2.

Sắp xếp mảng dùng cây tìm kiếm nhị phân

Nhiệm vụ 2.

Sắp xếp mảng dùng cây tìm kiếm nhị phân

Yêu cầu: Sắp xếp một mảng số nguyên a tăng dần.

Hướng dẫn:

2. Duyệt giữa cây tìm kiếm nhị phân T.

1. Tạo cây tìm kiếm nhị phân T từ mảng a.

Gợi ý: Mã nguồn tham khảo:

Kết quả chạy chương trình

LUYỆN TẬP

Nhiệm vụ. Tìm thanh gỗ theo yêu cầu: Tại xưởng gỗ, bác thợ mộc cần tìm một thanh gỗ có kích thước là k (cm) trong n thanh gỗ có các kích thước khác nhau để đóng tủ.

Yêu cầu: Để giúp bác thợ mộc tìm thanh gỗ đúng với kích thước đã cho. Hãy viết chương trình.

LUYỆN TẬP

Hướng dẫn: Sử dụng chương trình tạo cây tìm kiếm nhị phân và chương trình con tìm kiếm để giải quyết bài toán tìm kiếm trên.

• Hai số nguyên n, k (giá trị n cho biết có n thanh gỗ trong xưởng; giá trị k cho biết kích thước thanh gỗ mà bác thợ mộc cần tìm).

• n giá trị tiếp theo là kích thước của n thanh gỗ có trong xưởng.

Dữ liệu vào

LUYỆN TẬP

Hướng dẫn: Sử dụng chương trình tạo cây tìm kiếm nhị phân và chương trình con tìm kiếm để giải quyết bài toán tìm kiếm trên.

Dữ liệu ra: In ra màn hình “Có” nếu tìm thấy thanh gỗ đúng kích thước. Ngược lại, in “Không”.

LUYỆN TẬP

Ví dụ:

Gợi ý: Mã nguồn tham khảo:

VẬN DỤNG

Cho tập hợp số nguyên dương A = {28, 21, 43, 13, 23, 35, 50, 10, 15, 22, 27, 30, 40, 47, 52}.

a) Viết chương trình tạo cây tìm kiếm nhị phân T biểu diễn tập hợp A.

b) Vẽ minh hoạ cây T.

c) Viết chương trình kiểm tra giá trị x = 10 có xuất hiện trong cây tìm kiếm nhị phân T hay không.

d) Viết chương trình xuất ra màn hình các giá trị của tập hợp A được sắp xếp giảm dần.

Gợi ý đáp án:

a) Chương trình tạo cây tìm kiếm nhị phân T

biểu diễn tập hợp A:

b) Minh hoạ cây T:

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