昨天笔试了一个存储过程的问题，请大家帮忙，在线等

Question

2 SQLServer与算法：有如下表，记录了分左右区的2叉树记录。其中：LorR字段，-1 表示顶级，1 表示左边，2表示右边；Parent_id子段，-1 表示顶级，其它表示上级父ID;User_id字段值是唯一的。
User_id Parent_id LorR
1 -1 -1
2 1 1
3 1 2
4 2 1
5 2 2
6 3 1
......
请书写一个存储过程，返回给定User_id 的左、右区中小区(网络点数少一点的区，一样多则左边优先)的最下一个新节点（如有左右2个空节点，左边优先）。格式：
P_GetNewNode (@User_id int, @Node_id int output, @LorR int output)
AS
......
set @Node_id = ...
set @LorR = ...
GO

Answer 1

请书写一个存储过程，返回给定User_id 的左、右区中小区(网络点数少一点的区，一样多则左边优先)的最下一个新节点（如有左右2个空节点，左边优先）。
--------
啥意思？

Answer 2

你要的返回值是 按树查找到底? 还是只根据uer_id 找到它本身的树就好 ????

Answer 3

alter proc P_GetNewNode (@User_id int)
AS
select * from Tree a where [User_id]=@User_id and not
exists (select 1 from Tree where [User_id]=@User_id and  Parent_id=a.Parent_id
and [User_id]<a.[User_id])这样可以单行的 找到你输入的 user_id 对应的最小的树杈
但是 你需要 循环找到底么?
就是需要 把树遍历完么 ?

Answer 4

