功能遍歷樹在C＃

考慮在c＃下面擴展方法，遍歷：功能遍歷樹在C＃

IEnumerable<T> Traverse<T>(this IEnumerable<T> source, 
           Func<T, IEnumerable<T>> fnRecurse);

這種方法允許通過一個樹中的一個遞歸被T所定義和任何功能使噸至返回其子節點。

現在考慮下面執行的T：

class Node 
{ 
    public string Name; 
    public List<Node> Children; 
}

我的目標是編寫最短的功能可能會返回一個IEnumerable 包含在這棵樹的每個節點的完全合格的路徑。例如：

var node = GetParentNode(); 
return node.Traverse(node => node.Children) 
      .Select(node => GetParentName(node) + ":" + node.Name);

很顯然，向Node添加Parent屬性會使問題變得微不足道。相反，我想以某種方式在函數內部構建我的父字符串。我不認爲這在C++中會太難，但我不知道如何在C＃中完成它。有任何想法嗎？

來源

2009-11-05 Ben Fulton

我認爲訣竅就是不要傳遞一個Node類型。相反，傳遞Node它是合格的路徑。例如

var node = GetTheStartNode(); 
var start = new { Path = node.Name; Node = node }; 
var paths = 
    start 
    .Traverse(x => x.Node.Children.Select(
     c => new { .Path = x.Path + ":" c.Name; .Node=c)) 
    .Select(x => x.Path);

來源

2009-11-05 17:26:06 JaredPar

我只是在輸入完全相同的答案:)（除非你不需要「用」在C＃:) – 2009-11-05 17:28:37

@Tony，很好的捕捉與。每天以4種語言工作對於連貫的SO回答並不好:) – JaredPar 2009-11-05 17:29:18

@Tony，當你轉回到Jon – JaredPar 2009-11-05 17:29:53

嗯，我不認爲你可以避免搜索樹，直到找到你正在尋找的節點而不存儲父指針。

您將從根開始。測試當前節點是否匹配。如果它是匹配的，則返回節點或名稱（作爲這一個元素的列表）。否則，如果這是一個葉節點，則返回null。如果不是葉，則遍歷它的子節點，如果子節點返回非空值，則將當前節點放在列表中並返回。

從原始調用返回，null表示找不到匹配。否則，您將按順序列出節點列表。

來源

2009-11-05 17:30:18

最清晰，最重用的解決方案：

創建枚舉所有可能的pathes泛型方法：

static IEnumerable<IEnumerable<T>> ComputePaths<T>(T Root, Func<T, IEnumerable<T>> Children) { 
    yield return new[] { Root }; 
    foreach (var Child in Children(Root)) 
     foreach (var ChildPath in ComputePaths(Child, Children)) 
      yield return new[] { Root }.Concat(ChildPath);    
}

產生的枚舉可以很容易地轉換成您的字符串表示。

// All paths 
    var Paths = ComputePaths(Test, x => x.Children); 

    // Compute string representation 
    var StrPaths = from p in Paths select string.Join(":", p.Select(t => t.Name).ToArray()); 

    foreach(var p in StrPaths) 
     Console.WriteLine(p);

來源

2009-11-05 17:40:57 Dario

功能遍歷樹在C＃

回答

相關問題