首页 > 代码库 > 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的所有子节点,返回结果如下:
id | name | pid | depth |
1 | 江苏省 | 0 | 0 |
2 | 南京市 | 1 | 1 |
3 | 玄武区 | 2 | 2 |
4 | 鼓楼区 | 2 | 2 |
9 | 苏州市 | 1 | 1 |
10 | 吴中区 | 9 | 2 |
11 | 吴江区 | 9 | 2 |
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的所有父节点,返回结果如下:
id | name | pid | depth |
5 | 浙江省 | 0 | 0 |
6 | 杭州市 | 5 | 1 |
8 | 滨江区 | 6 | 2 |
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. 父子节点(树)遍历写法小结
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。