Cây tìm kiếm nhị phân – chèn, tìm, xoá và duyệt cây

Thuộc chủ đề Giải quyết vấn đề với sự trợ giúp của máy tính (Tin học 12), gắn với cấu trúc dữ liệu cây. Trong cây tìm kiếm nhị phân, mọi khoá ở cây con trái nhỏ hơn và mọi khoá ở cây con phải lớn hơn khoá của nút, nên tìm, chèn và xoá chỉ đi theo một đường từ gốc xuống. Mô phỏng tô đường so sánh qua từng nút, đếm số phép so sánh, tính chiều cao cây và cho thấy khi chèn dãy khoá đã sắp xếp thì cây suy biến thành một danh sách. Học sinh nhập khoá rồi bấm Chèn, Tìm hoặc Xoá để xem từng bước, kể cả xoá nút có hai con bằng nút kế tiếp theo thứ tự giữa. Nút Xây cây mới dựng cây từ các khoá theo thứ tự ngẫu nhiên, tăng dần hoặc khoá giữa trước và ghi chiều cao cùng số so sánh trung bình vào bảng so sánh. Chế độ Duyệt cây chạy duyệt trước, giữa, sau và theo mức cùng ngăn xếp hoặc hàng đợi; chế độ Cây biểu thức dựng cây từ biểu thức và cho ký pháp tiền tố, trung tố, hậu tố. Câu hỏi gợi ý: – Chèn 7 khoá theo thứ tự tăng dần thì cây cao bao nhiêu, và cần bao nhiêu phép so sánh để tìm khoá lớn nhất? – Vì sao duyệt giữa một cây tìm kiếm nhị phân luôn cho dãy khoá tăng dần? – Biểu thức (3 + 4) * 5 viết theo ký pháp hậu tố như thế nào, và vì sao cách viết đó không cần dấu ngoặc?