Chuyên đề Tin 12 CTST Bài 2.2. Các phép toán duyệt cây nhị phân

Mảng một chiều để biểu diễn các giá trị trong cây nhị phân như sau:

[2, 24, 11, None, 3, 8, 9]

Phép toán duyệt cây nhị phân tạo ra kết quả ở bảng trên này là duyệt in-order. Ta sẽ thăm nút con bên trái, sau đó là nút hiện tại, và cuối cùng là nút con bên phải. Đối với cây tìm kiếm nhị phân, phép duyệt này sẽ cho kết quả là các giá trị được sắp xếp theo thứ tự tăng dần.

Cách biểu diễn các giá trị của cây bằng mảng một chiều theo ba phép duyệt:

a) Duyệt trước (Pre-order): Thăm nút gốc trước, sau đó là cây con bên trái và cuối cùng là cây con bên phải. [20,24,14,None,None,None,None,None,None,None,None]

b) Duyệt giữa (In-order): Thăm cây con bên trái trước, sau đó là nút gốc và cuối cùng là cây con bên phải. None,None,None,None]

c) Duyệt sau (Post-order): Thăm cây con bên trái trước, sau đó là cây con bên phải và kết thúc ở nút gốc. [None]

Cho cây nhị phân như Hình 8. Biểu diễn các giá trị trong cây nhị phân bằng mảng một chiều theo:

a) Duyệt trước: Thăm nút gốc trước, sau đó là cây con bên trái và cuối cùng là cây con bên phải.

[20,24,14,None,None,None,None,None,None,None,None]

b) Duyệt giữa: Thăm cây con bên trái trước, sau đó là nút gốc và cuối cùng là cây con bên phải.

[None,None,None,None]

c) Duyệt sau: Thăm cây con bên trái trước, sau đó là cây con bên phải và kết thúc ở nút gốc.

[None]        

Cho các thao tác: (1) Duyệt nút gốc; (2) Duyệt cây con trái; (3) Duyệt cây con phải. Sắp xếp thứ tự các thao tác tương ứng với các phép toán duyệt cây nhị phân:

a) Duyệt trước:

Thao tác: Duyệt nút gốc -> Duyệt cây con trái -> Duyệt cây con phải

Thứ tự: (1) -> (2) -> (3)

b) Duyệt giữa:

Thao tác: Duyệt cây con trái -> Duyệt nút gốc -> Duyệt cây con phải

Thứ tự: (2) -> (1) -> (3)

c) Duyệt sau:

Thao tác: Duyệt cây con trái -> Duyệt cây con phải -> Duyệt nút gốc

Thứ tự: (2) -> (3) -> (1)

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