Giáo án điện tử 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

CHÀO MỪNG CÁC EM ĐẾN BUỔI HỌC NÀY!

KHỞI ĐỘNG

a) Em hãy quan sát hình sau đây và cho biết đâu là cây nhị phân hoàn chỉnh, đâu là cây nhị phân hoàn hảo?

b) Thế nào là cây nhị phân hoàn chỉnh? Thế nào là cây nhị phân hoàn hảo?

Cây nhị phân hoàn chỉnh.

Cây nhị phân hoàn hảo.

KHỞI ĐỘNG

• Cây nhị phân hoàn chỉnh là cây nhị phân thoả mãn:
• Cây nhị phân hoàn hảo là cây nhị phân thoả mãn:
• Mỗi nút trong có đúng 2 nút con.
• Tất cả các nút lá ở cùng một độ sâu.

BÀI 2: THỰC HÀNH

DUYỆT CÂY NHỊ PHÂN

NỘI DUNG BÀI HỌC

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

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

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

1

XÂY DỰNG CÂY NHỊ PHÂN

TỪ MỘT DANH SÁCH CÁC

PHẦN TỬ CHO TRƯỚC

Thực hành 1

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

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.

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.

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

Với cây nhị phân tổng quát: 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ố.

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

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

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

1

HƯỚNG DẪN:

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

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

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.

2

HƯỚNG DẪN:

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

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

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.

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

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

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.

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 chỉnh ở Hình 1b bằng mảng một chiều list bằng cách đá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.

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

• Chương trình sử dụng list để biểu diễn cây nhị phân trong Hình 1b:
• Màn hình kết quả:

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

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

Thực hành 2

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

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.

1

HƯỚNG DẪN:

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.

2

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ả.

3

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

DUYỆT CÂY THEO THỨ TỰ TRƯỚC,

THỨ TỰ SAU VÀ THỨ TỰ GIỮA

Thực hành 3

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

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

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