Cho mảng số nguyên dương A = [5, 8, 7, 4, 9, 2). Xây dựng cây nhị phân
Cho mảng số nguyên dương A = [5, 8, 7, 4, 9, 2).
Giải Chuyên đề Tin 12 Bài 2.2: Các phép toán duyệt cây nhị phân - Chân trời sáng tạo
Thực hành trang 39 Chuyên đề Tin học 12: Cho mảng số nguyên dương A = [5, 8, 7, 4, 9, 2).
a) Xây dựng cây nhị phân với mảng số nguyên dương trên.
b) Sử dụng phép toán duyệt trước, duyệt giữa, duyệt sau để xuất thứ tự các giá trị trên
cây nhị phân được xây dựng ở câu a).
Lời giải:
Cho mảng số nguyên dương A = [5, 8, 7, 4, 9, 2).
a) Xây dựng cây nhị phân với mảng số nguyên dương: A = [5, 8, 7, 4, 9, 2).
- Phần tử đầu tiên 5 là gốc.
- lớn hơn 5, đặt vào cây con phải của 5.
- 7 nhỏ hơn 8, đặt vào cây con trái của 8.
- 4 nhỏ hơn 5, đặt vào cây con trái của 5.
- 9 lớn hơn 8, đặt vào cây con phải của 8.
- 2 nhỏ hơn 4, đặt vào cây con trái của 4.
b) Sử dụng phép toán duyệt trước, duyệt giữa, duyệt sau để xuất thứ tự các giá trị trên cây nhị phân được xây dựng ở câu a).
- Duyệt trước (Pre-order traversal):
Duyệt nút gốc -> Duyệt cây con trái -> Duyệt cây con phải
Thứ tự: 5 -> 4 -> 2 -> 8 -> 7 -> 9
- Duyệt giữa (In-order traversal):
Duyệt cây con trái -> Duyệt nút gốc -> Duyệt cây con phải
Thứ tự: 2 -> 4 -> 5 -> 7 -> 8 -> 9
- Duyệt sau (Post-order traversal):
Duyệt cây con trái -> Duyệt cây con phải -> Duyệt nút gốc
Thứ tự: 2 -> 4 -> 7 -> 9 -> 8 -> 5
Lời giải bài tập Chuyên đề Tin 12 Bài 2.2: Các phép toán duyệt cây nhị phân hay, chi tiết khác: