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

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

KHỞI ĐỘNG

Cho cây nhị phân như Hình 1. Hãy dùng mảng một chiều để biểu diễn các giá trị trong cây nhị phân.

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

KHỞI ĐỘNG

Cho cây nhị phân như Hình 1. Hãy dùng mảng một chiều để biểu diễn các giá trị trong cây nhị phân.

• Chú ý: Ở những nút có giá trị None khi đưa về mảng một chiều, phần tử mang giá trị 0.
• Mảng một chiều biểu diễn các giá trị trong cây nhị phân:

BÀI 2.2: CÁC PHÉP TOÁN DUYỆT CÂY NHỊ PHÂN

NỘI DUNG BÀI HỌC

1

2

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

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

CÁC PHÉP TOÁN

DUYỆT CÂY NHỊ PHÂN

1

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

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.

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

• 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).

THẢO LUẬN 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.

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:

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

2

Xử lí nút

gốc i (gốc).

1

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

3

a) Duyệt trước (gốc – trá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.

1

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

2

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.

a) Duyệt trước (gốc – trá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.

1

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

2

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.

a) Duyệt trước (gốc – trá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:

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

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.

a) Duyệt trước (gốc – trá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:

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

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 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:

Xử lí nút

góc i (gốc).

2

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

1

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

3

b) Duyệt giữa (trái – gốc – 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.

1

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) Duyệt giữa (trái – gốc – 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.

1

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.

b) Duyệt giữa (trái – gốc – 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:

Xử lí nút 7.

2

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

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

3

b) Duyệt giữa (trái – gốc – 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:

Xử lí nút 7.

2

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

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

3

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 phải (phải).

2

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

1

Xử lí nút

gốc i (gốc).

3

c) Duyệt sau (trái – phả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.

1

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.

c) Duyệt sau (trái – phả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.

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) Duyệt sau (trái – phả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 phải của nút 7: Duyệt cây gốc 3.

2

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.

c) Duyệt sau (trái – phả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:

Xử lí nút 7.

3

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 Làm SGK tr.35

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

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?

Phép toán duyệt giữa.

CÀI ĐẶT CÁC PHÉP TOÁN

DUYỆT CÂY NHỊ PHÂN

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