Populate a tree from Hierarchical data using 1 LINQ statement

I have set up this programming exercise.

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;}
开发者_Go百科        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"));

        }
    }
}

The desired output is a List of 3 treenodes, having items 1, 2 and 3. Item 2 will have a list of 2 dataobjects as its children member and so on.

I have been trying to populate this tree (or rather a forest) using just 1 statement in LINQ. A simple group by gives me the desired data but the challenge is to organize it in TreeNode objects.

Can someone give a hint or an impossibility result for this?

LINQ does not do particularly well with recursive data structures, but you can get close.

Since you probably want a tree of arbitrary depth, I'll change your definition of Children and add a constructor a helper method that will do the recursion needed to make a tree-building LINQ statement possible.

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

Now we can define the following method:

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

This method makes some assumptions, but should get you in the right direction.

• None of the passed in elements are the root node of the tree and a root node will be created to be the return value.
• The id of the parent node is always lower than the id of the node (this lets OrderBy + Aggregate be called to push the items into the tree)
• Every item in the sequence passed to the method will belong to the root or one of the other items (otherwise an exception will be thrown by the .First() call).

If you want just two level trees, it's rather simple:

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