Từ một dãy có ít nhất 6 số nguyên dương tùy ý em hãy vẽ hình minh hoa và mô tả
Từ một dãy có ít nhất 6 số nguyên dương tùy ý em hãy vẽ hình minh hoa và mô tả từng bước xây dựng một cây tìm kiếm nhị phân tương ứng với dãy đó, bắt dầu từ cây rỗng.
Giải Chuyên đề Tin 12 Bài 3: Cây tìm kiếm nhị phân - Cánh diều
Vận dụng trang 48 Chuyên đề Tin học 12: Từ một dãy có ít nhất 6 số nguyên dương tùy ý em hãy vẽ hình minh hoa và mô tả từng bước xây dựng một cây tìm kiếm nhị phân tương ứng với dãy đó, bắt dầu từ cây rỗng.
Lời giải:
Hướng dẫn gợi ý các bước làm:
Để minh họa cách xây dựng một cây tìm kiếm nhị phân (BST - Binary Search Tree) từ một dãy số nguyên dương tùy ý, hãy xem xét dãy số ví dụ: [10, 5, 15, 3, 7, 12, 18]. Ta có các bước chi tiết để xây dựng BST từ dãy số trên, bắt đầu từ cây rỗng:
Bước 1: Khởi tạo cây rỗng
Lúc đầu, cây tìm kiếm nhị phân (BST) là rỗng.
Bước 2: Thêm phần tử đầu tiên
- Phần tử 10: Là phần tử đầu tiên trong dãy, sẽ là gốc của cây.
Bước 3: Thêm phần tử thứ hai
- Phần tử 5: So sánh với gốc 10. Vì 5 < 10, nên 5 sẽ là con trái của 10.
Bước 4: Thêm phần tử thứ ba
- Phần tử 15: So sánh với gốc 10. Vì 15 > 10, nên 15 sẽ là con phải của 10.
Bước 5: Thêm phần tử thứ tư
- Phần tử 3: So sánh với gốc 10, sau đó với 5. Vì 3 < 10 và 3 < 5, nên 3 sẽ là con trái của 5.
Bước 6: Thêm phần tử thứ năm
- Phần tử 7: So sánh với gốc 10, sau đó với 5. Vì 7 < 10 và 7 > 5, nên 7 sẽ là con phải của 5.
Bước 7: Thêm phần tử thứ sáu
- Phần tử 12: So sánh với gốc 10, sau đó với 15. Vì 12 > 10 và 12 < 15, nên 12 sẽ là con trái của 15.
Bước 8: Thêm phần tử thứ bảy
- Phần tử 18: So sánh với gốc 10, sau đó với 15. Vì 18 > 10 và 18 > 15, nên 18 sẽ là con phải của 15.
Lời giải bài tập Chuyên đề Tin 12 Bài 3: Cây tìm kiếm nhị phân hay, chi tiết khác: