请教一个生成树的算法，即根据当前数据列表的特性生成树结构。

Question

本帖最后由 wtoeb 于 2013-01-27 05:19:27 编辑

Answer 1

with tb(ID,Name,Start,[End],ParentID,Level)
as(
select 1,'test1',600,        1000,0,0 union all
select 2,'test2',640,        720,0,0 union all
select 3,'test3',660,        680,0,0 union all
select 4,'test4',665,        670,0,0 union all
select 5,'test5',675,        678,0,0 union all
select 6,'test6',730,        900,0,0 union all
select 7,'test7',910,        950,0,0 union all
select 8,'test8',960,        1000,0,0 union all
select 9,'test9',1100,       1200,0,0 union all
select 10,'test10',1120,     1180,0,0),
cte as(
select id,name,start,[End],parentid=0,level=1,sumid=cast(rtrim(id) as varchar(1000)) from tb tb1 where not exists(select * from tb tb2 where tb2.id<tb1.id and tb1.Start between tb2.Start and tb2.[end] and tb1.[end] between tb2.Start and tb2.[end]) union all
select tb1.id,tb1.name,tb1.start,tb1.[end],c.id,c.level+1,cast(sumid+','+rtrim(tb1.id) as varchar(1000)) from tb tb1,cte c where tb1.id>c.id and charindex(','+rtrim(tb1.id)+',',','+sumid+',')<1 and tb1.start between c.start and c.[end] and tb1.[end] between c.start and c.[end]
)
select ID,Name,Start,[End],ParentID,Level from (select row= row_number()over(partition by id order by len(sumid) desc),* from cte)t  where row=1

Answer 2

void Format(IEnumerable<Data> array, int Start, int End, int Index)
{
    var 子集合 = (from x in array
                where x.Start >= Start && x.End <= End
                select x).ToList();
    var 最高级别集合 = (from x in 子集合
                    where !子集合.Any(y => y != x && y.Start <= x.Start && y.End >= x.End)
                    select x).ToList();
    foreach (var x in 最高级别集合)
    {
        x.Level = Index;
        Format(子集合.Except(最高级别集合), x.Start, x.End, Index + 1);
    }
}调用 Format(data, 1, 1500, 1) 得到 1 2 3 4 4 2 2 2 1 2

Answer 3

嗯，稍微修改一点点：void Format(IEnumerable<Data> array, int Start, int End, int Index)
{
    var 子集合 = (from x in array
                where x.Start >= Start && x.End <= End
                select x).ToList();
    var 最高级别集合 = (from x in 子集合
                    where !子集合.Any(y => y != x && y.Start <= x.Start && y.End >= x.End)
                    select x).ToList();
    var 余集 = 子集合.Except(最高级别集合).ToList();
    foreach (var x in 最高级别集合)
    {
        x.Level = Index;
        Format(余集, x.Start, x.End, Index + 1);
    }
}

Answer 4

上面没有改写 ParentID，再重构一下程序：static void Format(IEnumerable<Data> array, int Start, int End, int Index, Data Parent = null)
{
    var 子集合 = (from x in array
                where x.Start >= Start && x.End <= End
                select x).ToList();
    var 最高级别集合 = (from x in 子集合
                    where !子集合.Any(y => y != x && y.Start <= x.Start && y.End >= x.End)
                    select x).ToList();
    var 余集 = 子集合.Except(最高级别集合).ToList();
    foreach (var x in 最高级别集合)
    {
        x.Level = Index;
        if (Parent != null)
            x.ParentID = Parent.ID;
        Format(余集, x.Start, x.End, Index + 1, x);
    }
}