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).

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]:

Một cách phổ biến để xây dựng cây nhị phân từ một mảng là xây dựng cây nhị phân tìm kiếm (Binary Search Tree - BST). Quy tắc để xây dựng BST từ mảng là:

1. Bắt đầu với phần tử đầu tiên làm gốc.

2. Với mỗi phần tử tiếp theo, nếu nó nhỏ hơn nút hiện tại thì đặt vào cây con trái, nếu nó lớn hơn hoặc bằng thì đặt vào cây con phải.

Ta xây dựng cây nhị phân từ mảng A như sau:

• Phần tử đầu tiên 5 là gốc.

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

Cây nhị phân được xây dựng như sau:

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:

1. 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

2. 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

3. 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

Tóm lại, thứ tự các giá trị trên cây nhị phân khi duyệt là:

• Duyệt trước: 5, 4, 2, 8, 7, 9

• Duyệt giữa: 2, 4, 5, 7, 8, 9

• Duyệt sau: 2, 4, 7, 9, 8, 5