Truyền tải theo thứ tự DSA
Truyền tải theo thứ tự cây nhị phân
Traversal theo thứ tự là một loại Tìm kiếm theo chiều sâu, trong đó mỗi nút được truy cập theo một thứ tự nhất định. Đọc thêm về việc duyệt cây nhị phân nói chung tại đây .
Chạy hoạt ảnh bên dưới để xem cách thực hiện Truyền tải theo thứ tự của Cây nhị phân.
Kết quả:
Truyền tải theo thứ tự thực hiện Truyền tải theo thứ tự đệ quy của cây con bên trái, truy cập nút gốc và cuối cùng thực hiện Truyền tải theo thứ tự đệ quy của cây con bên phải. Việc truyền tải này chủ yếu được sử dụng cho Cây tìm kiếm nhị phân trong đó nó trả về các giá trị theo thứ tự tăng dần.
Điều làm cho việc truyền tải này diễn ra theo thứ tự "theo thứ tự" là nút được truy cập ở giữa các lệnh gọi hàm đệ quy. Nút được truy cập sau quá trình truyền tải theo thứ tự của cây con bên trái và trước quá trình truyền tải theo thứ tự của cây con bên phải.
Đây là cách mã cho Traversal theo thứ tự trông như thế nào:
Ví dụ
Trăn:
def inOrderTraversal(node):
if node is None:
return
inOrderTraversal(node.left)
print(node.data, end=", ")
inOrderTraversal(node.right)
Chạy ví dụ » Hàm inOrderTraversal()
tiếp tục gọi chính nó với nút con bên trái hiện tại làm đối số (dòng 4) cho đến khi đối số đó là None
và hàm trả về (dòng 2-3).
Lần đầu tiên node
đối số là None
là khi nút con trái của nút C được đưa ra làm đối số (C không có nút con trái).
Sau đó, phần data
của nút C được in (dòng 5), có nghĩa là 'C' là thứ đầu tiên được in.
Sau đó, nút con bên phải của nút C được đưa ra làm đối số (dòng 6), là None
, do đó lệnh gọi hàm trả về mà không làm gì khác.
Sau khi 'C' được in, lệnh gọi hàm inOrderTraversal()
trước đó tiếp tục chạy, do đó 'A' được in, sau đó là 'D', rồi 'R', v.v.