在C#中实现树的功能性遍历

Question

考虑以下C#扩展方法Traverse：

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

这种方法允许我们通过T定义的树和导致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 );

显然，在节点中添加一个Parent属性会使问题变得微不足道。相反，我想以某种方式在函数对象内部构建我的父字符串。我认为在C++中这并不难，但我不知道如何在C#中实现。有任何想法吗？

- Ben Fulton

Answer 1

我认为诀窍在于不要直接传递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);

- JaredPar

---

我刚刚打了完全相同的答案 :) （除了在C#中不需要“With” :)） - Jon Skeet

@Tony，with的问题你发现得不错。每天使用4种语言对于连贯的SO答案来说并不好。 - JaredPar

@Tony，当你切换回Jon时，Twitter风格的评论看起来会非常有趣。 - JaredPar

是的，我“期待着”一系列关于为什么Tony改了他的名字的元问题。 - Jon Skeet

Answer 2

最清晰和可重用的解决方案：

创建一个通用方法，枚举所有可能的路径：

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);

- Dario

Answer 3

我认为如果不存储父节点，你无法避免搜索树直到找到所需节点。

从根节点开始。测试当前节点是否匹配。如果匹配，则返回该节点或仅返回名称（作为此元素列表）。否则，如果这是叶节点，则返回 null。如果不是叶子节点，请遍历其子节点，如果子节点返回非空值，则将当前节点添加到列表开头并返回。

从原始调用返回，null 表示未找到匹配项。否则，您将按顺序拥有节点列表。

- Jason Kleban