Với cây T như Câu 1, nếu thực hiện thuật toán duyệt ngược thì thứ tự các khoá
Với cây T như Câu 1, nếu thực hiện thuật toán duyệt ngược thì thứ tự các khoá thể hiện trên màn hình như thế nào?
Giải Chuyên đề Tin 12 Bài 9: Các thuật toán duyệt trên cây tìm kiếm nhị phân - Kết nối tri thức
Câu hỏi 2 trang 43 Chuyên đề Tin học 12: Với cây T như Câu 1, nếu thực hiện thuật toán duyệt ngược thì thứ tự các khoá thể hiện trên màn hình như thế nào?
Lời giải:
Hướng dẫn cụ thể các bước thực hiện như sau:
1. Duyệt cây con phải của nút gốc (2):
- Duyệt cây con phải của nút 9 (không có nút con phải nào).
- Thăm nút 9.
- Duyệt cây con trái của nút 9:
Duyệt cây con phải của nút 5 (không có nút con phải nào).
Thăm nút 5.
Duyệt cây con trái của nút 5 (không có nút con trái nào).
2. Thăm nút gốc (2).
3. Duyệt cây con trái của nút gốc (2):
Duyệt cây con phải của nút 1:
- Duyệt cây con phải của nút 1 (thứ hai) (không có nút con phải nào).
- Thăm nút 1 (thứ hai).
- Duyệt cây con trái của nút 1 (thứ hai) (không có nút con trái nào).
Thăm nút 1.
Duyệt cây con trái của nút 1:
- Duyệt cây con phải của nút 0 (không có nút con phải nào).
- Thăm nút 0.
- Duyệt cây con trái của nút 0 (không có nút con trái nào).
Kết quả duyệt ngược
9, 5, 2, 2, 1, 1, 0
Như vậy, dãy các khoá theo thứ tự duyệt ngược trên cây tìm kiếm nhị phân được tạo từ dãy A = [2,1,9,0,2,1,5] là: [9, 5, 2, 2, 1, 1, 0].
Lời giải bài tập Chuyên đề Tin 12 Bài 9: Các thuật toán duyệt trên cây tìm kiếm nhị phân hay, ngắn gọn khác: