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ạn nên đọc
-
Trọng tâm là gì? Công thức tính trọng tâm của tam giác
-
Các công thức đạo hàm và đạo hàm lượng giác đầy đủ nhất
-
Công thức tính diện tích hình chóp
-
Công thức tính diện tích tam giác: vuông, thường, cân, đều
-
Chuyển từ cơ số 16 sang cơ số 2
-
Công thức tính đường chéo hình vuông, đường chéo hình chữ nhật
-
Bí mật thú vị ẩn giấu bên trong dòng mã nhị phân trên tờ 50 bảng Anh in hình Alan Turing
-
Công thức tính tỉ số thể tích các khối đa diện
Theo Nghị định 147/2024/ND-CP, bạn cần xác thực tài khoản trước khi sử dụng tính năng này. Chúng tôi sẽ gửi mã xác thực qua SMS hoặc Zalo tới số điện thoại mà bạn nhập dưới đây:

Cũ vẫn chất
-
Google One là gì? 4 lý do tại sao nên sử dụng Google One
Hôm qua -
Build Ixtal DTCL, các đội hình Ixtal DTCL 9.5
Hôm qua -
Lỗi dấu thăng (####) trong Excel là lỗi gì?
Hôm qua -
Cách xem video YouTube giới hạn độ tuổi mà không cần đăng nhập
Hôm qua -
Plant Empires - Merge Defense Monster
-
Cách tưởng nhớ trên Facebook
Hôm qua -
Khắc phục sự cố click chuột phải trên Windows 10
Hôm qua -
Khai báo biến trong SQL Server
Hôm qua -
Cách viết chữ lên ảnh trong Google Docs
Hôm qua -
Cách kết nối tay cầm PS5 với PC Windows, Mac, Steam
Hôm qua