Tổng quan
Duyệt trung thứ tự (inorder) là cách duyệt theo chiều sâu, thăm mọi nút của cây nhị phân theo thứ tự Trái, Gốc, Phải. Nó duyệt hết cây con trái của một nút, rồi thăm chính nút đó, cuối cùng duyệt cây con phải.
Tính chất đặc trưng của nó là trên một Cây Tìm Kiếm Nhị Phân (BST), duyệt inorder cho ra các khóa theo thứ tự tăng dần, nên đây là cách tự nhiên để đọc lần lượt toàn bộ một BST.
Duyệt Inorder hoạt động thế nào?
- Bắt đầu từ gốc, duyệt đệ quy toàn bộ cây con trái trước.
- Thăm (xử lý) nút hiện tại ngay khi cây con trái đã duyệt xong.
- Duyệt đệ quy cây con phải.
- Trường hợp cơ sở là cây con rỗng (null), khi đó đệ quy chỉ đơn giản trả về.
Khi nào nên dùng?
- Đọc các khóa của Cây Tìm Kiếm Nhị Phân theo thứ tự đã sắp mà không cần bước sắp riêng.
- Kiểm tra một cây có đúng là BST hay không bằng cách xác nhận dãy duyệt tăng nghiêm ngặt.
- Tìm nút liền trước hoặc liền sau theo thứ tự trong các thao tác trên BST.
Phân tích độ phức tạp
Duyệt inorder thăm mỗi nút đúng một lần, nên chạy trong O(n) thời gian. Ngăn xếp đệ quy sâu bằng chiều cao cây h, dùng O(h) bộ nhớ — O(log n) với cây cân bằng và O(n) với cây suy biến dạng chuỗi.
Câu hỏi thường gặp
Vì sao duyệt inorder cho kết quả đã sắp trên BST?
Trong BST, mọi khóa ở cây con trái nhỏ hơn nút và mọi khóa ở cây con phải lớn hơn nút. Vì vậy thăm theo Trái, Gốc, Phải sẽ phát ra các khóa từ nhỏ đến lớn.
Có thể duyệt inorder mà không cần đệ quy không?
Có. Một ngăn xếp tường minh mô phỏng đệ quy, và duyệt Morris còn đạt O(1) bộ nhớ phụ bằng cách tạm nối các con trỏ phải null thành liên kết quay về tổ tiên.