An và Hòa cùng tham gia một hoạt động về bài toán trên dãy số. Giả sử các phần từ 45, 35, 60

Giải Chuyên đề Tin 12 Bài 3: Cây tìm kiếm nhị phân - Cánh diều

Hoạt động 1 trang 43 Chuyên đề Tin học 12: An và Hòa cùng tham gia một hoạt động về bài toán trên dãy số. Giả sử các phần từ 45, 35, 60, 30, 46, 75, 11, 55, 65, 96, 12, 58 của tập số An giữ được biểu diễn dưới dạng cây nhị phân trong Hình 2, các nút được đánh chỉ số từ 0 đến 11. Em hãy quan sát đặc điểm của cây và các giá trị khóa từng nút của cây này, tử đó đưa ra một cách giúp Hoa đạt ít câu hỏi nhất cô thế để tim ra vị trí nút có giá trị khoá 55.

Lời giải:

An và Hòa cùng tham gia một hoạt động về bài toán trên dãy số. Giả sử các phần từ 45, 35, 60, 30, 46, 75, 11, 55, 65, 96, 12, 58 của tập số An giữ được biểu diễn dưới dạng cây nhị phân trong Hình 2, các nút được đánh chỉ số từ 0 đến 11. Hướng dẫn các bước xây dựng cây BST từ dãy số [45, 35, 60, 30, 46, 75, 11, 55, 65, 96, 12, 58]:

1. Bắt đầu với 45 là gốc.

2. Chèn 35: 35 < 45, nên 35 là con trái của 45.

3. Chèn 60: 60 > 45, nên 60 là con phải của 45.

4. Chèn 30: 30 < 45 và 30 < 35, nên 30 là con trái của 35.

5. Chèn 46: 46 > 45 và 46 < 60, nên 46 là con trái của 60.

6. Chèn 75: 75 > 45 và 75 > 60, nên 75 là con phải của 60.

7. Chèn 11: 11 < 45 và 11 < 35 và 11 < 30, nên 11 là con trái của 30.

8. Chèn 55: 55 > 45 và 55 < 60 và 55 > 46, nên 55 là con phải của 46.

9. Chèn 65: 65 > 45 và 65 > 60 và 65 < 75, nên 65 là con trái của 75.

10. Chèn 96: 96 > 45 và 96 > 60 và 96 > 75, nên 96 là con phải của 75.

11. Chèn 12: 12 < 45 và 12 < 35 và 12 < 30 và 12 > 11, nên 12 là con phải của 11.

12. Chèn 58: 58 > 45 và 58 < 60 và 58 > 46 và 58 > 55, nên 58 là con phải của 55.

Cây BST sẽ có cấu trúc như sau:

Thực hiện theo các bước sau để tìm giá trị khóa 55,

1. So sánh với nút gốc (45):

• 55 > 45: đi tới cây con phải (60).

2. So sánh với nút 60:

• 55 < 60: đi tới cây con trái (46).

3. So sánh với nút 46:

• 55 > 46: đi tới cây con phải (55).

4. So sánh với nút 55:

• 55 = 55: tìm thấy giá trị khóa.

Vậy, chỉ cần 4 bước so sánh để tìm ra nút có giá trị khóa 55 trong cây này.

 

Lời giải bài tập Chuyên đề Tin 12 Bài 3: Cây tìm kiếm nhị phân hay, chi tiết khác:

• Khởi động trang 43 Chuyên đề Tin học 12: Em hãy đưa ra danh sách giá trị khóa các nút ở cây nhị phân (Hình 1) trong phép duyệt ....

• Thực hành trang 45 Chuyên đề Tin học 12: Từ cây tìm kiểm nhị phân trong Hình 3 sau khi đã chèn thêm nút có giá trị khóa 33 ....

• Thực hành trang 47 Chuyên đề Tin học 12: Từ cây tìm kiểm nhị phân trong Hình 5, em hãy mô tả từng bước tìm kiểm một nút có ....

• Vận dụng trang 48 Chuyên đề Tin học 12: 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ả ....

• Câu hỏi tự kiểm tra 1 trang 48 Chuyên đề Tin học 12: Trong các câu sau đây, câu nào là đúng về cây tìm kiếm nhị phân ....

• Câu hỏi tự kiểm tra 2 trang 48 Chuyên đề Tin học 12: Trong cây tìm kiếm nhị phân em vừa xây dựng ở phần vận dụng ....

Xem thêm lời giải bài tập Chuyên đề học tập Tin học 12 Cánh diều hay, chi tiết khác:

• Chuyên đề Tin học 12 Bài 4: Thực hành tổng hợp: Ứng dụng cây tìm kiếm nhị phân

• Chuyên đề Tin học 12 Bài 1: Đồ thị, phân loại đồ thị

• Chuyên đề Tin học 12 Bài 2: Biểu diễn đồ thị trên máy tính

• Chuyên đề Tin học 12 Bài 3: Thực hành các thao tác cơ bản với đồ thị trên máy tính

• Chuyên đề Tin học 12 Bài 4: Duyệt đồ thị

Xem thêm các tài liệu học tốt lớp 12 hay khác:

• Giải Chuyên đề Tin học 12 Kết nối tri thức
• Giải Chuyên đề Tin học 12 Chân trời sáng tạo
• Giải Chuyên đề Tin học 12 Cánh diều

---