Giáo án chuyên đề Khoa học máy tính 12 cánh diều Bài 2: Thực hành duyệt cây nhị phân

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 nhắc lại ý tưởng phương pháp biểu diễn cây nhị phân bằng mảng một chiều.

Em hãy trình bày ý tưởng biểu diễn cây nhị phân bằng mảng một chiều.

- GV nhấn mạnh về việc sử dụng cây nhị phân hoàn chỉnh.

- GV lấy một ví dụ cây nhị phân và hướng dẫn các bước thực hành trên ví dụ.

Hướng dẫn:

Bước 1. Bổ sung các nút giả vào cây để trở thành cây nhị phân hoàn chỉnh.

Bước 2. Biểu diễn cây nhị phân hoàn chỉnh bằng kiểu dữ liệu mảng một chiều list.

Hình 1a. Một ví dụ 
cây nhị phân với 5 nút

Hình 1b. Thực hiện Bước 1 
trên cây ở Hình 1a

- GV yêu cầu HS quan sát Hình 1b và trả lời câu hỏi:

 Em hãy trình bày cách đánh chỉ số cho các nút trên cây nhị phân hoàn chỉnh ở Hình 1b.

- GV hướng dẫn chương trình mẫu và yêu cầu HS viết chương trình đối với ví dụ cây nhị phân tự tạo.

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

- HS quan sát chương trình mẫu và viết chương trình đối với ví dụ cây nhị phân tự tạo.

- GV quan sát và trợ giúp 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 chạy chương trình và báo cáo kết quả cho GV.

- GV kiểm tra kết quả chạy chương trình của HS.

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

- Từ kết quả thực hành của HS, GV nhận xét, đánh giá quá trình HS thực hiện nhiệm vụ.

- GV chuyển sang nội dung Thực hành 2.

Thực hành 1. Xây dựng cây nhị phân từ một danh sách các phần tử cho trước

- Biểu diễn cây nhị phân hoàn hảo có n nút bằng mảng một chiều:

• Gán nhãn cho các nút của cây từ trên xuống dưới và từ trái sang phải trên cùng một mức bằng các chỉ số 0, 1, …, n – 1.

• Lưu các nút vào mảng một chiều: nút có chỉ số i được lưu vào phần tử có chỉ số i.

- Với cây nhị phân tổng quát, ta sẽ thêm vào một số nút giả và gán giá trị None để được cây nhị phân hoàn chỉnh, đưa các nút cây vào mảng một chiều vào đúng vị trí theo thứ tự vừa được đánh số.

- Hình 1b biểu diễn cây nhị phân hoàn chỉnh thu được sau khi tiến hành bổ sung các nút giả vào cây nhị phân ở Hình 1a. Để biểu diễn cây nhị phân hoàn chỉnh ở Hình 1b bằng mảng một chiều list, ta đánh chỉ số các nút trên cây như sau:

• Nút gốc có chỉ số 0.

• Đối với nút có chỉ số i: 

• Nút con trái có chỉ số 2 * i + 1.

• Nút con phải có chỉ số 2 * i + 2.

* Chương trình sử dụng list để biểu diễn cây nhị phân trong Hình 1b:

Hình 2. Chương trình in ra danh sách nút

Màn hình kết quả:

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 phân tích và hướng dẫn các bước thực hiện thuật toán xây dựng cây nhị phân bằng cách bổ sung từng nút vào cây nhị phân hoàn chỉnh biểu diễn bởi mảng một chiều.

Hướng dẫn:

• Tạo cây nhị phân hoàn chỉnh từ việc nhập vào một dãy số từ bàn phím.

• Giả sử nút thật có giá trị là số dương và nút giả có giá trị là 0. Cây rỗng tương ứng với dsNut[0] = 0.

• Dữ liệu nhập để tạo cây nhị phân tổng quát ở Hình  1a là dãy các số 4, 7, 9, 0, 12, 14. Cần tạo cây nhị phân hoàn chỉnh từ cây nhị phân tổng quát bằng cách thêm vào các nút giả.

- GV hướng dẫn chương trình mẫu và yêu cầu HS viết chương trình đối với ví dụ cây nhị phân tự tạo.

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

- HS quan sát chương trình mẫu và viết chương trình đối với ví dụ cây nhị phân tự tạo.

- GV quan sát và trợ giúp 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 chạy chương trình và báo cáo kết quả cho GV.

- GV kiểm tra kết quả chạy chương trình của HS.

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

- Từ kết quả thực hành của HS, GV nhận xét, đánh giá quá trình HS thực hiện nhiệm vụ.

- GV chuyển sang nội dung Thực hành 3.

Thực hành 2. Sử dụng kiểu dữ liệu list trong Python xây dựng cây nhị phân bằng cách bổ sung từng nút vào cây

Hình 3. Chương trình tạo cây nhị phân hoàn chỉnh từ mảng dsNut

Màn hình kết quả:

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 nhắc lại phương pháp duyệt cây nhị phân theo thứ tự trước.

 Em hãy trình bày phương pháp duyệt cây nhị phân theo thứ tự trước.

- GV phân tích và hướng dẫn các bước thực hiện thuật toán đệ quy duyệt cây nhị phân theo thứ tự trước.

- GV hướng dẫn chương trình mẫu và yêu cầu HS viết chương trình đối với ví dụ cây nhị phân tự tạo.

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

- HS quan sát chương trình mẫu và viết chương trình đối với ví dụ cây nhị phân tự tạo.

- GV quan sát và trợ giúp 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 chạy chương trình và báo cáo kết quả cho GV.

- GV kiểm tra kết quả chạy chương trình của HS.

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

- Từ kết quả thực hành của HS, GV nhận xét, đánh giá quá trình HS thực hiện nhiệm vụ.

Thực hành 3. Duyệt cây theo thứ tự trước, thứ tự sau và thứ tự giữa

a) Thứ tự trước

- Phương pháp duyệt cây nhị phân T theo thứ tự trước:

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

2. Duyệt các nút của  theo thứ tự trước.

3. Duyệt các nút của  theo thứ tự trước.

- Mã giả mô tả thuật toán đệ quy duyệt cây nhị phân T theo thứ tự trước (gốc – trái – phải):

Hình 4. Mã giả mô tả thuật toán đệ quy 
duyệt theo thứ tự trước

- Chương trình duyệt cây theo thứ tự trước:

Hình 5. Chương trình duyệt cây 
theo thứ tự trước

Màn hình kết quả: