Ngày soạn:…/…/…

Ngày dạy:…/…/…

BÀI 9: CÁC THUẬT TOÁN DUYỆT TRÊN CÂY TÌM KIẾM NHỊ PHÂN

(2 tiết)

I. MỤC TIÊU

1. Kiến thức

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

• Trình bày các thuật toán duyệt trên cây tìm kiếm nhị phân.

• Trình bày thuật toán sắp xếp dãy số sử dụng cây tìm kiếm nhị phân.

2. Năng lực

Năng lực chung:

• Năng lực giao tiếp và hợp tác: Biết lựa chọn hình thức làm việc nhóm với quy mô phù hợp với yêu cầu và thực hiện tốt nhiệm vụ.

• Năng lực tự chủ và tự học: Chủ động học tập, tìm hiểu nội dung bài học, biết lắng nghe và trả lời nội dung trong bài học.

• Giải quyết vấn đề và sáng tạo: Trả lời được các câu hỏi, giải quyết được các vấn đề với sự hỗ trợ của công nghệ thông tin và truyền thông.

Năng lực Tin học:

• Thực hiện được các thuật toán duyệt trên cây tìm kiếm nhị phân.

• Tìm kiếm và 1 sắp xếp dây số dựa trên cây tìm kiếm nhị phân.

3. Phẩm chất

• Chăm chỉ: Tích cực tìm tòi và sáng tạo trong học tập.

• Trung thực: Thực hiện đúng phần việc của bản thân và hợp tác làm việc nhóm khi được giao nhiệm vụ. Có ý thức báo cáo kết quả một cách chính xác.

• Trách nhiệm: Hoàn thành các bài tập theo yêu cầu của GV thông qua hệ thống câu hỏi, phiếu học tập, thông qua sản phẩm.

II. THIẾT BỊ DẠY HỌC VÀ HỌC LIỆU:

1. Đối với giáo viên:

• Tài liệu, máy tính, máy trình chiếu.

• SGK, SGV Chuyên đề học tập Tin học 12 – Định hướng Khoa học máy tính – Kết nối tri thức với cuộc sống.

2. Đối với học sinh:

• Vở ghi, máy tính.

• SGK Chuyên đề học tập Tin học 12 – Định hướng Khoa học máy tính – Kết nối tri thức với cuộc sống.

III. TIẾN TRÌNH DẠY HỌC

A. HOẠT ĐỘNG KHỞI ĐỘNG

a. Mục tiêu: HS nhận ra được một mô hình dữ liệu mới khác với kiểu dữ liệu mảng đã học.

b. Nội dung: HS quan sát các hình ảnh, suy nghĩ, thảo luận và trả lời câu hỏi.

c. Sản phẩm học tập: Câu trả lời của HS.

d. Tổ chức thực hiện:

Bước 1: GV chuyển giao nhiệm vụ học tập

- GV cho HS thảo luận theo nhóm đôi.

- GV yêu cầu HS quan sát và trả lời câu hỏi Khởi động SGK trang 41

Quan sát cây tìm kiếm nhị phân trong Hình 9.1, cùng trao đổi, thảo luận các câu hỏi sau:

a) Nếu thực hiện thuật toán duyệt giữa (trái - gốc – phải) thì nút đầu tiên được duyệt là nút nào?

b) Nút cuối cùng được duyệt là nút nào?

c) Thứ tự các nút được duyệt theo thuật toán duyệt giữa sẽ theo thứ tự nào? Em có nhận xét gì về kết quả đạt được? Giải thích vì sao.

Bước 2: HS thực hiện nhiệm vụ học tập

- HS tiếp nhận, thực hiện nhiệm vụ.

- GV hướng dẫn, hỗ trợ HS (nếu cần thiết).

Bước 3: Báo cáo kết quả hoạt động và thảo luận

- HS trình bày câu trả lời, các HS khác chú ý lắng nghe và nhận xét.

Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập

GV đánh giá kết quả của HS, dẫn dắt HS vào bài học mới: Ở các bài học trước ta đã tìm hiểu về cây tìm kiếm nhị phân, thuật toán tìm kiếm nhị phân. Bài học này chúng ta cùng đi tìm hiểu các thuật toán duyệt trên cây tìm kiếm nhị phân - Bài 9: Các thuật toán duyệt trên cây tìm kiếm nhị phân.

B. HOẠT ĐỘNG HÌNH THÀNH KIẾN THỨC

Hoạt động 1. Các thuật toán duyệt cây tìm kiếm nhị phân

a. Mục tiêu: HS biết và hiểu được cách thiết lập các thuật toán duyệt cây tìm kiếm nhị phân, biết được sự khác biệt của các thuật toán này so với các thuật toán duyệt đã biết trong Bài 6, biết được ý nghĩa thuật toán duyệt giữa và duyệt ngược trên cây tìm kiếm nhị phân.

b. Nội dung: GV giao nhiệm vụ; HS tìm hiểu nội dung mục 1, kết hợp với những hiểu biết về thực tiễn, thảo luận nhóm thực hiện nhiệm vụ.

c. Sản phẩm: Hình thành được kiến thức bài học. HS trình bày được các cách thiết lập các thuật toán duyệt cây tìm kiếm nhị phân.

d. Tổ chức thực hiện:

Hoạt động 2. Sắp xếp dãy số bằng cây tìm kiếm nhị phân

a. Mục tiêu: HS hiểu được ý tưởng và cách thực hiện thuật toán sắp xếp dãy số mới dựa trên cây tìm kiếm nhị phân và so sánh với các thuật toán sắp xếp đã biết.

b. Nội dung: GV giao nhiệm vụ; HS tìm hiểu nội dung mục 2, kết hợp với những hiểu biết về thực tiễn, thảo luận nhóm thực hiện nhiệm vụ.

c. Sản phẩm: Hình thành kiến thức bài học. HS nêu được thuật toán sắp xếp dãy số mới dựa trên cây tìm kiếm nhị phân.

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

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