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.

Hướng dẫn các bước duyệt cây theo thứ tự giữa:

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:

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

●        Đ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.

●        Như vậy, cây nhị phân này cũng là một cây tìm kiếm nhị phân.