Bài toán: cho cây tìm kiếm nhị phân T. Yêu cầu chèn khoá v vào cây T

Giải Chuyên đề Tin 12 Bài 7: Cây tìm kiếm nhị phân - Kết nối tri thức

Hoạt động 2 trang 33 Chuyên đề Tin học 12: Bài toán: cho cây tìm kiếm nhị phân T. Yêu cầu chèn khoá v vào cây T sao cho sau khi cho sau khi chèn khoá v thì cây T vẫn là cây tìm kiếm nhị phân.

Quan sát, thảo luận, tìm hiểu thuật toán tìm kiếm khoá 7 trên cây tìm kiếm nhị phân và cách chèn khoá 7 vào cây này.

Lời giải:

Quá trình chèn khoá v = 7 vào cây tìm kiếm nhị phân T ở Hình 7.6a như sau:

Bước 1. Tìm vị trí cần chèn khoá v trên cây T (Hình 7.6b). Khoá v lớn hơn khoá 5, đi đến nút con phải. Khoá y nhỏ khoá 10, đi đến nút con trái. Khoá y nhỏ hơn khoá 8, đi đến nút con trái và gặp nút giả None.

Bước 2. Chèn khoá v vào cây T (Hình 7.6c). Trong trường hợp khoá v không có trong cây T thì chèn khoá v vào cây này bằng cách tạo nút thật mới tại nút giả None và gán khoá y cho nút mới này.

Lời giải bài tập Chuyên đề Tin 12 Bài 7: Cây tìm kiếm nhị phân hay, ngắn gọn khác:

• Khởi động trang 30 Chuyên đề Tin học 12: Quan sát các cây nhị phân sau, em có nhận xét gì về giá trị của các nút trên cây ....

• Hoạt động 1 trang 30 Chuyên đề Tin học 12: Tìm hiểu và thảo luận về tổ chức dữ liệu của cây nhị phân và tìm kiếm cây nhị phân ....

• Câu hỏi 1 trang 32 Chuyên đề Tin học 12: Trong hình 7.5, em hãy cho biết cây nào là cây tìm kiếm nhị phân ....

• Câu hỏi 2 trang 32 Chuyên đề Tin học 12: Từ các khóa 1, 2, 3 có thể tạo ra được bao nhiêu cây tìm kiếm nhị phân? ....

• Câu hỏi 1 trang 34 Chuyên đề Tin học 12: 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 ....

• Câu hỏi 2 trang 34 Chuyên đề Tin học 12: Với cây nhị phân đã có ở Câu 1, em hãy vẽ sơ đồ cây sau khi chèn khoá 14 và cho biết ....

• Hoạt động 3 trang 34 Chuyên đề Tin học 12: Quan sát quá trình tìm kiếm khoá trên cây tìm kiếm phị phân thông qua các ví dụ cụ thể ....

• Câu hỏi 1 trang 36 Chuyên đề Tin học 12: Khi nào việc tìm kiếm trên cây tìm kiếm nhị phân là: nhanh nhất ....

• Câu hỏi 2 trang 36 Chuyên đề Tin học 12: Cây tìm kiếm nhị phân T được thiết lập bằng cách chèn lần lượt các phần tử 3, 1, 6, 5, 0 ....

• Luyện tập 1 trang 36 Chuyên đề Tin học 12: 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 ....

• Luyện tập 2 trang 36 Chuyên đề Tin học 12: Nếu dãy số được đưa vào cây tìm kiếm nhị phân là tăng dần (hoặc giảm dần) thì cây tìm kiếm ....

• Vận dụng 1 trang 36 Chuyên đề Tin học 12: 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 ....

• Vận dụng 2 trang 36 Chuyên đề Tin học 12: Viết hàm chèn khoá v vào cây tìm kiếm nhị phân T sử dụng kĩ thuật đệ quy ....

• Vận dụng 3 trang 36 Chuyên đề Tin học 12: 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 ....

• Vận dụng 4 trang 36 Chuyên đề Tin học 12: 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 thêm lời giải bài tập Chuyên đề học tập Tin học 12 Kết nối tri thức hay, ngắn gọn khác:

• Chuyên đề Tin học 12 Bài 8: Thực hành cây tìm kiếm nhị phân

• Chuyên đề Tin học 12 Bài 9: Các thuật toán duyệt trên cây tìm kiếm nhị phân

• Chuyên đề Tin học 12 Bài 10: Thực hành tổng hợp với cây tìm kiếm nhị phân

• Chuyên đề Tin học 12 Bài 11: Khái niệm đồ thị

• Chuyên đề Tin học 12 Bài 12: Biểu diễn đồ thị

Xem thêm các tài liệu học tốt lớp 12 hay khác:

• Giải Chuyên đề Tin học 12 Kết nối tri thức
• Giải Chuyên đề Tin học 12 Chân trời sáng tạo
• Giải Chuyên đề Tin học 12 Cánh diều

---