Trong lý thuyết cây nhị phân, việc duyệt qua các nút của cây là một hoạt động cơ bản, giúp trích xuất và xử lý thông tin từ cấu trúc dữ liệu cây. Có bốn phương pháp duyệt cơ bản thường được sử dụng: Duyệt trước (Pre-order), Duyệt giữa (In-order), Duyệt sau (Post-order), và Duyệt theo chiều rộng (Level-order traversal).
Duyệt trước (Pre-order Traversal) là phương pháp duyệt mà ở đó mỗi nút được xử lý trước các nút con của nó. Trong quá trình duyệt trước, nút hiện tại được thăm trước, sau đó là duyệt qua nút con bên trái và cuối cùng là nút con bên phải. Cách tiếp cận này thích hợp khi bạn muốn sao chép hoặc kiểm tra cấu trúc cây từ gốc.
Duyệt giữa (In-order Traversal), một phương pháp duyệt mà nút con bên trái được duyệt trước, tiếp theo là nút hiện tại và cuối cùng là nút con bên phải. Điều này tạo ra một kết quả duyệt qua cây theo thứ tự tăng dần, đặc biệt hữu ích trong các cây tìm kiếm nhị phân vì nó truy xuất dữ liệu trong một trật tự có tổ chức.
Duyệt sau (Post-order Traversal) là phương pháp mà ở đó nút hiện tại được xử lý sau cả hai nút con của nó. Quy trình này bắt đầu từ nút con bên trái, sau đó đến nút con bên phải và cuối cùng là nút hiện tại. Duyệt sau thích hợp cho các tác vụ như tính toán kích thước hoặc giải phóng bộ nhớ của cây, vì nó đảm bảo rằng các nút con được xử lý trước khi đến nút cha.
Cuối cùng, Duyệt theo chiều rộng (Level-order Traversal), khác biệt với ba phương pháp trước ở chỗ nó duyệt qua cây theo từng tầng, từ trên xuống dưới và từ trái sang phải. Điều này đòi hỏi sử dụng một hàng đợi để theo dõi nút nào cần được xử lý tiếp theo. Duyệt theo chiều rộng cung cấp cái nhìn tổng quan về cấu trúc của cây và được sử dụng trong các tác vụ như tìm kiếm rộng hoặc cân bằng lại cây.
Mỗi phương pháp duyệt mang lại những ưu điểm riêng và được chọn dựa trên mục tiêu cụ thể của tác vụ liên quan đến cây nhị phân. Việc hiểu biết và biết cách áp dụng linh hoạt các phương pháp duyệt này là cần thiết trong việc xử lý hiệu quả các vấn đề liên quan đến cây nhị phân.
Ví dụ: Xác định thứ tự trước, thứ tự đặt hàng sau và truyền qua thứ tự của Binary Trees như thể hiện trong hình:
Giải pháp: Việc đặt preorder, postorder và inorder traversal như sau:
Các thuật toán duyệt cây
Duyệt trước (Pre-order Traversal)
Duyệt trước (Pre-order Traversal) là một phương pháp duyệt cây nhị phân nơi mỗi nút được xử lý trước khi duyệt qua các nút con của nó. Quy tắc cơ bản của duyệt trước là “Xử lý Nút – Duyệt Con Trái – Duyệt Con Phải”. Trong ngữ cảnh của một cây nhị phân, “xử lý nút” thường có nghĩa là thực hiện một hành động như in giá trị của nút, lưu giá trị đó vào một danh sách, hoặc thực hiện một phép tính.
Thuật toán cho duyệt trước bắt đầu từ nút gốc của cây, xử lý nút đó (thường là in ra giá trị hoặc thêm vào một danh sách), sau đó đệ quy áp dụng cùng một quy trình cho nút con bên trái trước, tiếp theo là nút con bên phải. Thuật toán tiếp tục cho đến khi đạt được nút lá, sau đó quay trở lại nút cha và tiếp tục duyệt qua các nút còn lại theo cùng một cách.
Ví dụ, xét cây nhị phân với nút gốc là A, có hai nút con là B (trái) và C (phải), và nút B lại có hai nút con là D (trái) và E (phải). Quá trình duyệt trước sẽ là A -> B -> D -> E -> C. Điều này có nghĩa là nút A được xử lý trước, sau đó thuật toán chuyển xuống nút B, tiếp tục với nút D và E trước khi quay lại và chuyển sang nút C.
Ứng dụng của duyệt trước rất đa dạng và bao gồm việc sao chép cây nhị phân, vì quá trình duyệt đảm bảo rằng mỗi nút được xử lý trước khi tạo ra các bản sao của các nút con của nó. Duyệt trước cũng được sử dụng trong việc biểu diễn cây nhị phân dưới dạng một chuỗi các nút (ví dụ, cho việc lưu trữ hoặc truyền thông tin cây), cũng như trong việc xây dựng cây biểu thức từ biểu thức tiền tố. Sự hiểu biết về duyệt trước và khả năng áp dụng nó trong các tình huống cụ thể là chìa khóa cho việc xử lý hiệu quả các cấu trúc dữ liệu dựa trên cây nhị phân.
Duyệt giữa (In-order Traversal)
Duyệt giữa (In-order Traversal) là một kỹ thuật duyệt cây nhị phân mà ở đó mỗi nút được xử lý giữa lúc duyệt qua nút con bên trái và nút con bên phải của nó. Cách tiếp cận này tuân theo quy tắc “Duyệt Con Trái – Xử lý Nút – Duyệt Con Phải”, đảm bảo rằng tất cả nút con bên trái của một nút được duyệt qua trước nút đó, và tất cả nút con bên phải được duyệt sau.
Thuật toán cho duyệt giữa bắt đầu từ nút gốc, tiếp tục duyệt qua cây con bên trái đệ quy, sau đó xử lý nút hiện tại (ví dụ: in giá trị của nút hoặc thêm nó vào danh sách), và cuối cùng duyệt qua cây con bên phải. Quy trình này tiếp tục cho đến khi đạt được nút lá, sau đó thuật toán sẽ quay trở lại và duyệt qua phần còn lại của cây theo cùng một cách.
Một ví dụ minh họa cho duyệt giữa có thể là một cây nhị phân với cấu trúc như sau: nút gốc là A, có nút con bên trái là B và nút con bên phải là C; nút B lại có một nút con bên trái là D. Quá trình duyệt giữa sẽ là D -> B -> A -> C, nghĩa là nút D được xử lý trước (là nút con bên trái nhất), sau đó là nút B, tiếp theo là nút gốc A, và cuối cùng là nút C.
Ứng dụng của duyệt giữa đặc biệt quan trọng trong các cây tìm kiếm nhị phân (BST – Binary Search Trees), nơi nó được sử dụng để truy xuất dữ liệu được lưu trữ trong cây theo thứ tự tăng dần hoặc giảm dần. Kỹ thuật này giúp biểu diễn dữ liệu một cách có tổ chức và thường được sử dụng trong các tác vụ như in tất cả phần tử của cây theo thứ tự sắp xếp, hoặc trong việc chuyển đổi cây nhị phân tìm kiếm thành một danh sách hoặc mảng đã sắp xếp. Hiểu biết về duyệt giữa và khả năng áp dụng nó trong các tình huống cụ thể mở ra cánh cửa cho việc xử lý hiệu quả và có tổ chức các cấu trúc dữ liệu dựa trên cây.
Duyệt sau (Post-order Traversal)
Duyệt sau (Post-order Traversal) là một phương pháp duyệt cây nhị phân nơi mỗi nút được xử lý sau khi tất cả các nút con của nó đã được duyệt qua. Quy tắc cơ bản của duyệt sau là “Duyệt Con Trái – Duyệt Con Phải – Xử lý Nút”, đảm bảo rằng cả hai nút con (bên trái và bên phải) của một nút được duyệt qua trước khi nút đó được xử lý.
Thuật toán duyệt sau bắt đầu bằng việc duyệt đệ quy qua cây con bên trái của nút hiện tại, tiếp theo là cây con bên phải, và cuối cùng là xử lý nút hiện tại bằng cách thực hiện một hành động như in giá trị của nút hoặc thêm giá trị đó vào một danh sách. Quá trình này được lặp lại cho đến khi tất cả các nút trong cây đã được duyệt qua.
Ví dụ, xét một cây nhị phân với nút gốc là A, có hai nút con là B (bên trái) và C (bên phải), và B lại có hai nút con là D (bên trái) và E (bên phải). Quá trình duyệt sau cho cây này sẽ là D -> E -> B -> C -> A. Điều này có nghĩa là nút D và E được xử lý trước, sau đó đến nút B, tiếp theo là nút C, và cuối cùng là nút gốc A.
Ứng dụng của duyệt sau rất đa dạng và bao gồm việc giải phóng bộ nhớ của cây nhị phân trong quá trình giải phóng cây (tree destruction), nơi mỗi nút và tài nguyên liên quan phải được giải phóng sau khi tất cả các nút con của nó đã được giải phóng. Phương pháp này cũng được sử dụng trong các tác vụ liên quan đến việc xử lý sau cùng của dữ liệu, như tính toán giá trị của biểu thức toán học được biểu diễn bởi cây biểu thức, nơi giá trị của biểu thức con cần được tính toán trước khi áp dụng toán tử tại nút hiện tại. Duyệt sau cung cấp một cách tự nhiên để xử lý các nút từ dưới lên, từ lá đến gốc, phù hợp với các tình huống đòi hỏi việc xử lý hoặc tổng hợp thông tin từ các nút con trước khi có thể xử lý nút cha.
Duyệt theo chiều rộng (Level-order Traversal)
Duyệt theo chiều rộng (Level-order Traversal) là một phương pháp duyệt cây nhị phân mà ở đó các nút được xử lý tầng này trước, rồi mới đến tầng tiếp theo, từ trên xuống dưới và từ trái sang phải trong mỗi tầng. Khác biệt với các phương pháp duyệt sâu như duyệt trước, duyệt giữa, và duyệt sau, duyệt theo chiều rộng tập trung vào việc duyệt qua cây theo từng tầng, giúp thu thập thông tin theo cấp độ của cây một cách có hệ thống.
Thuật toán cho duyệt theo chiều rộng thường sử dụng một hàng đợi để lưu trữ và theo dõi thứ tự của các nút chờ được xử lý. Bắt đầu bằng việc đưa nút gốc vào hàng đợi, thuật toán tiếp tục bằng cách lấy từng nút ra khỏi hàng đợi, xử lý nó (ví dụ: in giá trị của nút), và sau đó đưa tất cả các nút con của nút đó vào hàng đợi. Quy trình này lặp lại cho đến khi hàng đợi trống.
Ví dụ, xét một cây nhị phân với nút gốc là A, có hai nút con là B (bên trái) và C (bên phải), và tiếp theo B có một nút con bên trái là D, còn C có một nút con bên phải là E. Quá trình duyệt theo chiều rộng sẽ là A -> B -> C -> D -> E, tức là bắt đầu từ nút gốc A, sau đó đến hai nút con của A là B và C, và cuối cùng là D và E, là các nút con của B và C.
Ứng dụng của duyệt theo chiều rộng rất đa dạng, từ việc tìm kiếm nút trong cây nhị phân cho đến việc xây dựng một bản sao của cây với cấu trúc giữ nguyên. Phương pháp này cũng được sử dụng trong việc xác định chiều cao của cây, tìm nút ở mức độ cụ thể, hoặc thậm chí là để kiểm tra tính cân bằng của cây. Trong các ứng dụng khoa học máy tính, duyệt theo chiều rộng hữu ích trong các thuật toán như tìm kiếm theo bề rộng trong mạng lưới hoặc để phân tích mức độ kết nối trong mạng xã hội. Sự hiểu biết về duyệt theo chiều rộng và khả năng áp dụng nó trong các tình huống thực tế là quan trọng trong việc giải quyết các vấn đề liên quan đến cấu trúc dữ liệu cây.
Ví dụ về thuật toán duyệt cây
Hãy xem xét một cây nhị phân ví dụ sau để minh họa việc áp dụng các thuật toán duyệt cây:
A
/ \
B C
/ \ \
D E FTrong cây này, A là nút gốc, B và C là các nút con của A, D và E là các nút con của B, và F là nút con của C.
- Duyệt Trước (Pre-order Traversal)
Quy tắc: Xử lý Nút – Duyệt Con Trái – Duyệt Con Phải
Thứ tự duyệt: A -> B -> D -> E -> C -> F
Giải thích: Bắt đầu từ A, duyệt đến B, sau đó đến D (nút con trái của B), quay lại B rồi đến E (nút con phải của B), sau đó quay lại A và chuyển sang C, cuối cùng đến F (nút con phải của C).
- Duyệt Giữa (In-order Traversal)
Quy tắc: Duyệt Con Trái – Xử lý Nút – Duyệt Con Phải
Thứ tự duyệt: D -> B -> E -> A -> C -> F
Giải thích: Bắt đầu từ nút con trái nhất là D, sau đó quay lại B, rồi đến E. Sau khi duyệt xong cây con B, chúng ta xử lý A, rồi chuyển sang cây con C và cuối cùng là F.
- Duyệt Sau (Post-order Traversal)
Quy tắc: Duyệt Con Trái – Duyệt Con Phải – Xử lý Nút
Thứ tự duyệt: D -> E -> B -> F -> C -> A
Giải thích: Bắt đầu từ D, sau đó đến E, và sau khi duyệt xong cả hai nút con của B, B được xử lý. Tiếp theo, chúng ta di chuyển sang cây con C, bắt đầu từ F, và sau khi F được duyệt, C được xử lý. Cuối cùng, sau khi tất cả các cây con đã được duyệt, nút gốc A được xử lý.
- Duyệt Theo Chiều Rộng (Level-order Traversal)
Quy tắc: Duyệt qua cây theo từng tầng từ trên xuống dưới, từ trái sang phải.
Thứ tự duyệt: A -> B -> C -> D -> E -> F
Giải thích: Bắt đầu từ nút gốc A, sau đó duyệt qua các nút ở tầng tiếp theo là B và C. Tiếp theo, duyệt qua các nút ở tầng thứ ba là D và E (con của B), và cuối cùng là F (con của C).
Mỗi phương pháp duyệt cây mang lại cái nhìn và ứng dụng khác nhau, phù hợp cho các tác vụ cụ thể trong việc xử lý và phân tích cấu trúc dữ liệu cây.
