Duyệt cây: Khám phá những bí ẩn đằng sau cây

Việc duyệt cây có vai trò quan trọng trong khoa học máy tính. Hãy cùng tìm hiểu về thuật toán duyệt cây và các phương pháp điều khiển thứ tự.

Duyệt cây nhị phân

Khi duyệt một cây nhị phân, việc thăm các đỉnh theo một thứ tự nhất định rất quan trọng. Chúng ta có thể xem xét cây theo thứ tự viếng thăm đỉnh A trước, sau đó viếng thăm hai con của nó, hoặc viếng thăm A giữa việc thăm hai con, thậm chí có thể thăm A sau khi đã viếng thăm hai con.

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

Tuỳ theo thứ tự viếng thăm đỉnh A và hai con của nó, chúng ta có ba phương pháp duyệt cây nhị phân: duyệt tiền thứ tự, trung thứ tự, và hậu thứ tự.

Duyệt tiền thứ tự

Chúng ta duyệt A, sau đó duyệt cây con gốc trái, và cuối cùng là duyệt cây con gốc phải.

Duyệt trung thứ tự

Chúng ta duyệt cây con gốc trái, sau đó duyệt A, và cuối cùng là duyệt cây con gốc phải.

Duyệt hậu thứ tự

Chúng ta duyệt cây con gốc trái, duyệt cây con gốc phải, và cuối cùng là duyệt A.

Ví dụ

Hãy xem một ví dụ về việc duyệt cây nhị phân này. Giả sử chúng ta có cây nhị phân sau:

          A
        /   \
       B     C
            / \
           D   E
          / \   \
         F   G   H

Với cây này, chúng ta có thể thực hiện duyệt tiền, trung, và hậu thứ tự như sau:

Duyệt tiền thứ tự: A, B, C, D, F, G, E, H Duyệt trung thứ tự: B, A, F, D, G, C, E, H Duyệt hậu thứ tự: B, F, G, D, H, E, C, A

Duyệt cây tổng quát

Ngoài việc duyệt cây nhị phân, chúng ta cũng có thể duyệt cây tổng quát. Phương pháp duyệt theo mức là một cách khác để duyệt cây. Chúng ta bắt đầu từ gốc, sau đó duyệt các con từ trái sang phải và tiếp tục duyệt các đỉnh ở các mức sau.

Giả mã

Để thực hiện việc duyệt cây, chúng ta có thể viết các hàm như sau:

Duyệt tiền thứ tự

visit(node)
print node.value
if node.left != null then visit(node.left)
if node.right != null then visit(node.right)

Duyệt hậu thứ tự

visit(node)
if node.left != null then visit(node.left)
if node.right != null then visit(node.right)
print node.value

Duyệt trung thứ tự

visit(node)
if node.left != null then visit(node.left)
print node.value
if node.right != null then visit(node.right)

Kết luận

Duyệt cây là một khám phá thú vị trong lĩnh vực khoa học máy tính. Việc điều khiển thứ tự khi duyệt cây nhị phân và cây tổng quát giúp chúng ta hiểu rõ hơn về cấu trúc của cây và khả năng sử dụng của chúng. Hãy khám phá thêm về việc duyệt cây và áp dụng trong các bài toán thực tế.