Câu hỏi:
26/06/2024 23Quan 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.
Siêu phẩm 30 đề thi thử THPT quốc gia 2024 do thầy cô VietJack biên soạn, chỉ từ 100k trên Shopee Mall.
Quảng cáo
Trả lời:
a) Nút đầu tiên: Khi thực hiện thuật toán duyệt giữa, nút đầu tiên được duyệt là nút ‘1’, vì nó là nút nằm xa nhất về bên trái của cây.
b) Nút cuối cùng: Nút cuối cùng được duyệt là nút ‘19’, vì nó là nút nằm xa nhất về bên phải của cây.
c) Thứ tự duyệt: Các nút sẽ được duyệt theo thứ tự sau: 1, 3, 4, 7, 8, 9, 10, 12, 15, 14, 19. Kết quả này cho thấy thuật toán duyệt giữa trên cây tìm kiếm nhị phân sẽ cho ra danh sách các nút theo thứ tự tăng dần. Điều này xảy ra bởi vì thuật toán này luôn tuân theo quy tắc: trước tiên duyệt tất cả các nút nhỏ hơn nút gốc (bên trái), sau đó là nút gốc (ở giữa), và cuối cùng là tất cả các nút lớn hơn nút gốc (bên phải).
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?
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.
Câu 4:
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.
Câu 5:
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.
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ề câu hỏi!