Em hãy đưa ra danh sách giá trị khóa các nút ở cây nhị phân (Hình 1)

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

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 cây theo thứ tự giữa và nhận xét đặc điểm của cây nhị phân cùng danh sách được đưa ra nà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à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:

• 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ừ ....

• 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
• Giải lớp 12 Kết nối tri thức (các môn học)
• Giải lớp 12 Chân trời sáng tạo (các môn học)
• Giải lớp 12 Cánh diều (các môn học)

---