Truyền tải đặt hàng trước DSA
Đặt hàng trước việc duyệt cây nhị phân
Traversal đặt hàng trước 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 .
Việc duyệt cây nhị phân theo thứ tự trước trông như thế này:
Kết quả:
Việc duyệt theo thứ tự trước được thực hiện bằng cách truy cập nút gốc trước, sau đó thực hiện duyệt đệ quy theo thứ tự trước cây con bên trái, sau đó là duyệt theo thứ tự trước cây con bên phải. Nó được sử dụng để tạo một bản sao của cây, ký hiệu tiền tố của cây biểu thức, v.v.
Việc duyệt này là thứ tự "trước" vì nút được truy cập "trước" việc duyệt thứ tự trước đệ quy của cây con trái và phải.
Đây là cách mã để truyền tải đơn đặt hàng trước trông như thế nào:
Ví dụ
Trăn:
def preOrderTraversal(node):
if node is None:
return
print(node.data, end=", ")
preOrderTraversal(node.left)
preOrderTraversal(node.right) Chạy ví dụ »Nút đầu tiên được in là nút R, vì Truyền tải đặt hàng trước hoạt động bằng cách truy cập hoặc in nút hiện tại trước tiên (dòng 4), trước khi gọi đệ quy các nút con trái và phải (dòng 5 và 6).
Hàm preOrderTraversal() tiếp tục duyệt cây con bên trái theo cách đệ quy (dòng 5), trước khi tiếp tục duyệt cây con bên phải (dòng 6). Vì vậy, các nút tiếp theo được in là 'A' và sau đó là 'C'.
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 khi None được trả về lần đầu tiên khi gọi con trái của C, con phải của C cũng trả về None và sau đó các lệnh gọi đệ quy tiếp tục truyền trở lại để con phải D của A là con tiếp theo được in.
Mã tiếp tục truyền trở lại để phần còn lại của các nút trong cây con bên phải của R được in.
