Заполнение дерева из Иерархических данных с использованием инструкции 1 LINQ

Question

Я настроил это упражнение по программированию.

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 treenodes, имеющих пункты 1, 2 и 3. Пункт 2 будет иметь список 2 DataObjects как его член детей и так далее.

Я пытаюсь заполнить это дерево (или, скорее, лес), используя только 1 инструкцию в LINQ. Простая группа дает мне нужные данные, но задача состоит в том, чтобы организовать ее в объектах TreeNode.

Может кто-нибудь дать подсказку или результат невозможности для этого?

Answer 1

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

Этот метод делает некоторые предположения, но должны получить вас в правильном направлении.

• Ни один из переданных элементов не является корневым узлом дерева, а корневой узел будет создан как возвращаемое значение.
• Идентификатор родительского узла всегда ниже, чем идентификатор узла (это позволяет OrderBy + Aggregate можно назвать, чтобы раздвинуть элементы в дереве)
• Каждый элемент в последовательности передается методу будет принадлежать root или один из других элементов (иначе исключение будет вызвано вызовом .First()).

Answer 2

Если вы хотите только два дерева уровня, это довольно просто:

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(), 
}