khoahoc.vietjack.com
Xin chào! Vào học

Câu hỏi:

13/07/2024 366 Lưu

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.

Quảng cáo

Trả lời:

verified Giải bởi Vietjack

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.

Đang tải chế độ Học...

Dành cho bạn Hot

Lớp 12 Vật lý
208 người thi tuần này

Trắc nghiệm Mô hình động học phân tử chất khí lớp 12 (có đáp án)

15 câu 1.9 K lượt thi Thi ngay →
Lớp 12 Tiếng Anh
133 người thi tuần này

Đề cương ôn tập giữa kì 1 Tiếng Anh 12 Global Success có đáp án

45 câu 1.3 K lượt thi Thi ngay →
Lớp 12 Sinh học
189 người thi tuần này

10 câu trắc nghiệm Sinh học 12 Kết nối tri thức Bài 8 có đáp án

10 câu 2 K lượt thi Thi ngay →
Lớp 12 Lịch sử
2,190 người thi tuần này

20 câu trắc nghiệm Lịch sử 12 Kết nối tri thức Bài 1 có đáp án

20 câu 22.4 K lượt thi Thi ngay →
Lớp 12 Địa lý
364 người thi tuần này

20 câu Trắc nghiệm Địa lý 12 Kết nối tri thức Bài 2 có đáp án

25 câu 6 K lượt thi Thi ngay →
Lớp 12 Tin học
556 người thi tuần này

15 câu Trắc nghiệm Tin học 12 Bài 1. Làm quen với Trí tuệ nhân tạo (có đáp án)

15 câu 13.2 K lượt thi Thi ngay →
Lớp 12 Giáo dục Kinh tế và Pháp luật
634 người thi tuần này

15 câu Trắc nghiệm KTPL 12 Bài 1 (có đáp án)

15 câu 8.9 K lượt thi Thi ngay →

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

Lời giải

Đáp án đúng là c) Cây tìm kiếm nhị phân giúp quá trình tìm kiếm phần tử trong dãy có giá trị cho trước nhanh hơn.

Các câu còn lại sai vì:

a) Sai vì trong cây tìm kiếm nhị phân, giá trị khóa của mọi nút trong cây con trái phải nhỏ hơn giá trị khóa của nút gốc, và giá trị khóa của mọi nút trong cây con phải phải lớn hơn giá trị khóa của nút gốc.

b) Sai vì từ một dãy số nguyên cho trước có thể tạo ra nhiều cây tìm kiếm nhị phân khác nhau tùy thuộc vào thứ tự chèn các số vào cây.

d) Sai vì quá trình tìm kiếm trên cây tìm kiếm nhị phân không luôn luôn cho kết quả tìm được nút có giá trị bằng giá trị khóa cho trước, nó chỉ trả về kết quả nếu giá trị đó thực sự tồn tại trong cây.

Lời giải

Danh sách giá trị khóa các nút ở cây nhị phân (Hình 1) trong phép duyệt cây theo thứ tự giữa như sau:

1. Bắt đầu từ gốc (2), duyệt cây con trái của 2.

2. Cây con trái của 2 là 1, không có cây con trái và cây con phải. Thăm nút 1.

3. Trở lại nút gốc 2, thăm nút 2.

4. Duyệt cây con phải của 2 là 5.

5. Từ 5, duyệt cây con trái của 5 là 3.

6. Cây con trái của 3 là null, thăm nút 3.

7. Duyệt cây con phải của 3 là 4.

8. Cây con trái và cây con phải của 4 đều là null. Thăm nút 4.

9. Trở lại nút 5, thăm nút 5.

10. Duyệt cây con phải của 5 là 6, không có cây con trái và cây con phải. Thăm nút 6.

Danh sách giá trị khóa các nút theo thứ tự giữa là: 1, 2, 3, 4, 5, 6

Nhận xét đặc điểm của cây nhị phân cùng danh sách được đưa ra:

- Điều này phù hợp với đặc điểm của cây tìm kiếm nhị phân (BST). Trong cây tìm kiếm nhị phân, khi duyệt theo thứ tự giữa, các giá trị khóa luôn được liệt kê theo thứ tự tăng dần.

- Danh sách giá trị khóa được duyệt theo thứ tự giữa (In-order Traversal) của cây nhị phân này là một dãy các giá trị tăng dần.

- Như vậy, cây nhị phân này cũng là một cây tìm kiếm nhị phân.

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 250K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 250K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 250K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Xem trọn bộ đề thi 7 câu hỏi
Xem thêm