Giáo án chuyên đề Khoa học máy tính 12 chân trời Bài 2.2: Các phép toán duyệt cây nhị phân

2

24

11

0

3

8

9

HOẠT ĐỘNG CỦA GV - HS

DỰ KIẾN SẢN PHẨM

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

- GV yêu cầu HS tìm hiểu nội dung trong SGK và trả lời câu hỏi:

+ Thế nào là duyệt cây nhị phân?

- GV chia lớp thành 6 nhóm:

+ Nhóm 1, 2: Tìm hiểu duyệt cây nhị phân theo phép toán duyệt trước.

+ Nhóm 3, 4: Tìm hiểu duyệt cây nhị phân theo phép toán duyệt giữa.

+ Nhóm 5, 6: Tìm hiểu duyệt cây nhị phân theo phép toán duyệt sau.

- Sau khi tìm hiểu quy trình duyệt cây nhị phân, các nhóm thực hiện duyệt cây nhị phân ở Hình 3 trong SGK theo cách duyệt mà nhóm đã tìm hiểu.

- GV yêu cầu HS vận dụng kiến thức vừa tìm hiểu, trả lời câu hỏi hoạt động Làm SGK tr.35:

Cho cây nhị phân như Hình 4.

Hình 4. Cây nhị phân

Kết quả thực hiện phép toán duyệt nhị phân như sau:

Phép toán duyệt cây nhị phân cho kết quả như bảng ở trên là phép toán nào?

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

- HS tìm hiểu nội dung SGK sau đó trao đổi, thảo luận thực hiện các yêu cầu mà GV đưa ra, ghi kết quả vào bảng phụ.

- GV quan sát, hướng dẫn, hỗ trợ các nhóm (nếu cần thiết).

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

- GV cho đại diện các nhóm có cùng nhiệm vụ bốc thăm: Trình bày hay nhận xét.

- Nhóm bốc thăm được nhiệm vụ trình bày sẽ mang bảng phụ lên và cử thành viên trình bày kết quả đã thảo luận gồm các bước của cách duyệt và minh hoạ thông qua ví dụ trên cây nhị phân được yêu cầu. Nhóm bốc thăm nhiệm vụ nhận xét sẽ theo dõi, nhận xét phần trình bày của nhóm bạn, bổ sung ý kiến (nếu cần thiết). 

- Các nhóm còn lại theo dõi, tiếp thu. 

Hướng dẫn trả lời câu hỏi hoạt động Làm SGK tr.35:

Phép toán duyệt cây nhị phân là phép toán duyệt giữa.

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

- GV nhận xét kết quả thảo luận của các nhóm, chính xác hoá lại các nội dung trả lời của HS.

1. Các phép toán duyệt cây nhị phân

- Duyệt cây nhị phân là quá trình thăm tất cả nút và mọi nút chỉ được thăm đúng một lần. Tuỳ theo quá trình thăm tất cả nút mà thứ tự xử lí của các nút là khác nhau.

Hình 2. Cây nhị phân gốc i.

- Tuỳ theo thứ tự giải quyết: xử lí nút i (gốc), duyệt cây con trái (trái), duyệt cây con phải (phải), có ba phép toán duyệt cây nhị phân như sau:

• Duyệt trước (gốc – trái – phải): xử lí nút gốc i (gốc), duyệt cây con trái (trái), duyệt cây con phải (phải).

• Duyệt giữa (trái – gốc – phải): duyệt cây con trái (trái), xử lí nút gốc i (gốc), duyệt cây con phải (phải). 

• Duyệt sau (trái – phải – gốc): duyệt cây con trái (trái), duyệt cây con phải (phải), xử lí nút gốc i (gốc).

Hình 3. Cây nhị phân

• a) Duyệt trước (gốc – trái – phải)

• - Thứ tự của phép toán duyệt trước cây gốc i:

Xử lí nút gốc i (gốc).

Duyệt cây con trái (trái).

Duyệt cây con phải (phải).

- Các bước thực hiện phép toán duyệt trước cây nhị phân ở Hình 3:

i = 0, xử lí nút 7.

Duyệt cây con trái của nút 7: Duyệt cây gốc 4. 

a. Xử lí nút 4.

b. Duyệt cây con trái của nút 4: Duyệt cây gốc 1.

• Xử lí nút 1.

• Duyệt cây con trái của nút 1: Không tồn tại trong cây Bỏ qua.

• Duyệt cây con phải của nút 1: Không tồn tại trong cây Bỏ qua.

c. Duyệt cây con phải của nút 4: Duyệt cây gốc 5.

• Xử lí nút 5.

• Duyệt cây con trái của nút 5: Không tồn tại trong cây Bỏ qua.

• Duyệt cây con phải của nút 5: Không tồn tại trong cây Bỏ qua.

Duyệt cây con phải của nút 7: Duyệt cây gốc 3.

a. Xử lí nút 3.

b. Duyệt cây con trái của nút 3: Duyệt cây gốc 2.

• Xử lí nút 2.

• Duyệt cây con trái của nút 2: Không tồn tại trong cây Bỏ qua.

• Duyệt cây con phải của nút 2: Không tồn tại trong cây Bỏ qua.

c. Duyệt cây con phải của nút 3: Không tồn tại trong cây Bỏ qua.

- Kết quả thực hiện phép toán duyệt trước cây nhị phân ở Hình 3:

