Giáo án điện tử chuyên đề Khoa học máy tính 12 cánh diều Bài 4 Thực hành tổng hợp: Ứng dụng 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 mảng A = [5, 7, 30, 23, 34, 15]. Hãy vẽ cây tìm kiếm nhị phân biểu diễn mảng A.

BÀI 4:

THỰC HÀNH TỔNG HỢP:

ỨNG DỤNG CÂY TÌM KIẾM

NHỊ PHÂN

NỘI DUNG BÀI HỌC

THỰC HÀNH

LUYỆN TẬP, VẬN DỤNG

PHẦN 1.

THỰC HÀNH

NHIỆM VỤ THỰC HÀNH

1. Mô tả các bước thực hiện thuật toán cho các yêu cầu trong bài toán.

2. Mô phỏng chi tiết các bước ứng dụng cây tìm kiếm nhị phân giải quyết bài toán đối với một ví dụ cụ thể.

3. Viết chương trình duyệt cây nhị phân theo thứ tự giữa.

4. Kết quả thử nghiệm trên các bộ dữ liệu đầu vào mẫu và tự tạo.

NỘI DUNG CỤ THỂ CẦN THỰC HIỆN

Gia đình Hương Trà làm kinh doanh, thường xuyên nhập về kho các mặt hàng có mã khác nhau. Mỗi lần có một mặt hàng nhập về kho, gia đình Hương Trà thường ghi chép lại bằng tay để quản lí. Sau khi được học về cây tìm kiếm nhị phân, Hương Trà muốn viết chương trình quản lí hàng hoá cho gia đình mình. Hương Trà dự định sử dụng cây tìm kiếm nhị phân để quản lí hàng hoá, mỗi nút trên cây sẽ lưu trữ thông tin của một mặt hàng.

Hương Trà hiểu là một mặt hàng có nhiều thông tin cần quản lí như: giá trị, số lượng, ngày xuất/nhập, nguồn gốc,... Do mới học cây tìm kiếm nhị phân với mỗi nút chứa thông tin một khoá, Hương Trà dự kiến xây dựng cây tìm kiếm nhị phân để quản lí một thông tin là mã mặt hàng, rồi sẽ tìm hiểm thêm để mở rộng sang bài toán quản lí nhiều thông tin mặt hàng. Cụ thể, Hương Trà sẽ xây dựng cây tìm kiếm nhị phân, mỗi nút có khoá là mã của một mặt hàng sao cho có thể thuận lợi để thực hiện các yêu cầu sau đây:

1. Mỗi lần một mặt hàng được nhập về, Hương Trà sẽ chèn vào cây tìm kiếm nhị phân một nút có khoá là mã của mặt hàng đó.

2. Trả lời có tồn tại mặt hàng trong kho có mã bằng x cho trước hay không.

3. Đưa ra danh sách mã các món hàng trong kho theo thứ tự tăng dần.

4. Đưa ra danh sách các mặt hàng có mã trong khoảng từ min đến max.

Thực hành 1.

Mô tả các bước thực hiện thuật toán

cho các yêu cầu trong bài toán

Thực hành 1. Mô tả các bước thực hiện thuật toán

cho các yêu cầu trong bài toán

Đầu vào của bài toán là một tập các phần tử có giá trị là mã các mặt hàng được nhập vào lần lượt.

1. Khởi tạo một cây tìm kiếm nhị phân rỗng. Với mỗi mã mặt hàng được nhập vào, tạo một nút mới có khoá là mã mặt hàng vừa nhập và chèn nút vào đúng vị trí trên cây tìm kiếm nhị phân.

YÊU CẦU

2. Với một giá trị x nhập vào, thực hiện thao tác tìm kiếm giá trị khoá x trên cây tìm kiếm nhị phân.

3. Thực hiện phép duyệt cây tìm kiếm nhị phân theo thứ tự giữa thu được danh sách các mã mặt hàng được đưa ra theo thứ tự giá trị khoá tăng dần.

YÊU CẦU

4. Thực hiện phép duyệt cây tìm kiếm nhị phân theo thứ tự giữa: Nếu gặp nút có giá trị khoá nhỏ hơn min hoặc có giá trị khoá lớn hơn max thì dừng việc duyệt đến các nút con của nó và tiếp tục quay lại quá trình duyệt cho các nhánh khác.

Thực hành 2.

Mô phỏng chi tiết các bước ứng dụng cây tìm kiếm nhị phân giải quyết

bài toán đối với một ví dụ cụ thể

Thực hành 2. Mô phỏng chi tiết các bước ứng dụng

cây tìm kiếm nhị phân giải quyết bài toán

đối với một ví dụ cụ thể

Nhiệm vụ: Mỗi nhóm chọn một ví dụ cụ thể và mô phỏng chi tiết từng bước trên ví dụ đó theo hướng dẫn.

Khởi tạo cây tìm kiếm nhị phân.

Chèn từng mã mặt hàng vào cây.

Tìm kiếm một mã mặt hàng trên cây.

Duyệt cây theo thứ tự giữa tìm nút có giá trị khoá x.

Duyệt cây theo thứ tự giữa đưa ra danh sách các nút có giá trị khoá trong khoảng từ min đến max.

HƯỚNG DẪN

Thực hành 3.

Viết chương trình duyệt

cây nhị phân theo thứ tự giữa

Thực hành 3. Viết chương trình

duyệt cây nhị phân theo thứ tự giữa

Em hãy nhắc lại

phương pháp duyệt cây nhị phân theo thứ tự giữa.

Thực hành 3. Viết chương trình

duyệt cây nhị phân theo thứ tự giữa

Phương pháp duyệt cây nhị phân T theo thứ tự giữa:

1. Duyệt các nút của theo thứ tự giữa.

2. Duyệt nút gốc r của T.

3. Duyệt các nút của theo thứ tự giữa.

------------------------------

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