Giáo án điện tử chuyên đề Khoa học máy tính 12 kết nối Bài 6: Cây nhị phân

CHÀO MỪNG

CÁC EM ĐẾN

VỚI BÀI HỌC!

KHỞI ĐỘNG

Câu hỏi 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ÀI 6:

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

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

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

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

PHẦN 1.

CẤU TRÚC CÂY VÀ

CÂY NHỊ PHÂN

Quan sát Hình 6.1 – 6.2, thảo luận nhóm 4, 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.

Cây (tree) bao gồm một tập hợp các nút (node) chứa thông tin, 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 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ỗi nút chỉ có thể kết nối với một nút cha.

THẢO LUẬN NHÓM

Chia lớp thành 3 tổ, thảo luận về:

• Tổ 1: Hình 6.1. a)
• Tổ 2: Hình 6.1. b)
• Tổ 3: Hình 6.1. c)

NHIỆM VỤ

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.

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

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

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.

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

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.

CỦNG CỐ

1

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

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

3

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

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

a)

b)

Câu 3

Chiều cao của cây:

a) 4;

b) 5.

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.

KẾT LUẬN

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

PHẦN 2.

BIỂU DIỄN CÂY

NHỊ PHÂN BẰNG BẢ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ó đủ 2k 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.

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 cây nhị phân hoàn chỉnh, chỉ ra mảng một chiều tương ứng.

Thảo luận nhóm, 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ây nhị phân hoàn chỉnh được đánh chỉ số: bắt đầu từ 0 (nút gốc), đá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.

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 cây nhị phân hoàn chỉnh, chỉ ra mảng một chiều tương ứng

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

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

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.

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

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:

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

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

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

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.

PHẦN 3.

CÁC THUẬT TOÁN DUYỆT CÂY NHỊ PHÂN

THẢO LUẬN NHÓM

Chia lớp thành 3 tổ, mỗi tổ 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

NHIỆM VỤ

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.

a

Duyệt trước (preorder traversal)

Cây con có nút gốc v được gọi là "cây v"

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

a

Duyệt trước (preorder traversal)

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