Các cách duyệt cây nhị phân tìm kiếm

Vấn đề phụ: Khử đệ quy trong duyệt cây sử dụng stack

Bài toán đặt ra

Duyệt một cây nhị phân tìm kiếm theo chiều rộng (BFS) hoặc theo chiều sâu (DFS) nhưng không sử dụng đệ quy. Ý tưởng ở đây là sử dụng hai kiểu cấu trúc dữ liệu quen thuộc là Stack (Ngăn xếp) và Queue (Hàng đợi) để xử lý vấn đề này.

Giả sử chúng ta có cây nhị phân tìm kiếm như sau:

Cây nhị phân tìm kiếm

Cách cài đặt thuật toán thông dụng nhất để duyệt cây nhị phân tìm kiếm theo chiều sâu (Deep First Search) là sử dụng đệ quy. Đây là ví dụ cài đặt thuật toán trong ngôn ngữ C++:

Thuật toán duyệt theo chiều sâu

Kết quả khi chạy chương trình

Ưu điểm của cách triển khai thuật toán duyệt cây sử dụng đệ quy là code tương đối ngắn gọn, tường minh, dễ đọc hiểu.

Tại sao phải khử đệ quy ?

Trong trường hợp tổng quát, khử đệ quy là một việc làm khá phức tạp và khó khăn. Ở hàm tính giai thừa hay tính số fibonacci, ta có thể dùng một thuật toán không đệ quy, nhưng trong một số bài toán, đệ quy là bắt buộc. Bạn có thể nói rằng, vậy thì cứ sử dụng đệ quy, vừa ngắn gọn dễ hiểu, vừa dễ cài đặt. Nhưng có đôi khi, sự hạn hẹp của bộ nhớ dành cho chương trình con không cho phép chúng ta làm điều đó; hoặc chúng ta biết rằng, ngôn ngữ máy không có đệ quy, vì vậy các trình biên dịch đều phải có nhiệm vụ khử đệ quy. Và bạn có thể thực sự gặp rắc rối với thủ tục đệ quy của mình khi trong một môi trường lập trình mà không cung cấp khả năng gọi đệ quy. Khử đệ quy giúp bạn vẫn giữ được nguyên bản thuật toán đệ quy của mình mà không hề có lời gọi đệ quy, và như thế chương trình có thể chạy được trong bất kỳ môi trường lập trình nào.

– ToidammeIT –

Khử đệ quy như thế nào?

Khử đệ quy thực chất là chúng ta phải làm công việc của một trình biên dịch đối với một thủ tục, đó là: Đặt tất cả các giá trị của các biến cục bộ và địa chỉ của chỉ thị kế tiếp vào ngăn xếp (Stack), quy định các giá trị tham số cho thủ tục và chuyển tới vị trí bắt đầu thủ tục, thực hiện lần lượt từng câu lệnh. Sau khi thủ tục hoàn tất thì nó phải lấy ra khỏi ngăn xếp địa chỉ trả về và các giá trị của các biến cục bộ, khôi phục các biến và chuyển tới địa chỉ trả về.

Cụ thể trong ví dụ bên trên, chúng ta sẽ triển khai thuật toán như sau:

So sánh về thuật toán và kết quả giữa 2 phương pháp duyệt cây

Đối với thuật toán duyệt cây nhị phân theo chiều sâu sử dụng stack, đầu tiên chúng ta sẽ push nút gốc vào stack. Sau đó, chạy vòng lặp while kiểm tra xem stack có rỗng hay không. Nếu stack không rỗng thì lần lượt pop từng phần tử ra, in giá trị của phần tử đó và push tiếp lần lượt 2 phần tử con bên phải và bên trái vào stack rồi quay lại đầu vòng lặp. Quá trình này sẽ kết thúc khi toàn bộ nút lá được pop khỏi stack (không còn phần tử con bên trái hay bên phải nào được push vào stack nữa).

Duyệt cây theo chiều rộng (BFS)

Ý tưởng duyệt cây theo chiều rộng là chúng ta sẽ sử dụng tính chất FIFO của hàng đợi, để lần lượt đưa vào hàng đợi (enqueue) các node theo từng mức, sau đó đưa ra khỏi hàng đợi (dequeue) lần lượt các phần tử để xử lý. Cụ thể với ví dụ cây bên trên như sau:

Đầu tiên, node gốc (5) được đưa vào trong queue.

Hình ảnh minh họa cho hàng đợi

Nhận thấy hàng đợi hiện tại (chiều mũi tên màu cam) không rỗng, bắt đầu thực hiện các công đoạn sau:

• Bước 1: Dequeue phần tử đầu tiên của hàng đợi (Chuyển sang ô có mũi tên màu đỏ)
• Bước 2: In phần tử đã được dequeue (In ô có mũi tên màu đỏ ra màn hình)
• Bước 3: Thêm 2 phần tử con bên trái và bên phải (nếu có) của phần tử đã được dequeue vào hàng đợi
• Bước 4: Nếu hàng đợi không rỗng, quay lại bước 1
• Bước 5: Kết thúc

Mô phỏng trực quan từng bước của chương trình:

Mô phỏng từng bước chạy cho đến khi kết thúc thuật toán (hàng đợi rỗng)

Triển khai thuật toán bằng ngôn ngữ C++

Kết quả khi chạy chương trình

Tóm lại, cách duyệt DFS sử dụng đệ quy, stack hoặc duyệt cây theo chiều rộng đều có những ưu nhược điểm riêng, cần lựa chọn phương pháp phù hợp theo yêu cầu của phần mềm. Hi vọng bài viết này sẽ giúp bạn có cái nhìn rõ hơn về các phương pháp duyệt cây thông qua những ví dụ bên trên.