Giáo án điện tử chuyên đề Khoa học máy tính 12 chân trời Bài 2.1: Cây và cây nhị phân

CHÀO MỪNG

CẢ LỚP ĐẾN VỚI

BÀI HỌC NÀY!

KHỞI ĐỘNG

Quan sát sơ đồ tổ chức của một công ty ở Hình 1 và cho biết các phòng ban chức năng trong công ty được tổ chức như thế nào.

Hình 1. Sơ đồ tổ chức của một công ty theo chức năng

BÀI 2.1: CÂY VÀ

CÂY NHỊ PHÂN

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

NỘI DUNG BÀI HỌC

01

Giới thiệu cây, cây nhị phân

02

Biểu diễn

cây nhị phân

PHẦN 1.

GIỚI THIỆU CÂY, CÂY NHỊ PHÂN

1. GIỚI THIỆU CÂY, CÂY NHỊ PHÂN

Cấu trúc dữ liệu

Tuyến tính: bao gồm các phần tử tạo thành một dãy nối tiếp nhau và thông thường thao tác duyệt được thực hiện tuần tự theo trình tự của các phần tử. Mỗi phần tử có nhiều nhất một phần tử kề đi sau nó.

Phi tuyến tính: bao gồm các phần tử không tạo thành một dãy nối tiếp nhau. Mỗi phần tử có thể có nhiều phần tử kề đi sau nó. → Cấu trúc dữ liệu cây.

Nghiên cứu nội dung mục 1.a SGK và trả lời câu hỏi:

• Nêu khái niệm cây và các khái niệm cơ bản về cây.
• Chỉ ra các khái niệm chính của cây tương ứng.

a) Cây

Cây: một tập hợp rỗng hoặc bao gồm nhiều phần tử được gọi là nút.

Mỗi nút cha có thể có nhiều nút con và mỗi nút con chỉ có một nút cha.

Một cây chỉ có một nút gốc là nút không có nút cha.

Cây rỗng: cây không có nút nào. Ngược lại, các nút có liên kết “cha – con” với nhau.

a) Cây

Biểu diễn nút trên cây

Nút cha nằm ở trên và nút con nằm ở dưới, chúng kết nối với nhau bằng một cạnh.

Một nút và các nút nằm ở phía dưới nút này liên kết “cha – con” với nhau tạo thành cây con có nút gốc là nút này.

Cây có cấu trúc đệ quy: một cây có thể chứa các cây con.

Một số khái niệm cơ bản về cây:

Nút gốc:

• Nút đầu tiên, thường là điểm xuất phát cho việc truy cập và duyệt cây.
• Tất cả các nút khác trong cây sẽ nằm dưới nút gốc theo một cấu trúc phân nhánh, gọi là quan hệ “cha – con”:
• Mỗi nút trong cây có thể không có hoặc có một số nút con.
• Một nút có nút con được gọi là nút cha.
• Nút gốc (của cây) không có nút cha. Các nút còn lại chỉ có một nút cha. Nút cha và nút con được kết nối bằng một cạnh trong hình vẽ của cây.

Nút lá

Là nút không có nút con.

Nếu cây chỉ có một nút thì nút gốc cũng là nút lá.

Nút nhánh (nút trong)

Là nút có ít nhất một nút con.

Nếu cây có nhiều hơn một nút thì nút gốc cũng là nút trong.

Mức của một nút

• Mức của nút gốc bằng 0 (quy ước).

• Mức của một nút (khác nút gốc) bằng mức của nút cha cộng 1.

Chiều cao của cây

• Là mức lớn nhất của các nút lá.

• Cây rỗng có chiều cao là -1.

Đường đi

Từ nút gốc đến nút x là dãy các cạnh từ nút gốc đến nút x.

• Cây gốc 14 có nút gốc 14, nút này có ba cây con là cây gốc 7, cây gốc 23 và cây gốc 8. Cây gốc 8 có nút gốc 8, nút này có hai cây con là cây gốc 2 và cây gốc 27.
• Nút 14 là nút cha của nút 7, nút 7 là nút con của nút 14.
• Nút 24 là nút lá vì không có các nút con.

• Nút 8 là nút trong vì nó có các nút con (là nút 2 và nút 27).
• Mức của nút gốc 14 là 0 (theo quy ước), mức của nút 7 là 1, mức của nút 24 là 2.
• Cây gốc 14 có chiều cao là 2.
• Đường đi từ nút 14 đến nút 26 là cạnh (14-7) và cạnh (7-26), kí hiệu là [14, 7, 26].

Hoạt động Làm tr.28 SGK

Cho các cây như ở Hình 3. Cho biết:

a) Nút gốc, nút nhánh, nút lá ở Hình 3a.

b) Mức và chiều cao của cây trong Hình 3b.

Hình 3a.

Hình 3b.

Hình 3. Biểu diễn cây

Hình 3a.

Hình 3b.

Hình 3. Biểu diễn cây

Nút gốc: 2.

Nút nhánh: 24, 11, 20, 8.

Nút lá: 83, 3, 10, 15, 9.

Mức của nút 2 là 0.

Mức của các nút 24, 11 là 1.

Mức của các nút 8, 3, 8,9 là 2.

Chiều cao của cây là 2.

• Cây là một tập hợp rỗng hoặc bao gồm nhiều phần tử được gọi là nút.

• Cây rỗng là cây không có nút nào. Ngược lại, các nút có liên kết “cha – con” với nhau: mỗi nút cha có thể có nhiều nút con và mỗi nút con chỉ có một nút cha; một cây chỉ có một nút gốc là nút không có nút cha.

GHI NHỚ

