Duyệt cây nhị phân¶

Dưới góc độ cấu trúc vật lý, cây là cấu trúc dữ liệu dựa trên danh sách liên kết (linked list). Do đó, phương pháp duyệt của nó bao gồm việc truy cập lần lượt các nút thông qua con trỏ. Tuy nhiên, cây là một cấu trúc dữ liệu phi tuyến tính, điều này làm cho việc duyệt cây trở nên phức tạp hơn so với việc duyệt danh sách liên kết, đòi hỏi sự hỗ trợ của các thuật toán tìm kiếm.

Các phương pháp duyệt cây nhị phân (binary tree) phổ biến bao gồm duyệt theo mức (level-order traversal), duyệt tiền thứ tự (preorder traversal), duyệt trung thứ tự (inorder traversal) và duyệt hậu thứ tự (postorder traversal).

Duyệt theo mức¶

Như được thể hiện trong hình dưới đây, duyệt theo mức (level-order traversal) duyệt qua cây nhị phân từ trên xuống dưới, từng tầng một. Trong mỗi tầng, nó truy cập các nút từ trái qua phải.

Duyệt theo mức về mặt bản chất là duyệt theo chiều rộng (breadth-first traversal), còn được gọi là tìm kiếm theo chiều rộng (BFS), tiến dần ra ngoài theo từng tầng.

Triển khai mã nguồn¶

Duyệt theo chiều rộng thường được triển khai với sự trợ giúp của một "hàng đợi" (queue). Hàng đợi tuân theo quy tắc "vào trước, ra trước" (first in, first out), còn duyệt theo chiều rộng tuân theo quy tắc "tiến triển theo từng tầng"; ý tưởng cốt lõi của cả hai là nhất quán. Mã nguồn triển khai như sau:

[file]{binary_tree_bfs}-[class]{}-[func]{level_order}

Phân tích độ phức tạp¶

Độ phức tạp thời gian là \(O(n)\): Tất cả các nút được truy cập một lần, tốn thời gian \(O(n)\), với \(n\) là số lượng nút.
Độ phức tạp không gian là \(O(n)\): Trong trường hợp xấu nhất, tức là cây nhị phân đầy đủ (full binary tree), trước khi duyệt đến tầng cuối cùng, hàng đợi chứa tối đa \((n + 1) / 2\) nút cùng lúc, chiếm dụng không gian \(O(n)\).

Duyệt tiền thứ tự, trung thứ tự và hậu thứ tự¶

Tương ứng, duyệt tiền thứ tự, trung thứ tự và hậu thứ tự đều thuộc về duyệt theo chiều sâu (depth-first traversal), còn được gọi là tìm kiếm theo chiều sâu (DFS), đi sâu nhất có thể trước khi quay lui.

Hình dưới đây thể hiện cách hoạt động của duyệt theo chiều sâu trên cây nhị phân. Duyệt theo chiều sâu giống như việc "đi bộ" quanh chu vi của toàn bộ cây nhị phân, đi qua ba vị trí tại mỗi nút, tương ứng với duyệt tiền thứ tự, trung thứ tự và hậu thứ tự.

Triển khai mã nguồn¶

Tìm kiếm theo chiều sâu thường được triển khai dựa trên đệ quy (recursion):

[file]{binary_tree_dfs}-[class]{}-[func]{post_order}

Tip

Tìm kiếm theo chiều sâu cũng có thể được triển khai bằng phương pháp lặp (iterative), độc giả quan tâm có thể tự mình tìm hiểu thêm.

Hình dưới đây thể hiện quy trình đệ quy của duyệt tiền thứ tự trên cây nhị phân, có thể chia thành hai giai đoạn đối lập nhau: "đi xuống" (descending) và "trở về" (returning).

"Đi xuống" nghĩa là thực hiện một cuộc gọi đệ quy mới, trong đó chương trình sẽ truy cập nút tiếp theo.
"Trở về" nghĩa là cuộc gọi hàm trả về, cho biết nút hiện tại đã được xử lý hoàn toàn.

Phân tích độ phức tạp¶

Độ phức tạp thời gian là \(O(n)\): Tất cả các nút được truy cập một lần, tốn thời gian \(O(n)\).
Độ phức tạp không gian là \(O(n)\): Trong trường hợp xấu nhất, tức là khi cây bị suy biến thành danh sách liên kết, độ sâu đệ quy đạt tới \(n\) và hệ thống sẽ chiếm dụng không gian khung ngăn xếp (stack frame) là \(O(n)\).