在C＃中以函数方式遍历树

在c＃，Traverse中考虑以下扩展方法：

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

此方法允许通过T定义的树递归，并且任何函数都会导致T返回其子节点。

现在考虑以下T的实现：

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

我的目标是编写可能的最短函数，它将返回包含此树中每个节点的完全限定路径的IEnumerable。 就像是：

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

显然，向Node添加Parent属性会使问题变得微不足道。 相反，我想以某种方式在仿函数中构建我的父字符串。 我不认为这在C ++中会太难，但我不知道如何在C＃中做到这一点。 有任何想法吗？

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

Answer 2

最清晰，最可重复使用的解决方案：

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

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

生成的枚举可以很容易地转换为您的字符串表示forms。

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

Answer 3

好吧，我不认为你可以避免搜索树，直到你找到你正在寻找的节点而不存储父指针。

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

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