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ê

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