Giáo án chuyên đề Khoa học máy tính 12 cánh diều Bài 1: Giới thiệu 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

- Từ hoạt động Khởi động, GV trình bày một số khái niệm cơ bản về cây, cấu trúc dữ liệu cây.

- GV yêu cầu HS làm việc độc lập và trả lời các câu hỏi:

+ Em hãy quan sát Hình 3 trình bày ý tưởng chủ đạo của các thuật ngữ:

• Nút trong.

• Nút lá.

• Khoá.

• Đường đi.

• Độ sâu/mức của một nút.

• Chiều cao cây.

+ Theo em, cây có những ứng dụng thực tế nào?

- GV yêu cầu HS thực hiện phần Thực hành.

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

- HS tìm hiểu nội dung mục 1 SGK tr.29 – 31 và trả lời các câu hỏi mà GV đưa ra.

- 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 lần lượt trả lời các câu hỏi.

- HS khác nhận xét, bổ sung. 

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

- Từ câu trả lời của HS, GV nhận xét, đánh giá quá trình HS thực hiện nhiệm vụ.

- GV chính xác hoá lại các nội dung kiến thức.

- GV chuyển sang nội dung tiếp theo.

1. Khái niệm cây

- Cấu trúc dữ liệu cây là một cấu trúc phân cấp gồm một tập hợp hữu hạn các nút, giữa các nút có mối quan hệ phân cấp gọi là quan hệ cha-con:

+ Trên cây có một nút đặc biệt gọi là nút gốc. 

+ Mỗi nút có thể không có hoặc có ít nhất một nút con nhưng chỉ có duy nhất một nút cha, ngoại trừ nút gốc là không có nút cha. 

+ Cây không chứa nút nào được gọi là cây rỗng. 

+ Cây không rỗng có thể được định nghĩa đệ quy như sau:

• Bước cơ sở: Cây có duy nhất một nút r và r được gọi là nút gốc của cây này.

• Bước quy nạp: Giả sử , ,…,  là các cây với nút gốc lần lượt là , ,…, . Ta có thể xây dựng cây mới bằng cách đặt r làm nút cha của các nút , ,…, . Trong cây này:

• r là nút gốc và , ,…,  là các cây con của nút gốc r. 

• Các nút , ,…,  được gọi là nút con của nút r, mỗi nút con này được nối với r bởi một cạnh. 

Hình 2. Cấu trúc đệ quy của cây

- Một số thuật ngữ trên cây:

Hình 3. Minh hoạ các thuật ngữ trên cây

+ Nút trong là nút có ít nhất một nút con.

+ Nút lá là nút không có nút con nào. 

+ Mỗi nút của cây thường được gán một khoá là một giá trị liên quan đến thông tin cần được cất giữ trong nút đó.

+ Đường đi là một dãy các cạnh liên tiếp nhau trên cây. 

Ví dụ: Nếu , ,…,  là dãy nút đôi một khác nhau trên cây sao cho nút  là cha của nút  với 1 ≤ i < k, thì dãy này biểu diễn đường đi duy nhất từ nút  tới nút . 

+ Độ sâu hay mức của một nút là số lượng cạnh trên đường đi duy nhất từ gốc r đến nút đó. 

+ Chiều cao cây là độ sâu của nút lá có độ sâu lớn nhất.

- Một số ứng dụng thực tế của cây: 

+ Cây phả hệ.

Cây phả hệ nhà Hậu Lê

+ Sơ đồ lịch thi đấu.

Sơ đồ lịch thi đấu tứ kết EURO 2024

+ Sơ đồ phân cấp quản lí.

Hình 4. Một cây phân cấp quản lí

+ Mục lục của một quyển sách.

Hình 5. Ví dụ cây mục lục một quyển sách

Thực hành: Em hãy vẽ cây biểu diễn phân cấp một phần các thư mục trong máy tính của mình để mô tả cấu trúc tổ chức lưu trữ thư mục mẹ, thư mục con và các tệp trong máy tính. Em hãy tính chiều cao của cây và chỉ ra nút nào là nút lá, nút trong, nút gốc.

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 đọc và thực hiện cá nhân Hoạt động 2 SGK tr.31:

Đội tuyển Argentina đã giành chức vô địch World Cup 2022. Dựa vào hình minh hoạ ở Hình 6, em hãy vẽ cây trong tin học biểu diễn kết quả thi đấu World Cup 2022 các trận đấu từ vòng đấu loại 1:16 đến hết trận chung kết với cấu trúc như sau:

• Gốc của cây là đội vô địch.

• Mỗi nút ngoại trừ các nút là có đúng hai nút con tương ứng với hai đội tham gia trận đấu loại trực tiếp. Khoá của các nút trong là tên đội bóng giành chiến thắng. Khoá của các nút lá là tên các đội bóng ghép đấu với nhau ở vòng 1:16.

Hình 6. Kết quả các vòng đấu loại

- Từ Hoạt động 2, GV trình bày một số khái niệm của cây nhị phân.

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

+ 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?

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

- HS tìm hiểu nội dung mục 2 SGK tr.31 – 32 và trả lời các câu hỏi mà GV đưa ra.