b) Duyệt giữa (trái – gốc – phải)

• - Thứ tự của phép toán duyệt giữa cây gốc i:

Duyệt cây con trái (trái).

Xử lí nút góc i (gốc).

Duyệt cây con phải (phải).

- Các bước thực hiện phép toán duyệt giữa cây nhị phân ở Hình 3:

Duyệt cây con trái của nút 7: Duyệt cây gốc 4.

a. Duyệt cây con trái của nút 4: Duyệt cây gốc 1.

• Duyệt cây con trái của nút 1: Không tồn tại trong cây Bỏ qua.

• Xử lí nút 1.

• Duyệt cây con phải của nút 1: Không tồn tại trong cây Bỏ qua.

b. Xử lí nút 4.

c. Duyệt cây con phải của nút 4: Duyệt cây gốc 5.

• Duyệt cây con trái của nút 5: Không tồn tại trong cây Bỏ qua.

• Xử lí nút 5.

• Duyệt cây con phải của nút 5: Không tồn tại trong cây Bỏ qua.

Xử lí nút 7. 

Duyệt cây con phải của nút 7: Duyệt cây gốc 3.

b. Duyệt cây con trái của nút 3: Duyệt cây gốc 2.

• Duyệt cây con trái của nút 2: Không tồn tại trong cây Bỏ qua.

• Xử lí nút 2.

• Duyệt cây con phải của nút 2: Không tồn tại trong cây Bỏ qua.

a. Xử lí nút 3.

c. Duyệt cây con phải của nút 3: Không tồn tại trong cây Bỏ qua.

- Kết quả thực hiện phép toán duyệt giữa cây nhị phân ở Hình 3:

c) Duyệt sau (trái – phải – gốc)

• - Thứ tự của phép toán duyệt sau cây gốc i:

Duyệt cây con trái (trái).

Duyệt cây con phải (phải).

Xử lí nút gốc i (gốc).

- Các bước thực hiện phép toán duyệt sau cây nhị phân ở Hình 3:

Duyệt cây con trái của nút 7: Duyệt cây gốc 4. 

a. Duyệt cây con trái của nút 4: Duyệt cây gốc 1.

• Duyệt cây con trái của nút 1: Không tồn tại trong cây Bỏ qua.

• Duyệt cây con phải của nút 1: Không tồn tại trong cây Bỏ qua.

• Xử lí nút 1.

b. Duyệt cây con phải của nút 4: Duyệt cây gốc 5.

• Duyệt cây con trái của nút 5: Không tồn tại trong cây Bỏ qua.

• Duyệt cây con phải của nút 5: Không tồn tại trong cây Bỏ qua.

• Xử lí nút 5.

c. Xử lí nút 4.

Duyệt cây con phải của nút 7: Duyệt cây gốc 3.

a. Duyệt cây con trái của nút 3: Duyệt cây gốc 2.

• Duyệt cây con trái của nút 2: Không tồn tại trong cây Bỏ qua.

• Duyệt cây con phải của nút 2: Không tồn tại trong cây Bỏ qua.

• Xử lí nút 2.

b. Duyệt cây con phải của nút 3: Không tồn tại trong cây Bỏ qua.

c. Xử lí nút 3.

Xử lí nút 7.

- Kết quả thực hiện phép toán duyệt sau cây nhị phân ở Hình 3:

HOẠT ĐỘNG CỦA GV - HS

DỰ KIẾN SẢN PHẨM

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

- GV tổ chức cho HS làm việc độc lập, đọc SGK, tìm hiểu thuật toán và các đoạn chương trình duyệt cây nhị phân theo ba cách duyệt trước, duyệt giữa, duyệt sau. Sau đó, GV yêu cầu HS thực hiện viết đoạn chương trình trên máy tính, chạy thuật toán và quan sát kết quả.

- GV yêu cầu HS vận dụng kiến thức vừa tìm hiểu, thực hiện hoạt động Làm SGK tr.38 – 39: 

Cho cây nhị phân như Hình 8. Biểu diễn các giá trị trong cây nhị phân bằng mảng một chiều theo:

a) Duyệt trước.

b) Duyệt giữa.

c) Duyệt sau.

Hình 8. Cây nhị phân

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

- HS đọc, phân tích, tìm hiểu thuật toán và đoạn chương trình cài đặt phép toán duyệt nhị phân trong SGK.

- Cá nhân HS viết lại đoạn chương trình, chạy thuật toán và quan sát kết quả duyệt cây nhị phân.

- GV quan sát, 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 báo cáo kết quả chạy chương trình.

- GV mời 3 HS xung phong trình bày kết quả thực hiện hoạt động Làm. HS khác chú ý lắng nghe, nhận xét và bổ sung (nếu cần). 

Hướng dẫn trả lời câu hỏi hoạt động Làm SGK tr.38 – 39:

…………………..

2. Cài đặt các phép toán duyệt cây nhị phân

Hình 1. Cây nhị phân

a) Duyệt trước (gốc – trái – phải)

- Thuật toán:

- Cài đặt thuật toán duyệt trước bằng hàm đệ quy:

Hình 5. Quá trình duyệt trước cây nhị phân

- Chương trình tham khảo:

Kết quả duyệt trước cây nhị phân ở Hình 1:

b) Duyệt giữa (trái – gốc – phải)

- Thuật toán:

- Cài đặt thuật toán duyệt giữa bằng hàm đệ quy:

………………………..