Kênh giáo viên » Giáo án tích hợp NLS chuyên đề Tin học 12 Khoa học máy tính (cả năm)

Giáo án NLS chuyên đề Tin học 12 KHMT Bài 6: Cây nhị phân

Xem mẫu

Tải về

Giáo án chuyên đề NLS Tin học 12 - Khoa học máy tính (bộ SGK thống nhất từ 2026 - 2027) Bài 6: Cây nhị phân. Với năng lực số được tích hợp, tiết học sẽ giúp học sinh tăng cường khả năng ứng dụng công nghệ, tin học vào việc tìm hiểu các chuyên đề học tập. KHBD này là file word, tải về dễ dàng.

=> Giáo án tích hợp NLS chuyên đề Tin học 12 Khoa học máy tính

Các tài liệu bổ trợ

Giáo án NLS chuyên đề Tin học 12 KHMT Bài 6: Cây nhị phân

Ngày soạn:…/…/…

Ngày dạy:…/…/…

CHUYÊN ĐỀ 2: TÌM HIỂU CÂY TÌM KIẾM NHỊ PHÂN

TRONG SẮP XẾP VÀ TÌM KIẾM

BÀI 6: CÂY NHỊ PHÂN

(2 tiết)

I. MỤC TIÊU

1. Kiến thức

Sau bài học này, HS sẽ:

Nêu được khái niệm cây và các định nghĩa có liên quan.
Trình bày mô hình cây nhị phân.
Phân loại cây nhị phân.
Biểu diễn cây nhị phân hoàn chỉnh bằng mảng một chiều.
Trình bày các thuật toán duyệt trên cây nhị phân.

2. Năng lực

Năng lực chung:

Năng lực giao tiếp và hợp tác: Biết lựa chọn hình thức làm việc nhóm với quy mô phù hợp với yêu cầu và thực hiện tốt nhiệm vụ.
Năng lực tự chủ và tự học: Chủ động học tập, tìm hiểu nội dung bài học, biết lắng nghe và trả lời nội dung trong bài học.
Giải quyết vấn đề và sáng tạo: Trả lời được các câu hỏi, giải quyết được các vấn đề với sự hỗ trợ của công nghệ thông tin và truyền thông.

Năng lực Tin học:

Nêu được khái niệm cây, cây nhị phân.
Biểu diễn được cây nhị phân bằng mảng một chiều.
Trình bày và mô phỏng được các phép toán duyệt trước, duyệt giữa, duyệt sau cây nhị phân bằng biểu diễn trực quan.

Năng lực số:

3.4.NC1a: Lập trình (HS tự viết các hàm/chương trình Python mô tả thuật toán duyệt cây nhị phân).
2.1.NC1a: Tương tác thông qua công nghệ số (HS xem video được tạo bởi công cụ AI và trả lời câu hỏi, sử dụng máy tính cá nhân hoặc thiết bị di động có kết nối Internet để làm bài tập trắc nghiệm củng cố trên môi trường số).
5.3.NC1a: Sử dụng sáng tạo công nghệ số (HS sử dụng Python IDE để thực thi, kiểm thử và cải tiến chương trình biểu diễn/duyệt cây nhị phân).
1.3.NC1a: Quản lí dữ liệu, thông tin và nội dung số (HS tổ chức, lưu trữ và truy xuất các tệp chương trình Python của bài học trong môi trường lập trình có cấu trúc).
1.2.NC1a: Đánh giá dữ liệu, thông tin và nội dung số (HS đối chiếu kết quả chương trình với thứ tự duyệt theo thuật toán và dữ liệu của bài toán để đánh giá tính đúng đắn).
6.2.NC1a: Sử dụng trí tuệ nhân tạo (HS sử dụng công cụ AI hoặc sản phẩm số do GV cung cấp để tiếp nhận thông tin, trả lời câu hỏi đơn giản).
1.1.NC1a: Duyệt, tìm kiếm và lọc dữ liệu, thông tin và nội dung số (HS tiếp cận, khai thác được thông tin từ nguồn học liệu số dưới sự hướng dẫn của GV).

Năng lực AI:

12.A1.2: Con người trong hệ thống AI (HS phân tích vai trò của bản thân và AI trong quá trình ra quyết định; tự xây dựng cách giải, AI chỉ hỗ trợ gợi ý/giải thích khi cần.).
12.A3.1: Trách nhiệm công dân trong xã hội có AI (HS sử dụng AI an toàn, trung thực và có trách nhiệm; kiểm chứng gợi ý AI trước khi sử dụng, không sao chép nguyên văn mã nguồn).

3. Phẩm chất

Chăm chỉ: Tích cực tìm tòi và sáng tạo trong học tập.
Trung thực: Thực hiện đúng phần việc của bản thân và hợp tác làm việc nhóm khi được giao nhiệm vụ. Có ý thức báo cáo kết quả một cách chính xác.
Trách nhiệm: Hoàn thành các bài tập theo yêu cầu của GV thông qua hệ thống câu hỏi, phiếu học tập, thông qua sản phẩm.

II. THIẾT BỊ DẠY HỌC VÀ HỌC LIỆU

1. Đối với giáo viên

SGK, KHBD Chuyên đề học tập Tin học 12 – Định hướng Khoa học máy tính.
Phòng thực hành máy tính cài đặt sẵn môi trường lập trình Python (IDLE, PyCharm, VS Code,…) và có kết nối Internet, máy trình chiếu.
Học liệu số & Công cụ AI:
Bộ câu hỏi trắc nghiệm trên phần mềm Quizizz/website kenhhoctap.edu.vn hoặc phiếu bài tập số.
Video AI được tạo bằng các công cụ AI để khởi động bài học.
Công cụ Chatbot AI (ChatGPT/Gemini).

2. Đối với học sinh

SGK Chuyên đề học tập Tin học 12 – Định hướng Khoa học máy tính.
Vở ghi.

III. TIẾN TRÌNH DẠY HỌC

1. HOẠT ĐỘNG KHỞI ĐỘNG

a. Mục tiêu: HS nhận ra được một mô hình dữ liệu mới khác với kiểu dữ liệu mảng đã học.

b. Nội dung: HS quan sát các hình ảnh, suy nghĩ, thảo luận và trả lời câu hỏi.

c. Sản phẩm học tập: Câu trả lời của HS.

d. Tổ chức thực hiện:

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

- GV yêu cầu xem video AI được thiết kế để phục vụ bài dạy và trả lời câu hỏi xuất hiện trong video đó.

- GV cho HS thảo luận theo nhóm đôi.

- GV yêu cầu HS quan sát và trả lời câu hỏi Khởi động SGK trang 23:

1. Quan sát các sơ đồ biểu diễn thông tin trong Hình 6.1, em có nhận xét gì?

2. Các sơ đồ này có những điểm gì chung?

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

- HS xem video và suy nghĩ câu trả lời.

- HS tiếp nhận, thực hiện nhiệm vụ.

- GV 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 trình bày câu trả lời, các HS khác chú ý lắng nghe và nhận xét.

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

- GV nhận xét, đánh giá và kết luận.

[6.2.NC1a: HS sử dụng công cụ AI hoặc sản phẩm số do GV cung cấp để tiếp nhận thông tin, trả lời câu hỏi đơn giản.

2.1.NC1a: HS thực hiện các tương tác cơ bản với học liệu số (xem video, trả lời câu hỏi trên môi trường số).

1.1.NC1a: HS tiếp cận, khai thác được thông tin từ nguồn học liệu số dưới sự hướng dẫn của GV.]

- GV đánh giá kết quả của HS, dẫn dắt HS vào bài học mới: Trong chuyên đề này, ta đi tìm hiểu về cây tìm kiếm nhị phân trong sắp xếp và tìm kiếm. Trước hết ta đi tìm hiểu thế nào là cây, cây nhị phân, cách biểu diễn cây nhị phân bằng mảng một chiều - Bài 6: Cây nhị phân.

2. HOẠT ĐỘNG HÌNH THÀNH KIẾN THỨC

Hoạt động 1. Tìm hiểu cấu trúc cây và cây nhị phân

a. Mục tiêu: HS nêu được khái niệm và một số định nghĩa của cấu trúc cây tổng quát.

