Duyệt cây trong cấu trúc dữ liệu và giải thuật

Duyệt cây là gì?

Duyệt cây là một tiến trình để truy cập tất cả các nút của một cây và cũng có thể in các giá trị của các nút này. Bởi vì tất cả các nút được kết nối thông qua các cạnh (hoặc các link), nên chúng ta luôn luôn bắt đầu truy cập từ nút gốc. Do đó, chúng ta không thể truy cập ngẫu nhiên bất kỳ nút nào trong cây. Có ba phương thức mà chúng ta có thể sử dụng để duyệt một cây:

Duyệt tiền thứ tự (Pre-order Traversal)

Duyệt trung thứ tự (In-order Traversal)

Duyệt hậu thứ tự (Post-order Traversal)

Nói chung, chúng ta duyệt một cây để tìm kiếm hay là để xác định vị trí phần tử hoặc khóa đã cho trong cây hoặc là để in tất cả giá trị mà cây đó chứa.

Duyệt trung thứ tự trong cây nhị phân

Trong cách duyệt này, cây con bên trái được truy cập đầu tiên, sau đó là nút gốc và sau đó là cây con bên phải. Bạn nên luôn luôn ghi nhớ rằng mỗi nút đều có thể biểu diễn một cây con.

Nếu một cây nhị phân được duyệt trung thứ tự, kết quả tạo ra sẽ là các giá trị khóa được sắp xếp theo thứ tự tăng dần.

Ở hình ví dụ minh họa trên, A là nút gốc. Với phương thức duyệt trung thứ tự, chúng ta bắt đầu từ nút gốc A, di chuyển tới cây con bên trái B của nút gốc. Tại đây, B cũng được duyệt theo cách thức duyệt trung thứ tự. Và tiến trình tiếp tục cho đến khi tất cả các nút đã được truy cập. Kết quả của cách thức duyệt trung thứ tự cho cây trên sẽ là:

D → B → E → A → F → C → G

Giải thuật cho cách duyệt trung thứ tự

Duyệt cho tới khi tất cả các nút đều được duyệt:
Bước 1: Duyệt các cây con bên trái một cách đệ qui
Bước 2: Truy cập nút gốc
Bước 3: Duyệt các cây con bên phải một cách đệ qui

Duyệt tiền thứ tự trong cây nhị phân

Trong cách thức duyệt tiền thứ tự trong cây nhị phân, nút gốc được duyệt đầu tiên, sau đó sẽ duyệt cây con bên trái và cuối cùng sẽ duyệt cây con bên phải.

Ở hình ví dụ minh họa trên, A là nút gốc. Chúng ta bắt đầu từ A, và theo cách thức duyệt tiền thứ tự, đầu tiên chúng ta truy cập chính nút gốc A này và sau đó di chuyển tới nút con bên trái B của nó. B cũng được duyệt theo cách thức duyệt tiền thứ tự. Và tiến trình tiếp tục cho tới khi tất cả các nút đều đã được truy cập. Kết quả của cách thức duyệt tiền thứ tự cây này sẽ là:

A → B → D → E → C → F → G

Giải thuật cho cách duyệt tiền thứ tự

Duyệt cho tới khi tất cả các nút đều được duyệt:
Bước 1: Truy cập nút gốc
Bước 2: Duyệt các cây con bên trái một cách đệ qui
Bước 3: Duyệt các cây con bên phải một cách đệ qui

Duyệt hậu thứ tự trong cây nhị phân

Trong cách thức duyệt hậu thứ tự trong cây nhị phân, nút gốc của cây sẽ được truy cập cuối cùng, do đó bạn cần chú ý. Đầu tiên, chúng ta duyệt cây con bên trái, sau đó sẽ duyệt cây con bên phải và cuối cùng là duyệt nút gốc.

Ở hình ví dụ minh họa trên, A là nút gốc. Chúng ta bắt đầu từ A, và theo cách duyệt hậu thứ tự, đầu tiên chúng ta truy cập cây con bên trái B. B cũng được duyệt theo cách thứ duyệt hậu thứ tự. Và tiến trình sẽ tiếp tục tới khi tất cả các nút đã được truy cập. Kết quả của cách thức duyệt hậu thứ tự của cây con trên sẽ là:

D → E → B → F → G → C → A

Giải thuật cho cách duyệt hậu thứ tự

Duyệt cho tới khi tất cả các nút đều được duyệt:
Bước 1: Duyệt các cây con bên trái một cách đệ qui
Bước 2: Duyệt các cây con bên phải một cách đệ qui
Bước 3: Truy cập nút gốc.

Theo Tutorialspoint

Bài trước: Giải thuật tìm kiếm theo chiều rộng

Bài tiếp: Cây tìm kiếm nhị phân (Binary Search Tree)