C＃ - 遞歸分組

Question

我有一個IGroup類型的對象列表。這些可以嵌套到一個umlimited級別，我試圖從數據庫中檢索它們後將它們分組。我無法理解如何遞歸地將所有組添加到正確的父母身上。任何以null作爲父項的組都是頂級組。我無法保證它們從數據庫中出來的順序。

public interface IGroup { 
    string ID { get; set; } 
    string Name { get; set; } 
    string ParentID { get; set; } 
    IList<IGroup> Groups { get; set; } 
    ... 

所以，如果我有一個列表：

Group1: ID = g1, ParentID = null 
Group1a: ID = g2, ParentID = g1 
Group2: ID = g3, ParentID = null 
Group1b: ID = g4, ParentID = g3 
Group1bc: ID = g5, ParentID = g4 

我試圖將它們分組爲：

|Group1 
|--Group1a 
|--Group1b 
|--| 
    |--Group1bc 
|Group2 

任何花哨的刺在遞歸將它們分組？

Answer 1

不需要遞歸。即：

var lookup = items.ToDictionary(g => g.ID); // items is IEnumerable<IGroup> 
foreach (var item in items.Where(g => g.ParentID != null)) { 
    lookup[item.ParentID].Groups.Add(item); 
} 
var parents = items.Where(g => g.ParentID == null); 

注意，如果沒有IGroup與相應ParentIDlookup[item.ParentID]將拋出。您可以使用TryGetValue更優雅地處理此問題。

我執行IGroup：

public class Group : IGroup { 
    public string ID { get; set; } 
    public string Name { get; set; } 
    public string ParentID { get; set; } 
    public IList<IGroup> Groups { get; set; } 
    public Group() { 
     Groups = new List<IGroup>(); 
    } 
} 

我的測試項目：

IEnumerable<IGroup> items = new List<IGroup>() { 
    new Group() { ID = "g1", ParentID = null }, 
    new Group() { ID = "g2", ParentID = "g1" }, 
    new Group() { ID = "g3", ParentID = null }, 
    new Group() { ID = "g4", ParentID = "g3" }, 
    new Group() { ID = "g5", ParentID = "g4" }, 
    new Group() { ID = "g6", ParentID = "g5" } 
};  

Answer 2

假設父組始終在子組之前創建，您可以嘗試通過父ID進行排序。

Answer 3

集團由ParentID（Linq：GroupBy），訂購ID。

從一個空的根節點（ID：null）開始，並添加所有具有此ParentID的項目。對於已添加的任何項目，遞歸地繼續此過程。

Answer 4

當你從數據庫中提取的每個元素，你需要將它添加到它的父。所以，保持一個字典，以幫助找到父母。如果你在孩子的父母之前得到一個孩子，那麼你可以插入一個佔位符，直到你得到真實的東西。

void BuildGroups() 
{ 
    foreach(IGroup x /* obtained from database or a collection or wherever */) 
     AddGroup(x); 
} 

Dictionary<string,IGroup> _groups = new Dictionary<string,IGroup>; 
string _parentGroupName = "PARENT"; 
void AddGroup(IGroup x) 
{ 
    // locate (or create) parent and add incoming group 
    IGroup parent; 
    string parentID = x.ParentID ?? _parentGroupName; 
    if(!groups.TryGetValue(parentID, out parent)) 
    { 
     parent = new Group(parentID); // SEE NOTE BELOW! 
     _groups[parentID] = parent; 
    } 
    parent.Groups.Add(x); 

    // locate (or insert) child, and make sure it's up to date 
    IGroup child; 
    if(groups.TryGetValue(x.ID, out child)) 
    { 
     // We must have inserted this ID before, because we found one 
     // of ITS children first. If there are any other values besides 
     // ParentID and ID, then copy them from X to child here. 
    } 
    else 
    { 
     // first time we've seen this child ID -- insert it 
     _groups[x.ID] = x; 
    } 

} 

在_parentGroupName字典元件隨後將是一個虛節點，其孩子們都頂層基團的（即，用NULL作爲PARENTID從數據庫的）;從該元素，你可以做一個遞歸遍歷：

VisitGroups(_groups[_parentGroupName], ""); 

void VisitGroups(string ID, string indent) 
{ 
    IGroup x; 
    if(_groups.TryGetValue(ID, out x)) 
    { 
     foreach(IGroup y in x.Groups) 
     { 
      WriteLine(indent + " {0}", y.ID); 
      VisitGroups(y.ID, indent + " "); 
     }   
    } 
} 

注：此實現在一個單一的在線運行，通過數據 - 你可以立即添加元素，因爲它們可以從數據庫中檢索，而你只需要一次通過數據。這意味着你可以節省一些時間和一些記憶。但是作爲回報，它要求你能夠分配一個類型爲IGroup（）的對象來充當佔位符，以防在其父對象之前檢索到子對象。如果您知道某些關於對象順序的內容，或者如果您以兩遍處理字典，則只能避免該要求，如其他答案中所示。

我使用sentinel值_parentGroupName將頂級節點保留在與其他所有其他集合相同的集合中。如果您願意，您可以輕鬆更改此選項以針對頂級節點使用單獨的集合。

Answer 5

這不是遞歸的，但這裏有一個解決方案（假設你已經在列表中的所有你組，即groups）

var rootGroups = new List<IGroup>(); 
var dic = groups.ToDictionary(g => g.ID); 
foreach (var g in groups) 
{ 
    if (g.ParentID == null) 
    { 
     rootGroups.Add(g); 
    } 
    else 
    { 
     IGroup parent; 
     if (dic.TryGetValue(g.ParentID, out parent)) 
     { 
       parent.Groups.Add(g); 
     } 
    } 
} 

Answer 6

你可以試試這個

public interface IGroup 
{ 
    string ID { get; set; } 
    string Name { get; set; } 
    string ParentID { get; set; } 
    List<IGroup> Groups { get; set; } 
} 
public class Group : IGroup 
{ 
    public string ID { get; set; } 
    public string Name { get; set; } 
    public string ParentID { get; set; } 
    public List<IGroup> Groups { get; set; } 
    public Group() 
    { 

    } 
    public Group(string id, string name, List<IGroup> childs) 
    { 
     ID = id; 
     Name = name; 
     Groups = (List<IGroup>)childs.Cast<IGroup>(); 
    } 

} 


class Program 
{ 
    static void Main(string[] args) 
    { 
     List<IGroup> OriginalList; 
     List<IGroup> HirarchList = new List<IGroup>(); 

     OriginalList = new List<IGroup>() 
     { 
      new Group() { ID = "g1", ParentID = null }, 
      new Group() { ID = "g2", ParentID = "g1" }, 
      new Group() { ID = "g3", ParentID = null }, 
      new Group() { ID = "g4", ParentID = "g3" }, 
      new Group() { ID = "g5", ParentID = "g4" }, 
      new Group() { ID = "g6", ParentID = "g5" } }; 

     HirarchList = GetCreateList(null, OriginalList); 
    } 
    public static List<IGroup> GetCreateList(string id, List<IGroup> list) 
    { 
     List<IGroup> temp = new List<IGroup>(); 
     temp = (from item in list 
       where item.ParentID == id 
       select (IGroup)new Group(item.ID, item.Name,GetCreateList(item.ID, list))).ToList(); 

     return (List<IGroup>)temp; 
    } 

}