Nghiên cứu nội dung mục 1.b SGK và trả lời câu hỏi:

• Thế nào là cây nhị phân?
• Một số dạng đặc biệt của cây nhị phân.
• Một số tính chất của cây nhị phân.

b) Cây nhị phân

b) Cây nhị phân

Khái niệm: Cây nhị phân là cây mà mỗi nút của cây có tối đa hai cây con (cây con trái và cây con phải).

Một số dạng đặc biệt của cây nhị phân: Gọi h là chiều cao của cây nhị phân.

Cây nhị phân hoàn chỉnh là cây nhị phân mà tại mức i (0 ≤ i < h) có nút và tại mức h thì các nút được điền từ trái qua phải.

Cây nhị phân hoàn hảo là cây nhị phân mà tại mức i (0 ≤ i ≤ h) có nút.

Tính chất 1: Số nút của mức i là (0 ≤ i ≤ h).

Tính chất 2: Số nút lá là .

Tính chất 3: Số nút trong là .

Tính chất 4: Số nút của cây là .

Tính chất 5: (Suy ra từ Tính chất 4).

Một số tính chất của cây nhị phân

Hoạt động Làm tr.29 SGK

Cho biết cây nào ở Hình 3 là cây nhị phân.

Hình 3. Biểu diễn cây

Hình 3a.

Hình 3b.

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

GHI NHỚ

PHẦN 2.

BIỂU DIỄN

CÂY NHỊ PHÂN

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

Nghiên cứu nội dung mục 2.a SGK và trả lời câu hỏi: Cách biểu diễn cây nhị phân bằng mảng một chiều.

Đánh chỉ số cho các nút của cây bắt đầu từ nút gốc.

Cây nhị phân có thể được lưu trữ trong mảng một chiều có () phần tử như sau:

• Nếu cây rỗng thì mảng là rỗng.
• Nút gốc có chỉ số 0.
• Nếu nút có chỉ số i thì nút con trái có chỉ số là 2i + 1 và nút con phải có chỉ số là 2i + 2.
• Nút có chỉ số i được lưu vào phần tử có chỉ số i.

Cây nhị phân có thể được lưu trữ trong mảng một chiều có () phần tử như sau:

• Nếu nút có chỉ số i không có nút con trái thì phần tử có chỉ số 2i + 1 là None.
• Nếu nút có chỉ số i không có nút con phải thì phần tử có chỉ số 2i + 2 là None.
• Các phần tử còn lại là None.
• Không lưu các giá trị None ở cuối mảng.

Ví dụ 1: Biểu diễn cây nhị phân ở Hình 3b (cây nhị phân hoàn hảo)

bằng mảng một chiều:

Hình 5. Đánh chỉ số cho các nút

Đánh chỉ số bắt đầu từ 0 cho các nút theo thứ tự từ mức 0 đến mức cuối cùng, từ trái sang phải trên cùng một mức.

1

Ví dụ 1: Biểu diễn cây nhị phân ở Hình 3b (cây nhị phân hoàn hảo)

bằng mảng một chiều:

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.

2

Ví dụ 2: Biểu diễn cây nhị phân tổng quát bằng mảng một chiều:

Thêm vào cây một số nút giả và gán giá trị None để được cây nhị phân hoàn chỉnh.

1

Hình 6. Thêm nút giả mang giá trị None cho cây

Đư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ố.

2

• Lưu ý: Để tiết kiệm vùng nhớ của mảng một chiều, không lưu trữ các nút giả None vào cuối mảng.
• Ví dụ: Trong hình, nút 12 và nút 9 là các nút lá; các nút con của các nút này là các nút giả None và không được lưu trữ vào cuối mảng.

b) Cài đặt cây nhị phân bằng mảng một chiều

• Giả sử nút thật có giá trị là số dương và nút giả có giá trị là 0. Dữ liệu nhập để tạo cây nhị phân tổng quát trong Hình 6b là dãy các số 5, 8, 10, 6, 0, 12, 9, 0, 15.
• Chương trình tham khảo:

Hoạt động Làm tr.31 SGK

Xây dựng mảng một chiều biểu diễn cây ở Hình 7.

Mảng một chiều biểu diễn cây ở Hình 7 là:

• Cách lưu trữ các nút của cây vào các phần tử của mảng một chiều như sau:
• Nút gốc là nút có chỉ số 0. Nếu nút có chỉ số i thì nút con trái có chỉ số là 2*i + 1 và nút con phải có chỉ số là 2*i + 2.

GHI NHỚ

• Cây rỗng thì phần tử có chỉ số 0 là None. Nút có chỉ số i được lưu vào phần tử có chỉ số i. Nếu nút có chỉ số i không có nút con trái thì phần tử có chỉ số 2*i + 1 là None. Nếu nút có chỉ số i không có nút con phải thì phần tử có chỉ số 2*i + 2 là None. Các phần tử còn lại là None. Không lưu các giá trị None ở cuối mảng. Điều này có nghĩa là thêm các nút None vào cây nhị phân tổng quát để cây này trở thành cây nhị phân hoàn chỉnh.

GHI NHỚ

LUYỆN TẬP

(câu hỏi trắc nghiệm)

Em hãy quan sát cây dưới đây và trả lời các Câu 1, 2, 3:

A. 1.

B. 2.

C. 3.

D. 4.

B. 2.

Câu 1. Mức của nút 6 là:

Em hãy quan sát cây dưới đây và trả lời các Câu 1, 2, 3:

A. nút 5 và nút 11.

B. nút 2 và nút 11.

C. nút 6 và nút 5.

D. nút 2 và nút 6.

D. nút 2 và nút 6.

Câu 2. Nút 7 là nút cha của:

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