Câu hỏi:
13/07/2024 130
Cho trước dãy số A = [2,1,9,0,2,1,5]. Tạo cây tìm kiếm nhị phân T từ dãy A và thực hiện thuật toán duyệt giữa trên cây T. Em hãy cho biết kết quả duyệt là dãy các khoá có thứ tự như thế nào.
Cho trước dãy số A = [2,1,9,0,2,1,5]. Tạo cây tìm kiếm nhị phân T từ dãy A và thực hiện thuật toán duyệt giữa trên cây T. Em hãy cho biết kết quả duyệt là dãy các khoá có thứ tự như thế nào.
Sách mới 2k7: Tổng ôn Toán, Lí, Hóa, Văn, Sử, Địa…. kỳ thi tốt nghiệp THPT Quốc gia 2025, đánh giá năng lực (chỉ từ 110k).
Quảng cáo
Trả lời:
Giải bởi Vietjack
Các bước xây dựng cây tìm kiếm nhị phân (BST) từ dãy số A
- Chèn 2: Làm gốc của cây.
- Chèn 1: So với 2, 1 nhỏ hơn, chèn vào bên trái của 2.
- Chèn 9: So với 2, 9 lớn hơn, chèn vào bên phải của 2.
- Chèn 0: So với 2, nhỏ hơn; so với 1, nhỏ hơn, chèn vào bên trái của 1.
- Chèn 2 (thứ hai): So với 2, bằng nhau; theo quy tắc chung (trường hợp đặc biệt), chèn vào bên phải của 2 gốc
- Chèn 1 (thứ hai): So với 2, nhỏ hơn; so với 1, bằng nhau; chèn vào bên phải của 1.
- Chèn 5: So với 2, lớn hơn; so với 9, nhỏ hơn, chèn vào bên trái của 9.
Cấu trúc cây BST
![Cho trước dãy số A = [2,1,9,0,2,1,5]. Tạo cây tìm kiếm nhị phân T từ dãy A và thực hiện thuật toán duyệt giữa trên cây T. Em hãy cho biết kết quả duyệt là dãy các khoá có thứ tự như thế nào. (ảnh 1)](https://video.vietjack.com/upload2/quiz_source1/2024/06/2-1719410368.jpg)
Duyệt giữa (In-order Traversal)
Duyệt giữa trên cây tìm kiếm nhị phân là duyệt theo thứ tự cây con trái, nút gốc, cây con phải.
Cụ thể các bước thực hiện như sau:
- Duyệt cây con trái của nút gốc (2):
+ Duyệt cây con trái của nút 1:
+ Duyệt cây con trái của 0 (không có nút con trái nào), thăm 0.
+ Thăm nút 1.
+ Duyệt cây con phải của 1:
2. Duyệt cây con trái của 1 (thứ hai) (không có nút con trái nào), thăm 1 (thứ hai).
- Thăm nút 1.
- Thăm nút gốc (2).
- Duyệt cây con phải của nút gốc (2):
- Duyệt cây con trái của nút 9:
- Duyệt cây con trái của 5 (không có nút con trái nào), thăm 5.
- Thăm nút 9.
- Duyệt cây con phải của 9 (không có nút con phải nào).
Kết quả duyệt giữa
0, 1, 1, 2, 2, 5, 9
Như vậy, dãy các khoá theo thứ tự duyệt giữa 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à: [0, 1, 1, 2, 2, 5, 9].
Nhà sách VIETJACK:
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 2:
Thuật toán sắp xếp dãy sử dụng cây tìm kiếm nhị phân có độ phức tạp thời gian là bao nhiêu?
Thuật toán sắp xếp dãy sử dụng cây tìm kiếm nhị phân có độ phức tạp thời gian là bao nhiêu?
Xem đáp án »
13/07/2024
257
Câu 3:
Trao đổi, thảo luận để giải bài toán sau:
Cho trước dãy số A. Thiết kế thuật toán sắp xếp lại dãy A theo thứ tự tăng dần hoặc giảm dần.
Trao đổi, thảo luận để giải bài toán sau:
Cho trước dãy số A. Thiết kế thuật toán sắp xếp lại dãy A theo thứ tự tăng dần hoặc giảm dần.
Xem đáp án »
13/07/2024
99
Câu 4:
Quan sát cây tìm kiếm nhị phân trong hình 9.1, cùng trao đổi, thảo luận các câu hỏi sau:
a) Nếu thực hiện thuật toán duyệt giữa (trái – gốc – phải) thì nút đầu tiên được duyệt là nút nào?
b) Nút cuối cùng được duyệt là nút nào?
c) Thứ tự các nút được duyệt theo thuật toán duyệt giữa sẽ theo thứ tự nào? Em có nhận xét gì về kết quả đạt được? Giải thích vì sao.
Quan sát cây tìm kiếm nhị phân trong hình 9.1, cùng trao đổi, thảo luận các câu hỏi sau:
a) Nếu thực hiện thuật toán duyệt giữa (trái – gốc – phải) thì nút đầu tiên được duyệt là nút nào?
b) Nút cuối cùng được duyệt là nút nào?
c) Thứ tự các nút được duyệt theo thuật toán duyệt giữa sẽ theo thứ tự nào? Em có nhận xét gì về kết quả đạt được? Giải thích vì sao.
Xem đáp án »
13/07/2024
75
Câu 5:
Dựa trên hàm BSTSort(A) đã biết, viết chương trình sắp xếp dãy số giảm dần theo kĩ thuật sử dụng cây tìm kiếm nhị phân.
Dựa trên hàm BSTSort(A) đã biết, viết chương trình sắp xếp dãy số giảm dần theo kĩ thuật sử dụng cây tìm kiếm nhị phân.
Xem đáp án »
13/07/2024
73
Câu 6:
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?
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?
Xem đáp án »
13/07/2024
60
về câu hỏi!