Giáo án chuyên đề Khoa học máy tính 12 kết nối Bài 6: 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 giới thiệu: Các sơ đồ trong hoạt động khởi động đều có cấu trúc cây.

- GV yêu cầu HS đọc, trao đổi và thảo luận theo nhóm (4 người/1 nhóm) tìm hiểu và trình bày các nội dung:

+ Các khái niệm liên quan đến cấu trúc cây được thể hiện trong Hình 6.2.

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

- GV chia lớp thành 3 tổ:

+ Tổ 1: Thảo luận về Hình 6.1. a)

+ Tổ 2: Thảo luận về Hình 6.1. b)

+ Tổ 3: Thảo luận về Hình 6.1. c)

- Trong mỗi tổ HS hoạt động nhóm 4 người, thực hiện nhiệm vụ mỗi nhóm:

Chỉ ra các khái niệm chính của cây tương ứng. 

• Gốc của cây.

• Các nút trên cây, nút lá, nút trong.

• Quan hệ cha con.

• Quan hệ anh em.

• Cây con.

• Mức của các nút.

• Bậc của nút.

• Chiều cao của cây.

- 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.24 SGK:

Câu 1. Tìm thêm các ví dụ cấu trúc cây.

Câu 2. Vẽ sơ đồ cây cho các biểu thức toán học sau:

a) (x + y)*(x - (y + z)/t).

b) x + (y + (z + t)/(u - v)).

Câu 3. Tính chiều cao của các cây trong Hình 6.3.

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ấu trúc cây bao gồm các nút có quan hệ cha - con. Cây có một nút gốc. Một

nút có thể có nhiều nút con. Nút gốc không có nút cha, mỗi nút còn lại chỉ có

một nút cha.

+ Cấu trúc cây có nhiều ứng dụng trên thực tế và trong Khoa học máy tính.

+ Cây nhị phân là cây mà mỗi nút có nhiều nhất hai nút con, được gọi là nút con trái và nút con phải.

1. Cấu trúc cây và cây nhị phân

- Cây (tree) bao gồm một tập hợp các nút (node) chứa thông tin, có kết nối với nhau, thường được gọi là quan hệ cha – con. 

+ Mỗi nút cha có thể kết nối với nhiều nút con. 

+ Mỗi nút chỉ có thể kết nối với một nút cha. 

+ Mỗi cây có một nút đóng vai trò gốc (root). Nút gốc không có nút cha (Hình 6.2).

- Một số khái niệm liên quan đến cấu trúc cây:

• Nút lá (leaf node): nút không có nút con.

• Nút trong (inner node) hay nút nhánh (branch node): nút có nút con.

• Cây con (sub tree) gồm: Nút cùng với các nút con bắt đầu từ nút đó.

• Mức (level) của nút: số cạnh cần đi để về tới nút gốc.

Mức của nút gốc là 0. Mức của nút con bằng mức của nút cha cộng 1.

• Nút anh em (sibling node): các nút có cùng nút cha.

• Chiều cao (height) của cây: độ dài đường đi đến nút lá sâu nhất.

• Bậc (degree) của một nút: số các nút con của nó. 

Bậc của cây là bậc lớn nhất của các nút.

- Cây nhị phân (binary tree) là cây mà mọi nút có tối đa hai nút con là nút con trái và nút con phải.

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

Câu 1. Một số ví dụ khác của cây có thể là:

Mô hình gia phả dòng họ.

Mô hình tổ chức của cơ quan.

Mô hình các chương, mục, bài học của một cuốn sách.

Câu 2. Sơ đồ cây tương ứng như sau:

a) 

b)

Câu 3. Chiều cao của cây: 

a) 4; 

b) 5.

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

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

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

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

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:

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:

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

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 chú ý:

Trong phần này tất cả các cây nhị phân đều được hiểu là cây nhị phân hoàn chỉnh và được biểu diễn bằng mảng một chiều A cho trước.

- GV chia lớp thành 3 tổ, mỗi tổ sẽ tìm hiểu một thuật toán duyệt cây nhị phân:

+ Tổ 1: Duyệt trước

+ Tổ 2: Duyệt sau.

+ Tổ 3: Duyệt giữa.

- Trong mỗi tổ, HS hoạt động theo nhóm 4 người, tìm hiểu và trình bày các vấn đề:

• Ý tưởng duyệt.

• Mô tả cách duyệt trên ví dụ.

• Viết đoạn chương trình mô tả thuật toán duyệt.

…………………

3. Các thuật toán duyệt cây nhị phân.

a) Duyệt trước (preorder traversal)

Cây con có nút gốc v được gọi là "cây v" (Hình 6.9). 

- Ý tưởng: bắt đầu từ nút gốc, sau đó duyệt cây con trái. Duyệt xong cây con trái thì chuyển sang duyệt cây con phải. Đoạn mã giả sau là thuật toán duyệt trước cây v. Lời gọi duyệt chính là  preorder (root).

- Ví dụ: cây nhị phân hoàn chỉnh có biểu diễn là mảng A=[4,1,7,0,2,6,8]. 

Lệnh duyệt trước bắt đầu từ gốc sẽ duyệt các nút của cây lần lượt theo mũi tên (Hình 6.10).

- Đoạn chương trình:

Hàm cài đặt thuật toán duyệt trước trên Python có dạng preorder(A, k), trong đó k là chỉ số nút bắt đầu duyệt, A là mảng biểu diễn cây nhị phân tương ứng.

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