迭代樹走

Question

它已經相當一段時間，因爲我把數據結構和算法在大學，所以我很驚訝最近一項建議是遞歸可能不是方式（TM）做樹的遍歷。出於某種原因迭代，基於隊列的遍歷不是我曾經使用過的技術。

什麼，如果有的話，是迭代與遞歸遍歷的優點？在什麼情況下我可以使用一種而不使用另一種？

Answer 1

如果您在進行寬度優先搜索，自然實現是將節點推入隊列，而不是使用遞歸。

如果您正在進行深度優先搜索，則遞歸是編碼遍歷的最自然的方式。但是，除非您的編譯器將迭代的尾部遞歸優化，否則您的遞歸實現將比迭代算法慢，並且會在足夠深的樹上發生堆棧溢出而死亡。

一些快速的Python來說明的區別：

#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

這取決於你是否想要做的是深度優先還是廣度優先遍歷。深度優先是通過遞歸最容易實現的。通過寬度優先，您需要保留一個節點隊列以便將來擴展。

Answer 3

如果您擁有固定數量的專用於堆棧的內存（與許多Java JVM配置中的問題相同），但如果您的樹較深（或者遞歸深度不足，遞歸可能無法正常工作在任何其他情況下都很高）;它會導致堆棧溢出。迭代方法，推動節點訪問隊列（用於類似BFS的遍歷）或堆棧（用於類似DFS的遍歷）具有更好的內存屬性，因此如果這很重要，請使用迭代方法。

遞歸的優點是簡單/高雅的表達，而不是表現。記住這是爲給定算法，問題大小和機器體系結構選擇適當方法的關鍵。

Answer 4

實際上，你應該使用隊列中的廣度優先搜索和堆棧進行深度優先搜索， 並從while循環運行你的算法。 如果在遍歷期間執行簡單的 操作，並且可能導致堆棧溢出，則進行遞歸函數調用會顯着拖動程序，但這些日子您需要嘗試真正難以看到其中的一個。

只要有一個哈希值來跟蹤已訪問的節點，以防它不是一棵樹，而是一個連接良好的圖。

Answer 5

去遞歸，因爲你實際上可能會得到一個堆棧溢出錯誤，畢竟這是stackoverflow.com。