b. Nội dung: GV giao nhiệm vụ; HS tìm hiểu nội dung mục 1, kết hợp với những hiểu biết về thực tiễn, thảo luận nhóm thực hiện nhiệm vụ.

c. Sản phẩm: Hình thành được kiến thức bài học. HS nhận biết cây và cây nhị phân.

d. Tổ chức thực hiện:

…………………………………………..

Hoạt động 2. Tìm hiểu cây nhị phân và cách biểu diễn cây nhị phân bằng mảng một chiều

a. Mục tiêu: HS phân biệt được định nghĩa cây nhị phân hoàn hảo, hoàn chỉnh và cách biểu diễn cây nhị phân hoàn chỉnh bằng mảng một chiều.

b. Nội dung: GV giao nhiệm vụ; HS tìm hiểu nội dung mục 2, kết hợp với những hiểu biết về thực tiễn, thảo luận nhóm thực hiện nhiệm vụ.

c. Sản phẩm: Hình thành kiến thức bài học. HS biểu diễn cây nhị phân bằng mảng một chiều.

d. Tổ chức thực hiện:

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

DỰ KIẾN SẢN PHẨM

NLS/AI

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

- GV giới thiệu, giải thích về:

Cây nhị phân hoàn chỉnh, cây nhị phân hoàn hảo và cây nhị phân không hoàn chỉnh.

Cây nhị phân hoàn chỉnh (complete) là cây nhị phân mà có thể đi một lượt tất cả các nút của cây lần lượt theo các mức, bắt đầu từ gốc, mỗi mức duyệt từ trái sang phải mà không bị đứt quãng.

- GV chia lớp thành các nhóm (4 người/1nhóm) thực hiện nhiệm vụ:

Nêu cách biểu diễn cây nhị phân hoàn chỉnh với mảng một chiều theo 2 cách sau:

+ Cách 1: Cho trước cây nhị phân hoàn chỉnh, chỉ ra mảng một chiều tương ứng.

+ Cách 2: Cho trước mảng một chiều, cần vẽ cây nhị phân hoàn chỉnh tương ứng.

- 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 Củng cố tr.26 SGK:

Câu 1. Cho mảng A = [2, 1, 8, 10, 0, 5, 9], biểu diễn cây nhị phân hoàn chỉnh. Hãy chỉ ra dãy các nút đi từ nút lá 9 về nút gốc 2.

Câu 2. Cho mảng A có 14 phần tử, biểu diễn cây nhị phân hoàn chỉnh. Tính chiều cao của cây nhị phân này.

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 trả lời các câu hỏi mà GV đưa ra.

- 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

- GV mời đại diện các nhóm báo cáo kết quả thảo luận.

- GV mờ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ừ kết quả thảo luận của nhóm, 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 kết luận:

+ Cây nhị phân hoàn chỉnh có thể được biểu diễn bằng mảng một chiều có số phần từ bằng số nút của cây. Ngược lại, màng một chiều có thể biểu diễn cây nhị phân hoàn chỉnh.

- GV giao về nhà HS tìm hiểu phần Lưu ý (SGK -tr.26) về cây nhị phân hoàn chỉnh đã biến đổi.

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

- Cây nhị phân hoàn chỉnh (complete) nếu tại mức i () có nút và tại mức h thì các nút liên tục tính từ trái qua phải, có thể khuyết một số nút bên phải, với h là chiều cao của cây.

kenhhoctap

- Cây nhị phân hoàn hảo là cây hoàn chỉnh và bậc cao nhất của cây có đủ nút.

+ Mỗi mức k sẽ có đủ 2^k nút.

+ Tổng số nút của cây hoàn hảo có chiều cao h là: .

kenhhoctap

- Thông thường, cấu trúc của cây là cấu trúc nút liên kết. Đối với cây nhị phân, cấu trúc cây (tree) có thuộc tính root cho biết nút gốc của cây; cấu trúc nút (node) có thuộc tính left cho biết nút con trái và thuộc tính right cho biết nút con phải.

*) Cho trước cây nhị phân hoàn chỉnh, chỉ ra mảng một chiều tương ứng.

