Câu hỏi:
26/06/2024 19Đọ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.
Siêu phẩm 30 đề thi thử THPT quốc gia 2024 do thầy cô VietJack biên soạn, chỉ từ 100k trên Shopee Mall.
Quảng cáo
Trả lờ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.
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 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 2:
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.
Câu 3:
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 5:
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.
Câu 6:
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ề câu hỏi!