Câu hỏi:

13/07/2024 456

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.

Quảng cáo

Trả lời:

verified
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)

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].

Bình luận


Bình luận

CÂU HỎI HOT CÙNG CHỦ ĐỀ

Câu 1:

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 1,136

Câu 2:

Viết hàm height(T) tính chiều cao của cây tìm kiếm nhị phân T.

Xem đáp án » 13/07/2024 743

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.

Xem đáp án » 13/07/2024 177

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:  (ảnh 1)

Xem đáp án » 13/07/2024 156

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.

Xem đáp án » 13/07/2024 148

Câu 6:

Quan sát cách cài đặt các thuật toán duyệt trên cây tìm kiếm nhị phân và trao đổi về ý nghĩa và sự khác biệt khi thực hiện các thuật toán này so với các thuật toán duyệt cây nhị phân đã học trong Bài 6.

Xem đáp án » 13/07/2024 124
Vietjack official store
Đăng ký gói thi VIP

VIP +1 - Luyện thi tất cả các đề có trên Website trong 1 tháng

  • Hơn 100K đề thi thử, đề minh hoạ, chính thức các năm
  • Với 2tr+ câu hỏi theo các mức độ Nhận biết, Thông hiểu, Vận dụng
  • Tải xuống đề thi [DOCX] với đầy đủ đáp án
  • Xem bài giảng đính kèm củng cố thêm kiến thức
  • Bao gồm tất cả các bậc từ Tiểu học đến Đại học
  • Chặn hiển thị quảng cáo tăng khả năng tập trung ôn luyện

Mua ngay

VIP +3 - Luyện thi tất cả các đề có trên Website trong 3 tháng

  • Hơn 100K đề thi thử, đề minh hoạ, chính thức các năm
  • Với 2tr+ câu hỏi theo các mức độ Nhận biết, Thông hiểu, Vận dụng
  • Tải xuống đề thi [DOCX] với đầy đủ đáp án
  • Xem bài giảng đính kèm củng cố thêm kiến thức
  • Bao gồm tất cả các bậc từ Tiểu học đến Đại học
  • Chặn hiển thị quảng cáo tăng khả năng tập trung ôn luyện

Mua ngay

VIP +6 - Luyện thi tất cả các đề có trên Website trong 6 tháng

  • Hơn 100K đề thi thử, đề minh hoạ, chính thức các năm
  • Với 2tr+ câu hỏi theo các mức độ Nhận biết, Thông hiểu, Vận dụng
  • Tải xuống đề thi [DOCX] với đầy đủ đáp án
  • Xem bài giảng đính kèm củng cố thêm kiến thức
  • Bao gồm tất cả các bậc từ Tiểu học đến Đại học
  • Chặn hiển thị quảng cáo tăng khả năng tập trung ôn luyện

Mua ngay

VIP +12 - Luyện thi tất cả các đề có trên Website trong 12 tháng

  • Hơn 100K đề thi thử, đề minh hoạ, chính thức các năm
  • Với 2tr+ câu hỏi theo các mức độ Nhận biết, Thông hiểu, Vận dụng
  • Tải xuống đề thi [DOCX] với đầy đủ đáp án
  • Xem bài giảng đính kèm củng cố thêm kiến thức
  • Bao gồm tất cả các bậc từ Tiểu học đến Đại học
  • Chặn hiển thị quảng cáo tăng khả năng tập trung ôn luyện

Mua ngay