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

CHÀO MỪNG

CẢ LỚP ĐẾN VỚI

BÀI HỌC NÀY!

KHỞI ĐỘNG

Em hãy quan sát một nhánh cây phả hệ ở Hình 1 và cho biết Bình phải xưng hô với An như thế nào?

Hình 1. Một nhánh cây phả hệ bên họ nội của An và Bình

KHỞI ĐỘNG

Hình 1. Một nhánh cây phả hệ bên họ nội của An và Bình

Bình phải xưng hô với An là bác vì Bình là cháu của chú Hiền và chú Hiền là em của bố An.

BÀI 1: GIỚI THIỆU

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

Khái niệm cây

02

Khái niệm

cây nhị phân

03

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

04

Duyệt cây nhị phân

PHẦN 1.

KHÁI NIỆM CÂY

1. Khái niệm cây

Cấu trúc dữ liệu cây: 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.

1. Khái niệm cây

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

1. Khái niệm cây

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

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

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?

Nút trong

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

Nút lá

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

Khóa

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

Một dãy các cạnh liên tiếp nhau trên cây.

VD: 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 (mức)

Số lượng cạnh trên đường đi duy nhất từ gốc r đến nút đó.

Chiều cao cây

Độ 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

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

• Sơ đồ phân cấp quản lí.
• Mục lục của 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.

PHẦN 2.

KHÁI NIỆM

CÂY NHỊ PHÂN

Đội tuyển Argentina đã giành chức vô địch World Cup 2022. Dựa vào Hình 6, 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:

• 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

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.

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

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

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.

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

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

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

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

Hình 9. Ví dụ nút con trái và nút con phải trong 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 đó:

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

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

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

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.

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

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?

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

Hình 11. Ví dụ biểu diễn một cây nhị phân

hoàn hảo bởi mả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:

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

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

• Cây nhị phân hoàn hảo là cây nhị phân thoả mãn:

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

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

PHẦN 3.

BIỂU DIỄN CÂY NHỊ PHÂN BẰNG MẢNG MỘT CHIỀU

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.

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

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

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

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

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

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.

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

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

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

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

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

Có thể biểu diễn cây nhị phân hoàn chỉnh bằng mảng một chiều như kĩ thuật biểu diễn cây nhị phân hoàn hảo bằng mảng một chiều.

Có thể sử dụng mảng một chiều để biểu diễn cây nhị phân.

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

Lưu ý: Số lượng nút giả được bổ sung có thể rất lớn. Trong trường hợp tồi nhất là cây có n nút mà các nút trong chỉ có một nút con phải, nghĩa là cây suy biến (lệch phải), chiều cao của cây là h = n – 1. Sau khi biến đổi cây này thành cây nhị phân hoàn chỉnh bằng cách thêm vào các nút giả; cây này có n nút thật dùng để lưu trữ dữ liệu và có 2n – 1 – n nút giả (không lưu trữ dữ liệu).

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

Ví dụ: Hình 12a là một cây nhị phân và Hình 12b là cây nhị phân sau khi thêm các nút giả vào cây ở Hình 12a để trở thành cây nhị phân hoàn chỉnh.

PHẦN 4.

DUYỆT CÂY

NHỊ PHÂN

4. Duyệt cây nhị phân

Hai cây trong Hình 13 khác nhau như thế nào?

4. Duyệt cây nhị phân

Hai cây khác nhau vì hai con của nút a xuất hiện trong hai cây theo thứ tự khác nhau.

Các nút con của một nút được xếp thứ tự từ trái sang phải.

Khái niệm: Duyệt cây là cách thăm tất cả các nút, mỗi nút đúng một lần theo một thứ tự nhất định.

4. Duyệt cây nhị phân

Thứ tự trước.

Thứ tự sau.

Thứ tự giữa.

Có thể duyệt thứ tự các nút của cây theo nhiều cách

• Xét một cây nhị phân T có nút gốc r với cây con trái và cây con phải .

Hình 14. Cấu trúc đệ quy cây nhị phân

------------------------------

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