- Cây nhị phân hoàn chỉnh được đánh chỉ số: bắt đầu từ 0 (nút gốc), sau đó đánh chỉ số lần lượt theo các nút ở từng mức, từ trái sang phải, cho đến nút cuối cùng của cây (Hình 6.6).

+ Cây rỗng tương ứng với mảng rỗng.

+ Nút gốc có chỉ số 0. Nếu nút có chỉ số k thì nút con trái có chỉ số 2k+1 và nút con phải có chỉ số 2k+2 và nút cha có chỉ số (k-1)/2.

kenhhoctap

*) Cho trước mảng một chiều, cần vẽ cây nhị phân hoàn chỉnh tương ứng.

- Nút gốc của cây sẽ tương ứng phần tử đầu tiên của mảng với chỉ số 0.

- Các phần tử tiếp theo tương ứng với chỉ số các nút của cây theo thứ tự từng mức, từ trái sang phải.

kenhhoctap

Hướng dẫn trả lời câu hỏi Củng cố

Câu 1. Cây nhị phân hoàn chỉnh tương ứng A = [2, 1, 8, 10, 0, 5, 9] có dạng như sau:

kenhhoctap

Dãy nút đi từ nút lá 9 về gốc là: 9, 8, 2.

Câu 2. Cây nhị phân hoàn chỉnh có 14 nút sẽ có dạng như sau:

kenhhoctap

Cây nhị phân này có chiều cao bằng 3.

- 5.3.NC1a: HS dùng Python IDE để kiểm tra cách ánh xạ mảng một chiều với cây nhị phân hoàn chỉnh.
- 1.2.NC1a: HS đối chiếu cây vẽ được với mảng và quy tắc chỉ số để kiểm tra kết quả.

Hoạt động 3: Tìm hiểu một số thuật toán duyệt cây nhị phân

a. Mục tiêu: HS biết và thực hiện thủ công và bằng lập trình các thuật toán duyệt trước, duyệt giữa và duyệt sau trên cây nhị phân hoàn chỉnh.

b. Nội dung: GV giao nhiệm vụ; HS tìm hiểu nội dung mục 3, kết hợp với những hiểu biết về thực tiễn, thảo luận nhóm thực hiện nhiệm vụ.

c. Sản phẩm: Hình thành kiến thức bài học. HS lập trình các thuật toán duyệt trước, duyệt giữa và duyệt sau cây nhị phân hoàn chỉnh.

d. Tổ chức thực hiện:

…………………………………………..

3. HOẠT ĐỘNG LUYỆN TẬP

a. Mục tiêu: Giúp HS hệ thống lại kiến thức đã học.

b. Nội dung: GV giao nhiệm vụ cho HS, HS hoàn thành phiếu bài tập.

c. Sản phẩm học tập: Phiếu bài tập.

d. Tổ chức thực hiện:

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

- GV tổng hợp các kiến thức cần ghi nhớ cho HS.

- GV tạo phiếu bài tập số bằng Google Forms/Liveworksheets/Azota hoặc tổ chức trò chơi trắc nghiệm trên Quizizz/website kenhhoctap.edu.vn để củng cố toàn bài.

- GV cung cấp mã QR hoặc đường Links cho HS chơi và làm bài tập.

- GV yêu cầu HS hoạt động cá nhân hoàn thành bài tập phần Luyện tập SGK trang 29.

Câu 1. Cây nào sau đây là hoàn hảo? Cây nào là hoàn chỉnh? Cây nào không là hoàn hảo và hoàn chỉnh?

kenhhoctap

Câu 2. Cây nhị phân gọi là đầy đủ nếu mỗi nút của nó hoặc là nút lá hoặc có đúng hai nút con. Khẳng định "Cây nhị phân đầy đủ sẽ luôn là hoàn chỉnh hoặc hoàn hảo" là đúng hay sai?

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

- HS suy nghĩ, hoàn thành các bài tập GV yêu cầu.

- GV quan sát và hỗ trợ, hướng dẫn.

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

- HS trả lời nhanh câu hỏi trắc nghiệm.

- Mỗi bài tập GV mời 1 đến 2 HS trình bày. Các HS khác chú ý chữa bài, theo dõi nhận xét bài làm của các bạn.

Gợi ý đáp án:

PHẦN TRẮC NGHIỆM