将平面集合转换为层次集合的递归方法

Question

我已经被这个问题困了几天了，希望你能给我一些建议或帮助我解决这个问题。我有一个对象集合

 public class Hierarchy
{
    public Hierarchy(string iD, string name, int level, string parentID, string topParent)
    {
        ID = iD;
        Name = name;
        Level = level;
        ParentID = parentID;
        Children = new HashSet<Hierarchy>();
    }
    public string ID { get; set; }
    public string Name{ get; set; }
    public int Level { get; set; }
    public string ParentID { get; set; }
    public ICollection<Hierarchy> Children { get; set; }
}

从Linq查询到我的实体的数据是:

ID      Name     Level ParentID
295152  name1    1     null
12345   child1   2     295152
54321   child2   2     295152
44444   child1a  3     12345
33333   child1b  3     12345
22222   child2a  3     54321
22221   child2b  3     54321
22002   child2c  3     54321
20001   child2a2 4     22222
20101   child2b2 4     22222

这个数据可以扩展到未知的层次深度(我只显示了4)。最终，我将有一个层次结构对象与多个子对象的集合，反过来可能有多个子对象的集合…等等…永远只有一个顶层对象。

我正在尝试在这个项目中尽可能多地使用Linq。

这显然需要某种递归方法，但我卡住了。如有任何建议或帮助，我将不胜感激。

TIA

Answer 1

你可以试试这个递归函数:

void PopulateChildren(Hierarchy root, ICollection<Hierarchy> source)
{
    foreach (var hierarchy in source.Where(h => h.ParentID == root.ParentID))
    {
        root.Children.Add(hierarchy);
        PopulateChildren(root, source);
    }
}

可以这样使用:

ICollection<Hierarchy> hierarchies = new List<Hierarchy>(); // source
// Get root
var root = hierarchies.Single(h => h.Level == 1);
// Populate children recursively
PopulateChildren(root, hierarchies);

Answer 2

实际上，迭代解决方案可能要简单得多。步骤如下:

1. 基于id将所有节点散列到字典中
2. 第二次循环，并将每个节点添加到其父节点的子列表

它看起来像这样:

Hierarchy CreateTree(IEnumerable<Hierarchy> Nodes)
{
    var idToNode = Nodes.ToDictionary(n => n.ID, n => n);
    Hierarchy root;
    foreach (var n in Nodes)
    {
        if (n.ID == null)
        {
            if (root != null)
            {
                //there are multiple roots in the data
            }
            root = n;
            continue;
        }
        Hierarchy parent;
        if (!idToNode.TryGetValue(n.ID, parent))
        {
            //Parent doesn't exist, orphaned entry
        }
        parent.Children.Add(n);
    }
    if (root == null)
    {
        //There was no root element
    }
    return root;
}

数据格式有几个明显可能的错误条件。你怎么处置他们就看你了。

一般来说，总是有一个迭代解和一个递归解。具体的问题会改变哪一个更容易。