cây lặp đi

Question

Đã khá lâu kể từ khi tôi mất cấu trúc dữ liệu và thuật toán ở trường đại học, vì vậy tôi đã rất ngạc nhiên thời gian gần đây bởi một gợi ý rằng đệ quy có thể không cách (tm) để làm cây traversal. Đối với một số lý do lặp đi lặp lại, hàng đợi dựa trên traversal đã không được một kỹ thuật mà tôi đã từng sử dụng.

Điều gì, nếu có, là những lợi thế của chuyển đổi lặp lại so với đệ quy? Trong những tình huống nào tôi có thể sử dụng nó thay vì cái khác?

Answer 1

Nếu bạn đang thực hiện tìm kiếm đầu tiên, việc thực hiện tự nhiên là đẩy các nút vào hàng đợi, không sử dụng đệ quy.

Nếu bạn đang thực hiện tìm kiếm chiều sâu đầu tiên thì đệ quy là cách tự nhiên nhất để mã truyền tải. Tuy nhiên, trừ khi trình biên dịch của bạn tối ưu hóa đệ quy đuôi vào lặp lại, triển khai đệ quy của bạn sẽ chậm hơn so với một thuật toán lặp lại, và sẽ chết với một tràn ngăn xếp trên một cây đủ sâu.

Một số Python nhanh chóng để minh họa sự khác biệt:

#A tree is a tuple of an int and a tree. 
t = (1, (2,(4, (6), (7, (9)))), (3, (5, (8)))) 
def bfs(t): 
    to_visit = [t] 
    while len(to_visit) > 0: 
     c = to_visit[0] 
     if type(c) is int: 
      print c 
     else: 
      print c[0] 
      to_visit.append(c[1]) 
      if len(c) > 2: to_visit.append(c[2]) 
     to_visit = to_visit[1:] 

def dfs(t): 
    if type(t) is int: 
     print t 
     return 
    print t[0] 
    dfs(t[1]) 
    if len(t) > 2: dfs(t[2]) 

bfs(t) 
dfs(t) 

Answer 2

Nó phụ thuộc vào việc bạn muốn làm Depth-First hoặc traversal Breadth-First. Độ sâu đầu tiên là dễ thực hiện nhất thông qua đệ quy. Với Breadth-đầu tiên bạn cần phải giữ một hàng đợi các nút để mở rộng trong tương lai.

Answer 3

Nếu bạn có một lượng bộ nhớ cố định dành riêng cho ngăn xếp, như bạn thường làm (điều này đặc biệt là một vấn đề trong nhiều cấu hình Java JVM), đệ quy có thể không hoạt động tốt nếu bạn có cây sâu (hoặc nếu chiều sâu đệ quy cao trong bất kỳ kịch bản nào khác); nó sẽ gây ra tràn ngăn xếp. Một cách tiếp cận lặp đi lặp lại, đẩy các nút truy cập vào một hàng đợi (đối với BFS giống như traversal) hoặc ngăn xếp (cho DFS giống như traversal) có tính chất bộ nhớ tốt hơn theo nhiều cách, vì vậy nếu điều này quan trọng, sử dụng một cách tiếp cận lặp đi lặp lại.

Ưu điểm của đệ quy là sự đơn giản/thanh lịch của biểu thức, không phải hiệu suất. Nhớ rằng đó là chìa khóa để lựa chọn phương pháp thích hợp cho một thuật toán, kích thước bài toán và kiến ​​trúc máy đã cho.

Answer 4

Thực ra bạn nên sử dụng hàng đợi cho tìm kiếm đầu tiên và ngăn xếp để tìm kiếm chiều sâu đầu tiên, và chạy thuật toán của bạn từ một vòng lặp while. Thực hiện các cuộc gọi hàm đệ quy có thể kéo chương trình của bạn một cách đáng kể nếu bạn thực hiện thao tác đơn giản trong khi di chuyển ngang và có thể gây tràn ngăn xếp, nhưng những ngày này bạn sẽ cần thực hiện khó khăn để xem chương trình.

Chỉ cần có một băm ở bên cạnh để theo dõi các nút đã truy cập trong trường hợp nó không phải là một cái cây mà là một biểu đồ được kết nối tốt.

Answer 5

Đi với đệ quy, bởi vì bạn thực sự có thể gặp phải lỗi tràn ngăn xếp và sau đó tất cả là stackoverflow.com.