首页 > 代码库 > 06. 父子节点(树)遍历写法小结

06. 父子节点(树)遍历写法小结

原文:06. 父子节点(树)遍历写法小结

对于树/图的遍历,通常有2种算法来实现:迭代(Iteration)和递归(Recursion),迭代是利用循环反复取值/赋值的过程;递归则是反复自己调用自己来获得最终结果。
SQL Server里的递归有32层嵌套限制,目的在于防止代码进入死循环,除非使用提示OPTION (MAXRECURSION 0)。

测试数据:

if OBJECT_ID(city) is not null    drop table cityGOcreate table city(id    int,name  nvarchar(10),pid   int,depth int)GOinsert into city select  1,N江苏省,0,0 union allselect  2,N南京市,1,1 union allselect  3,N玄武区,2,2 union allselect  4,N鼓楼区,2,2 union allselect  5,N浙江省,0,0 union allselect  6,N杭州市,5,1 union allselect  7,N西湖区,6,2 union allselect  8,N滨江区,6,2 union allselect  9,N苏州市,1,1 union allselect 10,N吴中区,9,2 union allselect 11,N吴江区,9,2

一. 查找子节点
查找节点1的所有子节点,返回结果如下:

idnamepiddepth
1江苏省00
2南京市11
3玄武区22
4鼓楼区22
9苏州市11
10吴中区92
11吴江区92

1. 迭代
(1) 不借助depth,通过not in来向下查找

if OBJECT_ID(f_get_child) is not null    drop function f_get_childGOcreate function f_get_child(@id int)returns @t table(id int)asbegin    insert into @t select @id    --insert into @t select id from city where pid = @id    while @@ROWCOUNT>0    begin        insert into @t         select a.id         from city a inner join @t b on a.pid = b.id        where a.id not in(select id from @t)    end    returnendGOselect * from city where id in(select id from f_get_child(1))

(2) 通过depth来逐层查找

if OBJECT_ID(f_get_child) is not null    drop function f_get_childGOcreate function f_get_child(@id int)returns @t table(id int, depth int)begin    declare @depth int    set @depth = 0    insert @t select ID,@depth from city where ID =@ID    while @@ROWCOUNT>0    begin        set @depth = @depth + 1        insert @t select a.ID,@depth          from city a, @t b         where a.pid = b.ID           and b.depth = @depth - 1    end        return      endGOselect * from city where id in(select id from f_get_child(1))

2. 递归
(1) 自定义函数递归

if OBJECT_ID(f_get_child) is not null    drop function f_get_childGOcreate function f_get_child(@id int)returns @t table(id int)asbegin    declare @pid int    set @pid = null    insert into @t    select @id     union all     select id from city where pid = @id        if exists(select 1        from city a inner join @t b on a.pid = b.id        where a.id not in(select id from @t))    begin        insert into @t         select a.id         from city a inner join @t b on a.pid = b.id        where a.id not in(select id from @t)        union all        select * from f_get_child(@pid)    end    returnendGOselect * from city where id in(select * from f_get_child(1))

(2) CTE递归

declare @id intset @id = 1;with tmpas(select * from city where id = @idunion allselect a.* from city ainner join tmp bon a.pid = b.id)select * from tmp order by id

二. 查找父节点
查找节点8的所有父节点,返回结果如下:

idnamepiddepth
5浙江省00
6杭州市51
8滨江区62

1. 迭代
父节点只有一个,不需要做什么限制,一直往上级查找pid就可以了。

if OBJECT_ID(f_get_parent) is not null    drop function f_get_parentGOcreate function f_get_parent(@id int)returns @t table(id int)asbegin    declare @pid int    insert into @t select @id    select @pid = pid from city where id = @id    while @pid<>0    begin        insert into @t values(@pid)        select @pid=pid from city where id=@pid    end    returnendGOselect * from city where id in(select * from f_get_parent(8))

2. 递归
(1) 自定义函数递归

if OBJECT_ID(f_get_parent) is not null    drop function f_get_parentGOcreate function f_get_parent(@id int)returns @t table(id int)ASbegin    declare @pid int    select top 1 @pid = pid    from city    where id = @id    if @pid <> 0    begin        insert into @t        select @id         union all        select * from f_get_parent(@pid)    end    else    begin        insert into @t        select @id     end    returnendGOselect * from city where id in(select * from f_get_parent(8))

(2) CTE递归

declare @id intset @id = 8;with tmpas(select * from city where id = @idunion allselect a.* from city ainner join tmp bon a.id = b.pid)select * from tmp order by id

 

06. 父子节点(树)遍历写法小结