当每个项目包含对其父项的引用时,从项列表中创建树

Question

我有一个类型的对象列表Foo.每个Foo对象都包含对其父对象的引用:

public class Foo
{
    public Foo Parent { get; set; }
}

(如果Parent为null,则Foo认为它是'根'节点.)正如您所看到的,这意味着一种"自下而上"的树层次结构.

我想通过将我的Foo对象包装在一个名为的新类中来颠倒这个child-> parent关联TreeItem.

public class TreeItem<T>
{
    public T Item { get; set; }
    public IEnumerable<TreeItem<T>> Children { get; set; }
}

如图所示,这将给我一个更自然的"自上而下"树层次结构.我相信这将允许更容易的数据绑定,例如.在WPF中TreeView.

是否有一个简洁的Linq语句,它能够获取a List<Foo>,找到每个Foo对象的子节点,并吐出相应转换后的列表TreeItem<Foo>？

除了Linq查询,最简单的算法是什么？

额外奖励:您将使用哪些词语或搜索词来描述这种"树翻转"转换？

Answer 1

ToLookup可以简单地为每个项目创建所有孩子的查找.一旦你有了,你就可以将每个项目映射到新对象,并有一个简单的机制来获取每个项目的所有子项.

IEnumerable<Foo> data = GetData();
var lookup = data.ToLookup(foo => foo.Parent);
Func<Foo, TreeItem<object>> selector = null;
selector = foo => new TreeItem<object>()
{
    Item = foo,
    Children = lookup[foo].Select(selector),
};
var rootNodes = lookup[null].Select(selector);

或者,如果您宁愿避免递归,则可以在构建查找时转换每个项目而不映射子项,然后改变每个项目以包含子项:

IEnumerable<Foo> data = GetData();
var lookup = data.ToLookup(foo => foo.Parent,
    foo => new TreeItem<object>() { Item = foo });
foreach (var node in lookup.SelectMany(x => x))
    node.Children = lookup[node.Item];
var rootNodes = lookup[null];

如果存在大量数据,则缺少递归可能很重要,并且它还允许它处理任意图形,而不仅仅是树.(特别是它可以处理循环.)