Giải chuyên đề Khoa học máy tính 12 Kết nối bài 6: Cây nhị phân

Hướng dẫn giải bài 6: Cây nhị phân bộ sách mới chuyên đề học tập Khoa học máy tính 12 Kết nối tri thức. Bộ sách được biên soạn theo định hướng đổi mới giáo dục phổ thông nhằm phát triển toàn diện phẩm chất, năng lực của học sinh. Hi vọng, với cách hướng dẫn cụ thể và giải chi tiết dưới đây các em sẽ nắm bài học tốt hơn.

B. Bài tập và hướng dẫn giải

Khởi động
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 đặc điểm chung gì?

1. CẤU TRÚC CÂY VÀ CÂY NHỊ PHÂN

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

Câu hỏi 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 hỏi 3: Tính chiều cao của các cây trong Hình 6.3.

A diagram of a constellation

Description automatically generated

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

Câu hỏi 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 hỏi 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. 

Lưu ý: Cây nhị phân tổng quát cũng có thể được biểu diễn bằng mảng một chiều bằng cách bổ sung các nút rỗng có giá trị None để tạo thành cây hoàn chỉnh, sau đó biểu diễn mảng như đã nêu trên. Ví dụ sau minh hoạ cho ý tưởng này.

A diagram of a number and a number

Description automatically generated with medium confidence

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

Câu hỏi 1: Cho mảng [A, B, C, D, E, F, G, H, I, J] biểu diễn một cây nhị phân. Em hãy cho biết thứ tự duyệt các nút của cây này theo phép duyệt trước (gốc-trái-phải). 

Câu hỏi 2: Với mảng dữ liệu ở Câu 1, thứ tự duyệt các phần tử sẽ như thế nào nếu thực hiện thuật toán duyệt sau?

Luyện tập

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

A diagram of a triangle with blue dots

Description automatically generated

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?

Vận dụng

1. Cho mảng một chiều A biểu diễn cây nhị phân hoàn chỉnh T. Viết hàm 1eve1(k) trả về mức của nút tương ứng với phần tử A[k] của cây T. 

2. Cho cây nhị phân T được biểu diễn bởi mảng một chiều A. Viết các hàm duyệt trước, duyệt giữa và duyệt sau trên cây T.

Thêm kiến thức môn học

Từ khóa tìm kiếm:

Giải chuyên đề học tập Khoa học máy tính 12 Kết nối tri thức, Giải chi tiết bài 6: Cây nhị phân chuyên đề học tập Khoa học máy tính 12 Kết nối tri thức, Giải chuyên đề học tập Khoa học máy tính 12 Kết nối tri thức bài 6: Cây nhị phân

Bình luận

Giải bài tập những môn khác