- 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 lần lượt trả lời các câu hỏi.

- HS khác nhận xét, bổ sung.

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

- Từ câu trả lời của HS, GV nhận xét, đánh giá quá trình HS thực hiện nhiệm vụ.

- GV chính xác hoá lại các nội dung kiến thức. 

- GV chuyển sang nội dung tiếp theo.

2. Khái niệm cây nhị phân

- Hình 7 là một ví dụ các nút biểu diễn trận đấu giữa Brasil và Hàn Quốc mà Brasil là đội giành chiến thắng, sau đó là trận đấu giữa Brasil và Croatia mà Croatia là đội giành chiến thắng.

Hình 7. Minh hoạ các nút cây nhị phân biểu diễn trận đấu Brasil – Hàn Quốc và trận đấu Brasil – Croatia

Cây nhị phân là cây mà mỗi nút có nhiều nhất là hai nút con.

Hình 8. Một số ví dụ cây nhị phân

- Vì mỗi nút chỉ có không quá hai nút con, ta gọi tương ứng chúng là nút con trái và nút con phải của nút đó:

Hình 9. Ví dụ nút con trái và nút con phải trong cây nhị phân

+ Nút con trái là nút gốc của cây con trái. 

+ Nút con phải là nút gốc của cây con phải. 

Mỗi nút của cây nhị phân hoặc là không có nút con, hoặc chỉ có nút con trái, hoặc chỉ có nút con phải, hoặc có cả nút con trái và nút con phải:

• Một nút không có nút con trái là nút có cây con trái là cây rỗng.

• Một nút không có nút con phải là nút có cây con phải là cây rỗng. 

• Nút lá là nút có hai cây con trái và phải đều rỗng.

- Một số dạng đặc biệt của cây nhị phân:

+ Cây nhị phân hoàn chỉnh là cây nhị phân thoả mãn:

• Tất cả các mức, ngoại trừ mức cuối cùng, đều phải lấp đầy hoàn toàn các nút.

• Tất cả các nút ở mức cuối cùng phải nằm lệch sang trái nhất có thể được.

Hình 10. Ví dụ một cây nhị phân hoàn chỉnh

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

Một cây nhị phân hoàn hảo chiều cao h sẽ có đúng  nút. 

Hình 11. Ví dụ một cây nhị phân hoàn hảo

Hướng dẫn trả lời câu hỏi Hoạt động 2 SGK tr.31:

Nhận xét: Mỗi nút của cây ngoại trừ các nút lá thì có đúng hai nút con.

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 đưa ra ý tưởng biểu diễn một cây nhị phân hoàn hảo bởi mảng, sau đó yêu cầu HS hoạt động cá nhân và trả lời câu hỏi:

+ Từ cách gán nhãn đã nêu, em hãy xác định nhãn của nút cha, nút con trái, nút con phải của mỗi nút có nhãn là i.

+ Làm thế nào để biến đổi một cây nhị phân tổng quát có chiều cao h thành cây nhị phân hoàn chỉnh?

- GV kết luận và trình bày cách biểu diễn cây nhị phân bằng mảng một chiều.

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

- HS tìm hiểu nội dung mục 3 SGK tr.33 – 34 và trả lời các câu hỏi mà GV đưa ra.

- 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 lần lượt trả lời các câu hỏi.

- HS khác nhận xét, bổ sung.

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

- Từ câu trả lời của HS, GV nhận xét, đánh giá quá trình HS thực hiện nhiệm vụ.

- GV chính xác hoá lại các nội dung kiến thức. 

- GV chuyển sang nội dung tiếp theo.

3. Biểu diễn cây nhị phân bằng mảng một chiều

- Xét cây nhị phân hoàn hảo T có n nút, trong đó mỗi nút chứa một giá trị:

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

+ Đặt tương ứng cây T với mảng một chiều 
A[0, …, n – 1], trong đó phần tử A[i](0   i  
n – 1) là giá trị cất giữ trong nút có nhãn là i trên cây T.

A[i] có nút con trái A[2 * i + 1] 
và nút con phải A[2 * i + 2]

Hình 11. Ví dụ biểu diễn một cây 
nhị phân hoàn hảo bởi mảng

+ Do cây nhị phân có mối quan hệ cha-con nên với mỗi nút có nhãn là i cần xác định được nhãn của nút cha, nút con trái, nút con phải của nó:

• Nhãn nút cha là [(i – 1) / 2] với i  1.

• Nhãn nút con trái là 2 * i + 1 với 2 * i + 1 < n.

• Nhãn nút con phải là 2 * i + 2 với 2 * i + 2 < n .

Ví dụ: Với cây ở Hình 11, nút với nhãn là 1 có:

• Nút cha là [(1 – 1) / 2] = 0.

• Nút con trái có nhãn là 2 * 1 + 1 = 3.

• Nút con phải có nhãn là 2 * 1 + 2 = 4.

- Một cây nhị phân tổng quát có chiều cao h được biến đổi thành cây nhị phân hoàn chỉnh bằng cách thêm các nút giả vào mỗi mức để mỗi mức có đầy đủ các nút, ngoại trừ mức h không được có các nút giả cuối cùng (các nút sát phải).