使用1條LINQ語句從分層數據填充樹

我已經設置了此編程練習。使用1條LINQ語句從分層數據填充樹

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 

namespace ConsoleApplication2 
{ 

    class DataObject { 
     public int ID { get; set; } 
     public int ParentID { get; set; } 
     public string Data { get; set; } 
     public DataObject(int id, int pid, string data) { this.ID = id; this.ParentID = pid; this.Data = data; } 
    } 

    class TreeNode { 
     public DataObject Data {get;set;} 
     public List<DataObject> Children { get; set; } 
    } 


    class Program 
    { 

     static void Main(string[] args) 
     { 
      List<DataObject> data = new List<DataObject>(); 
      data.Add(new DataObject(1, 0, "Item 1")); 
      data.Add(new DataObject(2, 0, "Item 2")); 
      data.Add(new DataObject(21, 2, "Item 2.1")); 
      data.Add(new DataObject(22, 2, "Item 2.2")); 
      data.Add(new DataObject(221, 22, "Item 2.2.1")); 
      data.Add(new DataObject(3, 0, "Item 3")); 

     } 
    } 
}

所需的輸出是3個樹節點列表中，具有項目1，2和3。第2項將具有2個數據對象作爲其子部件等的列表。

我一直試圖在LINQ中只使用1條語句來填充這個樹（或者說一個森林）。一個簡單的分組給了我想要的數據，但挑戰在於將它組織在TreeNode對象中。

有人可以給這個暗示或不可能的結果嗎？

來源

2010-05-03 Midhat

你是說你想要一個2級或任意級別的樹的列表？您定義TreeNode類的方式允許只有兩個級別的樹，即根和直接子級。 – 2010-05-03 19:12:30

是的。我需要任意深度。我認爲我在複製代碼示例時錯過了它 – Midhat 2010-05-04 04:46:39

LINQ不會遞歸數據結構做的特別好，但你可以親近。

因爲你很可能要任意深度的樹，我會改變兒童的定義，並增加一個構造一個輔助方法，將做，使樹建設LINQ聲明可能需要遞歸。

class TreeNode 
{ 
    public DataObject Data { get; set; } 
    public List<TreeNode> Children { get; private set; } 

    public TreeNode(DataObject data) 
    { 
     Data = data; 
     Children = new List<TreeNode>(); 
    } 

    //name chosen to match XElement method. I would name this 
    //SelfAndDescendants or change the behavior to match the name. 
    public IEnumerable<TreeNode> DescendantsAndSelf() 
    { 
     return (new TreeNode[] { this }).Concat(from c in this.Children 
               from sc in c.DescendantsAndSelf() 
               select sc); 
    } 
}

現在，我們可以定義以下方法：

public static TreeNode BuildTree(IEnumerable<DataObject> items, int rootId) 
{ 
    var root = new TreeNode(new DataObject(rootId, int.MinValue, "Root")); 
    return (from i in items 
      let n = new TreeNode(i) 
      group n by n.Data.ParentID into nodeGroup 
      orderby nodeGroup.Key ascending 
      select nodeGroup) 
      .Aggregate(root, (parent, childGroup) => 
      { 
       parent.DescendantsAndSelf() 
         .First(n => n.Data.ID == childGroup.Key) 
         .Children.AddRange(childGroup); 
       return parent; 
      }); 
}

這個方法做了一些假設，但應該讓你在正確的方向。

傳入的元素都不是樹的根節點，而是創建一個根節點作爲返回值。
父節點的ID總是比節點的ID下層（這讓OrderBy + Aggregate被稱爲推項目到樹）
傳遞給方法的序列中的每一項將屬於根或其他項目之一（否則將調用.First()調用拋出異常）。

來源

2010-05-03 23:50:23

如果你想只有兩個級別的樹，這是相當簡單：

var roots = from root in data 
where !data.Any(d => root.ParentID == d.ID) 
select new TreeNode 
{ 
    Data = root, 
    Children = data.Where(d => d.ParentID == root.ID).ToList(), 
}

來源

2010-05-03 19:18:59

使用1條LINQ語句從分層數據填充樹

回答

相關問題