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

我一直在这个问题上停留了几天，并希望得到一些想法或帮助解决它。我从LINQ查询对象将平面集合转换为分层集合的递归方法？

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

的数据的集合，以我的实体是：

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）。最终，我将有一个Hierarchy对象，它具有多个子对象的集合，而这些对象又可能具有多个子对象的集合...等等。总是只有一个顶级对象。

我想尽可能在这个项目中使用Linq。

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

TIA

来源

2013-01-11 John S

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

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

来源

2013-01-11 07:38:19

有一个需要做这个工作的轻微mod。在PopulateChildren层次的内部调用中需要传递，因为它是这个级别的“根”。那么这一切都很好。 –

这说明了递归和迭代之间对于一些问题的权衡：这个递归解决方案是O（n^2），而迭代解决方案是O（n）。 –

其实，迭代解决方案可能要容易得多。以下是具体步骤：

哈希全部基于其ID
循环通过第二时间节点到字典中，每个节点添加到它的父节点的子列表

，它看起来像这样：

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

有一些明显的数据格式可能的错误条件。它取决于你对他们做什么。

总的来说，总是有一个迭代解决方案和一个递归解决方案。特定的问题会改变哪一个更容易。

来源

2013-01-11 04:52:25

我真的很喜欢你的回应和说明。我希望我能做出两个答案。 –

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

回答

相关问题