從父/子的平面列表構建層次結構對象

Question

我有一個層次結構中的項目列表，我試圖將此列表解析爲實際的對象層次結構。我使用modified pre-order tree traversal來存儲/遍歷這個列表，所以我所擁有的是樹的一個子集，包括所有的孩子，都按他們的「左」值排序。

例如，給定的樹：

• 項A
  • 項目A.1
  • 項目A.2
    • 項目A.2.2
• B項
  • 項目B.1
• C項

我得到的名單：

• 項目A，項目A.1，A.2項，項目A.2.2，項目B，項目B.1，項目C

（這是爲了來自修改的預訂樹設置的「左」值）。

我想要做的是分析到包含樹的實際結構對象，例如這樣的：

Class TreeObject { 
    String Name; 
    Guid ID; 
    Guid ParentID; 
    List<TreeObject> Children; 
} 

平列表返回TreeObjects的列表 - 每個的TreeObject具有屬性ID ，ParentID，Left和Right。我正在尋找的是一個功能：

List<TreeObject> FlatToHeirarchy(List<TreeObject> list); 

它將扁平列表放入並返回一個嵌套列表。

換句話說：

List<TreeObject> flatSet = LoadTreeObjectsFromDatabase(); 
// flatSet.count == 7; flatSet(0).Children == null 
List<TreeObject> nestedSet = FlatToHeirarchy(flatSet); 
// nestedSet.count == 3; nestedSet(0).Children.count == 2 

我不知如何做到這一點 - 跟蹤的父母，並能夠處理更大的跳躍（例如，項目A.2.2 - >項目B）。

---

編輯：我在尋找一個非強力解決方案在這裏（例如，不循環幾次，移動項目到子節點，直到只有頂級的父母左）。我猜測有一個優雅的方法可以循環一次，並根據需要放置物品。

請記住，它們始終處於分層次序（因爲我使用的是MPTT），所以給定的項目將始終是上一個項目的子項或同級項目，或者至少與之前的項目共享父項。它永遠不會到達樹中的其他地方。

Answer 1

這是我最後寫的功能。我使用MPTT來存儲對象，所以列表按照'左'值的順序排列，這基本上意味着父對象始終位於列表中的任何給定項之前。換句話說，item.ParentID引用的項目一直是已經添加的（除了頂級或根節點的情況）。

public class TreeObject 
{ 
    public int Id { get; set; } 
    public int ParentId { get; set; } 
    public string Name { get; set; } 
    public IList<TreeObject> Children { get; set; } = new List<TreeObject>(); 
} 

public IEnumerable<TreeObject> FlatToHierarchy(List<TreeObject> list) 
{ 
    // hashtable lookup that allows us to grab references to containers based on id 
    var lookup = new Dictionary<int, TreeObject>(); 
    // actual nested collection to return 
    var nested = new List<TreeObject>(); 

    foreach (TreeObject item in list) 
    { 
     if (lookup.ContainsKey(item.ParentId)) 
     { 
      // add to the parent's child list 
      lookup[item.ParentId].Children.Add(item); 
     } 
     else 
     { 
      // no parent added yet (or this is the first time) 
      nested.Add(item); 
     } 
     lookup.Add(item.Id, item); 
    } 

    return nested; 
} 

和一個簡單的測試（即在LinqPad工作）：

void Main() 
{ 
    var list = new List<TreeObject>() { 
     new TreeObject() { Id = 1, ParentId = 0, Name = "A" }, 
     new TreeObject() { Id = 2, ParentId = 1, Name = "A.1" }, 
     new TreeObject() { Id = 3, ParentId = 1, Name = "A.2" }, 
     new TreeObject() { Id = 4, ParentId = 3, Name = "A.2.i" }, 
     new TreeObject() { Id = 5, ParentId = 3, Name = "A.2.ii" } 
    }; 

    FlatToHierarchy(list).Dump(); 
} 

結果：

因爲我更新這5年過去了，這裏有一個遞歸LINQ版本：

public IList<TreeObject> FlatToHierarchy(IEnumerable<TreeObject> list, int parentId = 0) { 
    return (from i in list 
      where i.ParentId == parentId 
      select new TreeObject { 
       Id = i.Id, 
       ParentId = i.ParentId, 
       Name = i.Name, 
       Children = FlatToHierarchy(list, i.Id) 
      }).ToList(); 
} 

