將平面集合轉換爲分層集合的遞歸方法？

我一直在這個問題上停留了幾天，並希望得到一些想法或幫助解決它。我從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

我真的很喜歡你的迴應和說明。我希望我能做出兩個答案。 –

將平面集合轉換爲分層集合的遞歸方法？

回答

相關問題