Bài 6: Cây nhị phân - Chuyên đề Tin học 12 Kết nối tri thức
Câu 1
Trả lời câu hỏi Khởi động trang 23 Chuyên đề Tin học 12 Kết nối tri thức
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ì?
Lời giải chi tiết:
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 sau:
a) Các thư mục được chia thành các thư mục nhỏ hơn và nhỏ dần hơn giúp dễ dàng phân loại thư mục có điểm chung hơn.
b) Ở mỗi nút sẽ chia thành 2 nhánh. Càng sâu sẽ càng nhiều nút.
c) Trong sơ đồ tư duy, từ chủ đề chính chia thành các nhánh nhỏ hơn để giúp biết thêm thông tin về chủ đề chính.
2. Điểm chung: Các sơ đồ đều xuất phát từ một ý tổng rồi chia lần lượt thành các nhánh nhỏ dần.
Câu 2
Trả lời câu hỏi Hoạt động 1 trang 23 Chuyên đề Tin học 12 Kết nối tri thức
Đọc, quan sát, qua sát thảo luận về khái niệm và cấu trúc cây. Với mỗi sơ đồ cây đã được mô tả trong hoạt động khởi động, hãy chỉ ra nút gốc, nút nhánh, nút lá và tính chiều cao của cây.
Lời giải chi tiết:
- Nút gốc không có nút cha.
- Nút nhánh là nút có nút con.
- Nút lá là nút không có nút con.
- Chiều cao của cây là độ dài đường đi đến nút lá sâu nhất, hay chính là mức cao nhất của các nút trên cây.
Câu 3
Trả lời câu hỏi 1 trang 24 Chuyên đề Tin học 12 Kết nối tri thức
Tìm thêm các ví dụ cấu trúc cây.
Lời giải chi tiết:
Ví dụ cấu trúc cây: Cây cối, Sinh học (Thực vật và động vật), Hệ thống các tệp, Mạng máy tính…
Câu 4
Trả lời câu hỏi 2 trang 24 Chuyên đề Tin học 12 Kết nối tri thức
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)).
Lời giải chi tiết:
a)
b)
Câu 5
Trả lời câu hỏi 3 trang 24 Chuyên đề Tin học 12 Kết nối tri thức
Tính chiều cao của các cây trong Hình 6.3.
Lời giải chi tiết:
a) Chiều cao: 4
b) Chiều cao: 5
Câu 6
Trả lời câu hỏi Hoạt động 2 trang 25 Chuyên đề Tin học 12 Kết nối tri thức
Đọc và thảo luận nhóm để tìm hiểu phân loại cây nhị phân và một số cách biểu diễn cây nhị phân bằng mảng 1 chiều hoặc bằng nút liên kết.
Lời giải chi tiết:
Phân loại cây nhị phân như sau:
- Cây nhị phân được gọi là hoàn hảo nếu mọi nút của cây đều có đủ hai nút con và tất cả các nút lá đều cùng mức.
- Cây nhị phân được gọi là hoan chỉnh nếu tại mức i có 2i nút và tại mức h thì các nút liên tục tính từ trái sang phải, có thể khuyết một số nút bên trái, với h là chiều cao của cây.
Một số cách biểu diễn cây nhị phân bằng mảng 1 chiều hoặc bằng nút liên kết:
- Mảng 1 chiều: nếu cho trước 1 mảng 1 chiều có thể dễ dàng thiết lập cây nhị phân hoàn chỉnh tương ứng với mảng này. Nút gốc của cây sẽ tương ứng với phần tử đầu tiên của mảng với chỉ số 0. Các phần tử tiếp theo sẽ 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.
- Biểu diễn cây nhị phân bằng nút liên kết: Cây có một nút gốc, mỗi nút có thể có nhiều nút con. Thông thường, cấu trúc của cây là cấu trúc liên kết.
Câu 7
Trả lời câu hỏi 1 trang 26 Chuyên đề Tin học 12 Kết nối tri thức
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.
Lời giải chi tiết:
- Nút 9 là nút lá ở chỉ số 6.
- Chỉ số của cha nút 9 là (6-1)//2 = 2, tức là nút 8.
- Chỉ số của cha nút 8 là (2-1)//2 = 0, tức là nút 2.
Như vậy, dãy các nút đi từ nút lá 9 về nút gốc 2 là: 9 -> 8 -> 2.
Câu 8
Trả lời câu hỏi 2 trang 26 Chuyên đề Tin học 12 Kết nối tri thức
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.
Lời giải chi tiết:
a) Chiều cao của cây nhị phân là: 3
b) Chiều cao của cây nhị phân là: 3
Câu 9
Trả lời câu hỏi Hoạt động 3 trang 27 Chuyên đề Tin học 12 Kết nối tri thức
Trao đổi, thảo luận và thực hiện các thuật toán duyệt cây nhị phân. Bài toán đặt ra là cần duyệt tất cả các nút của cây nhị phân, mỗi nút duyệt 1 lần.
Lời giải chi tiết:
a) Duyệt trước: Cây con có nút gốc v được gọi là cây v như minh hoạ ở Hình 6.9. Ý tưởng của phương pháp duyệt trước là 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ì sang duyệt cây con phải.
b) Duyệt sau: là duyệt toàn bộ cây con trái, sau dó duyệt toàn bộ cây con phải, cuối cùng duyệt nút gốc.
c) Duyệt giữa: là duyệt cây con trước, sau đó duyệt nút gốc, cuối dùng duyệt cây con phải.
Câu 10
Trả lời câu hỏi 1 trang 29 Chuyên đề Tin học 12 Kết nối tri thức
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).
Lời giải chi tiết:
Thứ tứ duyệt các nút là: A, B, D, H, I, E, J, C, F, G.
Câu 2
Trả lời câu hỏi 2 trang 29 Chuyên đề Tin học 12 Kết nối tri thức
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?
Lời giải chi tiết:
Thứ tứ duyệt các nút là: H, I, D, J, E, B, F, G, C, A
Luyện tập Câu 1
Trả lời câu hỏi Luyện tập 1 trang 29 Chuyên đề Tin học 12 Kết nối tri thức
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?
Lời giải chi tiết:
Cây hoàn hảo là: c
Cây hoàn chỉnh là: b
Cây không là hoàn hảo và hoàn chỉnh: a
Luyện tập Câu 2
Trả lời câu hỏi Luyện tập 2 trang 29 Chuyên đề Tin học 12 Kết nối tri thức
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?
Lời giải chi tiết:
Khẳng định "Cây nhị phân đầy đủ sẽ luôn là hoàn chỉnh hoặc hoàn hảo" là sai.
Ví dụ về một cây nhị phân đầy đủ không hoàn chỉnh và không hoàn hảo:
Vận dụng Câu 1
Trả lời câu hỏi Vận dụng 1 trang 29 Chuyên đề Tin học 12 Kết nối tri thức
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.
Lời giải chi tiế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 như sau:
function level(k) {
let level = 0;
while (k > 0) {
level++;
k = Math.floor((k - 1) / 2);
}
return level;
}
Vận dụng Câu 2
Trả lời câu hỏi Vận dụng 2 trang 29 Chuyên đề Tin học 12 Kết nối tri thức
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.
Lời giải chi tiết:
Viết các hàm duyệt trước, duyệt giữa và duyệt sau trên cây T như sau:
function preorderTraversal(A, index) {
if (index < A.length) {
console.log(A[index]); // In ra giá trị của nút hiện tại
preorderTraversal(A, 2 * index + 1); // Duyệt nút con trái
preorderTraversal(A, 2 * index + 2); // Duyệt nút con phải
}
}
function inorderTraversal(A, index) {
if (index < A.length) {
inorderTraversal(A, 2 * index + 1); // Duyệt nút con trái
console.log(A[index]); // In ra giá trị của nút hiện tại
inorderTraversal(A, 2 * index + 2); // Duyệt nút con phải
}
}
function postorderTraversal(A, index) {
if (index < A.length) {
postorderTraversal(A, 2 * index + 1); // Duyệt nút con trái
postorderTraversal(A, 2 * index + 2); // Duyệt nút con phải
console.log(A[index]); // In ra giá trị của nút hiện tại
}
}