Đọ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 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.
Giải Chuyên đề Tin 12 Bài 6: Cây nhị phân - Kết nối tri thức
Hoạt động 2 trang 25 Chuyên đề Tin học 12: Đọ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:
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.
Lời giải bài tập Chuyên đề Tin 12 Bài 6: Cây nhị phân hay, ngắn gọn khác:
Câu hỏi 1 trang 24 Chuyên đề Tin học 12: Tìm thêm các ví dụ cấu trúc cây ....
Câu hỏi 3 trang 24 Chuyên đề Tin học 12: Tính chiều cao của các cây trong Hình 6.3 ....