/*测试环境*/
create table Tree (
[User_id] int,
Parent_id int,
LorR int
)
insert into Tree select 1,-1,-1
union all select 2,1,1
union all select 3,1,2
union all select 4,2,1
union all select 5,2,2
union all select 6,3,1
union all select 7,3,2
union all select 8,4,1
union all select 9,4,2/*存储过程*/
create proc P_GetNewNode (@User_id int)
AS
select * into #temp from Tree where [User_id]=@User_id
while @@rowcount=1
begin
insert #temp select b.*
from #temp a,tree b 
where a.[user_id]=b.parent_id 
and b.[user_id] not in (select [user_id] from #temp)
and not exists (select 1 from Tree where Parent_id=b.Parent_id
and [User_id]<b.[User_id])
end 
select * from #temp向下找所有子树杈中,左或右最小的一个节点 
找到底
/*结果*/
4 2 1
8 4 1
2 1 1

Answer 5

如果这颗树是有规律的,即User_id顺序递增,树左边一定大于右边的话,那么 welove1983(啊哈啊哈) 所写的已经解决最重要的问题.

Answer 6

/*
2 SQLServer与算法：有如下表，记录了分左右区的2叉树记录。其中：LorR字段，-1 表示顶级，1 表示左边，2表示右边；Parent_id子段，-1 表示顶级，其它表示上级父ID;User_id字段值是唯一的。
User_id Parent_id LorR
1 -1 -1
2 1 1
3 1 2
4 2 1
5 2 2
6 3 1
......
请书写一个存储过程，返回给定User_id 的左、右区中小区(网络点数少一点的区，一样多则左边优先)的最下一个新节点（如有左右2个空节点，左边优先）。格式：
P_GetNewNode (@User_id int, @Node_id int output, @LorR int output)
AS
......
set @Node_id = ...
set @LorR = ...
GO
*/create table BTree(UserID int, ParentID int, LorR int)
goinsert BTree select 1, -1, -1
union all select 2, 1, 1
union all select 3, 1, 2
union all select 4, 2, 1
union all select 5, 2, 2
union all select 6, 3, 1--select * from BTree
go
create function fnGetSubNodes(@UserID int)
returns int as 
begin
declare @Total int, @SubNodeL int, @SubNodeR int
set @Total=0
select @SubNodeL=UserID from BTree where ParentID=@UserID and LorR=1
select @SubNodeR=UserID from BTree where ParentID=@UserID and LorR=2
if @SubNodeL is not null
set @Total=1+dbo.fnGetSubNodes(@SubNodeL)
if @SubNodeR is not null
set @Total=@Total+1+dbo.fnGetSubNodes(@SubNodeR)
return @Total
endgo
create function fnGetSubLayers(@UserID int, @Layer int)
returns varchar(100) as
begin
declare @result varchar(100)
set @result=cast(@Layer as varchar)+'|'+cast(@UserID as varchar)
declare @NID int, @NID2 int, @LL varchar(10), @LR varchar(10)
select @NID=UserID from BTree where ParentID=@UserID and LorR=1
select @NID2=UserID from BTree where ParentID=@UserID and LorR=2
if @NID is not null
begin
set @LL=dbo.fnGetSubLayers(@NID,@Layer+1)
if @NID2 is not null
begin
set @LR=dbo.fnGetSubLayers(@NID2,@Layer+1)
if(convert(int,left(@LL,charindex('|',@LL)-1))>=convert(int,left(@LR,charindex('|',@LR)-1)))
set @result=@LL
else
set @result=@LR
end
else
set @result=@LL
end
else if @NID2 is not null
set @result=@LR
return @result
end
go
create procedure spGetNewNode(@UserID int, @NodeID int output, @LorR int output)
AS
BEGIN
declare @SubNodeL int, @SubNodeR int, @Layer varchar(100)
select @SubNodeL=UserID from BTree where ParentID=@UserID and LorR=1
select @SubNodeR=UserID from BTree where ParentID=@UserID and LorR=2
if @SubNodeL is not null
if @SubNodeR is not null
if(dbo.fnGetSubNodes(@SubNodeL)<=dbo.fnGetSubNodes(@SubNodeR))
set @Layer=dbo.fnGetSubLayers(@SubNodeL,0)
else
set @Layer=dbo.fnGetSubLayers(@SubNodeR,0)
else
set @Layer=dbo.fnGetSubLayers(@SubNodeL,0)
else if @SubNodeR is not null
set @Layer=dbo.fnGetSubLayers(@SubNodeR,0)
select @NodeID=convert(int,right(@Layer,len(@Layer)-charindex('|',@Layer)))
select @LorR=LorR from BTree where UserID=@NodeID
END
GOdeclare @UserID int, @NodeID int, @LorR int
set @UserID=1
exec dbo.spGetNewNode @UserID, @NodeID output, @LorR output
select @UserID, @NodeID, @LorR go
drop function dbo.fnGetSubLayers
drop function dbo.fnGetSubNodes
drop procedure dbo.spGetNewNode
drop table BTree

Answer 7

create table Tree (
[User_id] int,
Parent_id int,
LorR int
)
insert into Tree select 1,-1,-1
union all select 2,1,1
union all select 3,1,2
union all select 4,2,1
union all select 5,2,2
union all select 6,3,1
union all select 7,3,2
union all select 8,4,1
union all select 9,4,2
SET QUOTED_IDENTIFIER ON 
GO
SET ANSI_NULLS ON 
GO
create    proc sp_tree (@uid int)
as 
beginif exists (select name from tempdb.dbo.sysobjects where id=object_id('tempdb..#temp1'))
drop table #temp1
if exists (select name from tempdb.dbo.sysobjects where id=object_id('tempdb..#temp1'))
drop table #temp2select *,fldlevel=1 into #temp1 from tree where [user_id]=@uid 
select *,fldlevel=1 into #temp2 from tree where [user_id]=@uid
declare @i int
set @i=1
while @i<10
begin
if not exists (select * from #temp1 where fldlevel=@i) break
insert into #temp1
select 
a.*,
@i+1
from 
tree a inner join (select * from #temp1 where fldlevel=@i) b on
b.parent_id=a.[user_id]
set @i=@i+1
end
set @i=1while @i<10
begin
if not exists (select * from #temp2 where fldlevel=@i) break
insert into #temp2
select 
a.*,
@i+1
from 
tree a inner join (select * from #temp2 where fldlevel=@i) b on
a.parent_id=b.user_id and 
(not exists (select *from tree where b.user_id=parent_id and lorR<A.lorR))
set @i=@i+1
endselect * from #temp1 
UNION 
select * from #temp2 order by  fldlevelend
GO
SET QUOTED_IDENTIFIER OFF 
GO
SET ANSI_NULLS ON 
GOEXEC SP_TREE 4/*Ｒesult
4 2 1 1
2 1 1 2
8 4 1 2
1 -1 -1 3
*/

Answer 8

/*
2 SQLServer与算法：有如下表，记录了分左右区的2叉树记录。其中：LorR字段，-1 表示顶级，1 表示左边，2表示右边；Parent_id子段，-1 表示顶级，其它表示上级父ID;User_id字段值是唯一的。
User_id Parent_id LorR
1 -1 -1
2 1 1
3 1 2
4 2 1
5 2 2
6 3 1
......
请书写一个存储过程，返回给定User_id 的左、右区中小区(网络点数少一点的区，一样多则左边优先)的最下一个新节点（如有左右2个空节点，左边优先）。格式：
P_GetNewNode (@User_id int, @Node_id int output, @LorR int output)
AS
......
set @Node_id = ...
set @LorR = ...
GO
*/create table BTree(UserID int, ParentID int, LorR int)
goinsert BTree select 1, -1, -1
union all select 2, 1, 1
union all select 3, 1, 2
union all select 4, 2, 1
union all select 5, 2, 2
union all select 6, 3, 1
union all select 7, 4, 1
union all select 8, 6, 1
union all select 9, 6, 2
union all select 10, 7, 1
union all select 11, 8, 1
union all select 12, 8, 2
union all select 13, 9, 2
union all select 14, 10, 2--select * from BTree
go
create function fnGetSubNodes(@UserID int)
returns int as 
begin
declare @Total int, @SubNodeL int, @SubNodeR int
set @Total=0
select @SubNodeL=UserID from BTree where ParentID=@UserID and LorR=1
select @SubNodeR=UserID from BTree where ParentID=@UserID and LorR=2
if @SubNodeL is not null
set @Total=1+dbo.fnGetSubNodes(@SubNodeL)
if @SubNodeR is not null
set @Total=@Total+1+dbo.fnGetSubNodes(@SubNodeR)
return @Total
endgo
create function fnGetSubLayers(@UserID int, @Layer int)
returns varchar(100) as
begin
declare @result varchar(100)
set @result=cast(@Layer as varchar)+'|'+cast(@UserID as varchar)
declare @NID int, @NID2 int, @LL varchar(10), @LR varchar(10)
select @NID=UserID from BTree where ParentID=@UserID and LorR=1
select @NID2=UserID from BTree where ParentID=@UserID and LorR=2
if @NID is not null
begin
set @LL=dbo.fnGetSubLayers(@NID,@Layer+1)
if @NID2 is not null
begin
set @LR=dbo.fnGetSubLayers(@NID2,@Layer+1)
if(convert(int,left(@LL,charindex('|',@LL)-1))>=convert(int,left(@LR,charindex('|',@LR)-1)))
set @result=@LL
else
set @result=@LR
end
else
set @result=@LL
end
else if @NID2 is not null
begin
set @LR=dbo.fnGetSubLayers(@NID2,@Layer+1)
set @result=@LR
end
return @result
end
go
create procedure spGetNewNode(@UserID int, @NodeID int output, @LorR int output)
AS
BEGIN
declare @SubNodeL int, @SubNodeR int, @Layer varchar(100)
select @Layer='0|'+cast(@UserID as varchar)
select @SubNodeL=UserID from BTree where ParentID=@UserID and LorR=1
select @SubNodeR=UserID from BTree where ParentID=@UserID and LorR=2
if @SubNodeL is not null
if @SubNodeR is not null
if(dbo.fnGetSubNodes(@SubNodeL)<=dbo.fnGetSubNodes(@SubNodeR))
set @Layer=dbo.fnGetSubLayers(@SubNodeL,0)
else
set @Layer=dbo.fnGetSubLayers(@SubNodeR,0)
else
set @Layer=dbo.fnGetSubLayers(@SubNodeL,0)
else if @SubNodeR is not null
set @Layer=dbo.fnGetSubLayers(@SubNodeR,0)
select @NodeID=convert(int,right(@Layer,len(@Layer)-charindex('|',@Layer)))
select @LorR=LorR from BTree where UserID=@NodeID
END
GOdeclare @UserID int, @NodeID int, @LorR int
set @UserID=1
print('UserID NodeID LorR')
while @UserID<=14
begin
exec dbo.spGetNewNode @UserID, @NodeID output, @LorR output
print(cast(@UserID as varchar)+' '+cast(@NodeID as varchar)+' '+cast(@LorR as varchar))
set @UserID=@UserID+1
endgo
drop function dbo.fnGetSubLayers
drop function dbo.fnGetSubNodes
drop procedure dbo.spGetNewNode
drop table BTree

Answer 9

/*
结果：
(14 row(s) affected)
UserID NodeID LorR
1 14 2
2 5 2
3 11 1
4 14 2
5 5 2
6 13 2
7 14 2
8 11 1
9 13 2
10 14 2
11 11 1
12 12 2
13 13 2
14 14 2
*/