1. CÂY TÌM KIẾM NHỊ PHÂN

Câu hỏi 1: Trong hình 7.1, em hãy cho biết cây nào là cây tìm kiếm nhị phân.

2. CHÈN MỘT KHÓA VÀO CÂY TÌM KIẾM NHỊ PHÂN

Câu hỏi 1: Cho trước dãy các số A = [10, 1, 2, 11, 8, 15, 20, 9, 0]. 

Hãy mô tả và vẽ sơ đồ cây nhị phân biểu diễn dãy số trên sau khi thực hiện thao tác chèn như đã mô tả trong hoạt động. 

3. THUẬT TOÁN TÌM KIẾM TRÊN CÂY TÌM KIẾM NHỊ PHÂN

Câu hỏi 1: Khi nào việc tìm kiếm trên cây tìm kiếm nhị phân là:

a) nhanh nhất?                            b) chậm nhất?

Luyện tập

1. Thay đổi thứ tự chèn các phần tử vào cây nhị phân có tạo ra các cây tìm kiếm nhị phân khác nhau hay không? Cho ví dụ minh họa.

Vận dụng

1. Dữ liệu đầu vào là danh sách học sinh trong lớp và điểm trung bình các môn. Danh sách được cho trong tệp văn bản có dạng như bảng bên.

Viết chương trình đọc tập dữ liệu đầu vào trên và liên tục thực hiện các thao tác sau:

a) Nhập thêm vào danh sách học sinh và điểm trung bình.

b) Tìm kiếm với yêu cầu nhập họ tên học sinh và đưa ra kết quả họ tên học sinh, điểm trung bình hoặc thông báo "không tìm thấy".

Chương trình kết thúc khi nhập vào một xâu rỗng. Yêu cầu giải bài này bằng cây tìm kiếm nhị phân.

3. Cho trước dãy A bao gồm các số nguyên và các giá trị None. Viết chương trình kiểm tra xem A có phải là biểu diễn của một cây nhị phân hoàn chỉnh đã biến đổi hay không?

Ví dụ:

Dãy [10, 7, 0, 5, None, 3] là biểu diễn của cây nhị phân hoàn chỉnh đã biến đổi. Dãy [1, 6, None, 2, 3, None, 4] không là biểu diễn của cây nhị phân tổng quát nào.