這種類型的枚舉操作是否有可接受的名稱？

我經常發現自己需要遍歷層次結構對象的樹狀結構，並且在每個項目上執行操作。在列表理解方面，這種操作是否有普遍接受的名稱？我問，因爲我記得之前它已經在python的zip function之前知道它在.net框架中具有相同的功能，並且認爲它有一個不尋常的名稱。這種類型的枚舉操作是否有可接受的名稱？

下面是一些通用的方法，它們會上下搜索樹結構並在遇到它們時產生每個項目。

public static IEnumerable<T> Ancestors<T>(T source, Func<T, T> selector) 
{ 
    do 
    { 
     yield return source; 
     source = selector(source); 
    } while (!Equals(source, default(T))); 
} 

public static IEnumerable<T> Descendents<T>(T source, 
              Func<T, IEnumerable<T>> selector) 
{ 
    var stack = new Stack<T>(); 
    stack.Push(source); 
    while (stack.Count > 0) 
    { 
     source = stack.Pop(); 
     yield return source; 
     var items = selector(source); 
     if (items != null) 
     { 
      foreach (var item in items) 
      { 
       stack.Push(item); 
      } 
     } 
    } 
}

來源

2011-06-23 Nathan Baulch

某種過濾的樹遍歷？我不知道這是否有一個特定的名稱。我不認爲它有。 –

第二個是進行深度優先搜索。不確定第二個人是否有名字，因爲儘管根據選擇器功能它被稱爲「祖先」，但它根本不需要實際上遵循「父母」（例如，它可以做任何事情，例如選擇「最好」的孩子node） –

@George：確切地說，「祖先」意味着某種層次關係。實際上，它可以很容易地用於在任一方向上遍歷雙向鏈表或遵循任何類型的任意路徑。 –

這些是標準的Tree Traversal函數，也俗稱「樹行走」。由於具體的步行策略未知，因此很難給出示例的標準化名稱:)

來源

2011-06-23 07:52:24 MattDavey

假設選擇器給出了子節點，則第二種方法是「右先優先深度優先」遍歷。也就是說，如果你有

 A 
    /\ 
    B  C 
/\ /\ 
D E F G

然後你得到A，C，G，F，B，E，D你「B」之前獲得「G」，因爲「深度優先」變爲深，因爲它可以在它嘗試另一個分支之前。在你的例子中，你會在B之前得到C，因爲它優先於左邊。

如果你把它改成

foreach (var item in items.Reverse())

，那麼你會得到一個左一深度優先遍歷，這是大多數人是怎麼想的深度優先遍歷。

如果您將堆棧更改爲隊列，那麼它將成爲「寬度優先」遍歷。 A，B，C，D，E，F，G。你一次完成一個完整的「等級」。

還有其他遍歷。請注意，深度優先搜索和廣度優先搜索都具有父節點出現在子節點之前的屬性。您還可以進行「後序」遍歷，其中每個節點都在其子節點之後。

二叉樹還具有「無序」遍歷。這棵樹的順序遍歷是D，B，E，A，F，C，G。也就是說，每一個左邊的孩子都出現在它的所有祖先之前，每一個正確的孩子都來自它的所有祖先。作爲練習，你可以在二叉樹上編寫一個有序遍歷嗎？

來源

2011-06-23 16:54:23

PseudoCode運動響應：'Function Inorder（Tree）{if（Tree == null）{return;} Inorder（Tree.Left）;輸出（Tree.Value）; Inorder（Tree.Right）;}' – Brian

@Brian：Super。你可以做到沒有遞歸？ –

@Eric，您需要使用普通的堆棧節點和返回地址爲堆棧上的每個節點使用標誌來模擬調用堆棧。當你彈出堆棧時，你檢查標誌是否爲1.「recurse」left或2.（yield）返回當前節點並右鍵單擊「遞歸」。不需要第三個狀態，這基本上是一個尾部呼叫優化。 – svick

這種類型的枚舉操作是否有可接受的名稱？

回答

相關問題