Answer 2

我假設你已經知道所有項目的父項。

所有你需要做的是在列表中的所有項目一次迭代和當前項目添加到其父的孩子名單。僅將沒有父項的項目保留在目標嵌套列表中。

下面是一些僞代碼：

foreach Item item in flatlist 
    if item.Parent != null 
     Add item to item.Parent.ChildrenList 
     Remove item from flatlist 
    end if 
end for 

至於讓父母，從我可以在你的例子中看到，您可能需要解析的名字，當你在列表中推進建立一個堆棧。

這個問題看起來辛苦，但它真的不是。很多人從錯誤的角度看待這個問題;你不能試圖填充每個兒童列表，而是從平面列表中刪除兒童項目，然後它變得容易。

Answer 3

下面是一個例子，希望這有助於

class Program 
{ 
    static void Main(string[] args) 
    { 
     TreeObject a = new TreeObject() { Name = "Item A" }; 
     a.Children.Add(new TreeObject() { Name = "Item A.1" }); 
     a.Children.Add(new TreeObject() { Name = "Item A.2" }); 

     TreeObject b = new TreeObject() { Name = "Item B" }; 
     b.Children.Add(new TreeObject() { Name = "Item B.1" }); 
     b.Children.Add(new TreeObject() { Name = "Item B.2" }); 

     TreeObject c = new TreeObject() { Name = "Item C" }; 

     List<TreeObject> nodes = new List<TreeObject>(new[] { a, b, c }); 

     string list = BuildList(nodes); 
     Console.WriteLine(list); // Item A,Item A.1,Item A.2,Item B,Item B.1,Item B.2,Item C 

     List<TreeObject> newlist = new List<TreeObject>(); 
     TreeObject temp = null; 

     foreach (string s in list.Split(',')) 
     { 
      if (temp == null || !s.Contains(temp.Name) || temp.Name.Length != s.Length) 
      { 
       temp = new TreeObject() { Name = s }; 
       newlist.Add(temp); 
      } 
      else 
      { 
       temp.Children.Add(new TreeObject() { Name = s }); 
      }        
     } 

     Console.WriteLine(BuildList(newlist)); // Item A,Item A.1,Item A.2,Item B,Item B.1,Item B.2,Item C 
    } 

    static string BuildList(List<TreeObject> nodes) 
    { 
     StringBuilder output = new StringBuilder(); 
     BuildList(output, nodes); 
     return output.Remove(output.Length - 1, 1).ToString(); 
    } 

    static void BuildList(StringBuilder output, List<TreeObject> nodes) 
    { 
     foreach (var node in nodes) 
     { 
      output.AppendFormat("{0},", node.Name); 
      BuildList(output, node.Children); 
     } 
    } 
} 

public class TreeObject 
{ 
    private List<TreeObject> _children = new List<TreeObject>(); 

    public string Name { get; set; } 
    public Guid Id { get; set; } 
    public List<TreeObject> Children { get { return _children; } } 
} 

}

Answer 4

通常編譯的替代版本，我不確定上面的代碼是否有問題。

private List<Page> FlatToHierarchy(List<Page> list) { 
     // hashtable lookup that allows us to grab references to the parent containers, based on id 
     Dictionary<int, Page> lookup = new Dictionary<int, Page>(); 
     // actual nested collection to return 
     List<Page> nested = new List<Page>(); 

     foreach(Page item in list) { 
     if (lookup.ContainsKey(item.parentId)) { 
      // add to the parent's child list 
      lookup[item.parentId].children.Add(item); //add item to parent's childs list 
      lookup.Add(item.pageId, item); //add reference to page in lookup table 
     } else { 
      // no parent added yet (or this is the first time) 
      nested.Add(item);  //add item directly to nested list     
      lookup.Add(item.pageId, item); //add reference to page in lookup table 
     } 
     } 
    return nested; 
    } 

Answer 5

修正由gregmac

IList<TreeObject> FlatToHierarchy(IQueryable<lcc_classe> list, int? parentId) 
    { 
     var q = (from i in list 
       where i.parent_id == parentId 
       select new 
       { 
        id = i.id, 
        parent_id = i.parent_id, 
        kks = i.kks, 
        nome = i.nome 
       }).ToList(); 
     return q.Select(x => new TreeObject 
      { 
       children = FlatToHierarchy(list, x.id) 
      }).ToList(); 
    }