ToHierarchy.cs

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

namespace ConsoleApplication1
{
    public abstract class HierarchyNode
    {
        public string ID { get; set; }
        public string Path { get; set; }
        public string Name { get; set; }
        public int Depth { get; set; }
    }

    public sealed class HierarchyParent : HierarchyNode
    {
        public IEnumerable<HierarchyNode> Children { get; set; }
    }

    public sealed class HierarchyLeaf<T> : HierarchyNode
    {
        public T Value { get; set; }
    }

    public static class HierarchyExtensions
    {
        class HierarchyItem<T>
        {
            public string[] Segments { get; set; }
            public T Item { get; set; }
        }

        static IEnumerable<HierarchyNode> Parents<T>(this IEnumerable<HierarchyItem<T>> items, int depth)
        {
            var parents = from item in items
                          where depth < item.Segments.Length - 1
                          group item by item.Segments[depth] into g
                          orderby g.Key
                          select (HierarchyNode)new HierarchyParent
                          {
                              ID = g.First().Segments.Take(depth+1).Join(Path.DirectorySeparatorChar),
                              Path = g.First().Segments.Take(depth).Join(Path.DirectorySeparatorChar),
                              Name = g.Key,
                              Depth = depth,
                              Children = g.Parents(depth + 1).Concat(g.Leaves(depth + 1))
                          };

            return parents;
        }

        static IEnumerable<HierarchyNode> Leaves<T>(this IEnumerable<HierarchyItem<T>> items, int depth)
        {
            var leaves = from item in items
                         where depth == item.Segments.Length - 1
                         orderby item.Segments[depth]
                         select (HierarchyNode)new HierarchyLeaf<T>
                         {
                             ID = item.Segments.Join(Path.DirectorySeparatorChar),
                             Path = item.Segments.Take(depth).Join(Path.DirectorySeparatorChar),
                             Name = item.Segments[depth],
                             Depth = depth,
                             Value = item.Item
                         };

            return leaves;
        }

        static string Join(this IEnumerable<string> seq, char separator)
        {
            var builder = new StringBuilder(seq.FirstOrDefault());

            foreach (var s in seq.Skip(1))
            {
                builder.Append(separator);
                builder.Append(s);
            }

            return builder.ToString();
        }

        public static IEnumerable<HierarchyNode> ToHierarchy<T>(this IEnumerable<T> seq, Func<T, string> pathSelector)
        {
            return seq.ToHierarchy(pathSelector, true);
        }

        public static IEnumerable<HierarchyNode> ToHierarchy<T>(this IEnumerable<T> seq, Func<T, string> pathSelector, bool lazy)
        {
            var items = from item in seq
                        select new HierarchyItem<T>
                        {
                            Segments = pathSelector(item).Split(Path.DirectorySeparatorChar, Path.AltDirectorySeparatorChar),
                            Item = item
                        };

            var root = items.Parents(0).Concat(items.Leaves(0));

            if (!lazy)
            {
                root = root.ToList();
                foreach (var parent in root.Traverse().OfType<HierarchyParent>())
                {
                    parent.Children = parent.Children.ToList();
                }
            }

            return root;
        }

        public static IEnumerable<HierarchyNode> Traverse(this IEnumerable<HierarchyNode> hierarchy)
        {
            foreach (var item in hierarchy.OrderBy(item => item.Name))
            {
                yield return item;

                if (item is HierarchyParent)
                    foreach (var child in ((HierarchyParent)item).Children.Traverse())
                        yield return child;
            }
        }

        public static void Visit(this IEnumerable<HierarchyNode> hierarchy, Action<HierarchyNode> action)
        {
            foreach (var item in hierarchy.Traverse())
                action(item);
        }
    }

    class TestItem
    {
        public string Path { get; set; }
        public int Value { get; set; }
    }

    class Program
    {
        static void Main(string[] args)
        {
            var items = new List<TestItem>
            {
                new TestItem { Path = @"Test\Some\Folder\5", Value = 5 },
                new TestItem { Path = @"Test\Some\Folder\1", Value = 1 },
                new TestItem { Path = @"Test\Some\Folder\3", Value = 3 },
                new TestItem { Path = @"One", Value = 1 },
                new TestItem { Path = @"Test\Some\Folder\6", Value = 6 },
                new TestItem { Path = @"Test\Some\Folder\6", Value = 6 },
                new TestItem { Path = @"Another\Test\Three", Value = 3 },
                new TestItem { Path = @"A\Really\Long\Path\Test\To\See\How\Deep\This\Goes\7", Value = 6 },
                new TestItem { Path = @"Test\Some\Folder\4", Value = 4 },
                new TestItem { Path = @"Test\Some\Folder\2", Value = 2 },
                new TestItem { Path = @"A\Really\Long\Path\Test\To\See\How\Deep\This\Goes\8", Value = 7 },
                new TestItem { Path = @"Another\Test\Four", Value = 4 },
                new TestItem { Path = @"Foo\Bar", Value = 15 },
                new TestItem { Path = @"Test\Foo\Bar", Value = 15 },
            };

            //var hierarchy = Directory.GetFiles(@"C:\Windows\Microsoft.NET", "*.dll", SearchOption.AllDirectories).ToHierarchy(path => path);
            var hierarchy = items.ToHierarchy(i => i.Path, false);

            foreach (var item in hierarchy.Traverse())
            {
                Console.WriteLine("{0}: {1} - {2}", item.Depth, item.Name, item.Path);
            }
        }
    }
}