昨天笔试了一个存储过程的问题，请大家帮忙，在线等
2 SQLServer与算法：

有如下表，记录了分左右区的2叉树记录。其中：LorR字段，-1 表示顶级，1 表示左边，2表示右边；Parent_id子段，-1 表示顶级，其它表示上级父ID;User_id字段值是唯一的。
User_idParent_idLorR
1-1-1
211
312
421
522
631
......
请书写一个存储过程，返回给定User_id 的左、右区中小区(网络点数少一点的区，一样多则左边优先)的最下一个新节点（如有左右2个空节点，左边优先）。

格式：
P_GetNewNode (@User_id int, @Node_id int output, @LorR int output)
AS
......
set @Node_id = ...
set @LorR = ...
GO


[解决办法]
请书写一个存储过程，返回给定User_id 的左、右区中小区(网络点数少一点的区，一样多则左边优先)的最下一个新节点（如有左右2个空节点，左边优先）。
--------
啥意思？
[解决办法]
/*测试环境*/
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

向下找所有子树杈中,左或右最小的一个节点
找到底


/*结果*/
421
841
211



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

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
begin

if 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 #temp2

select *,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=1

while @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
end


select * from #temp1
UNION
select * from #temp2 order by fldlevel

end


GO
SET QUOTED_IDENTIFIER OFF
GO
SET ANSI_NULLS ON
GO


EXEC SP_TREE 4


/*Ｒesult
4211
2112
8412
1-1-13


*/

[解决办法]
/*
2 SQLServer与算法：

有如下表，记录了分左右区的2叉树记录。其中：LorR字段，-1 表示顶级，1 表示左边，2表示右边；Parent_id子段，-1 表示顶级，其它表示上级父ID;User_id字段值是唯一的。
User_idParent_idLorR
1-1-1
211
312
421
522
631
......
请书写一个存储过程，返回给定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)
go

insert 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
end

go
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
GO

declare @UserID int, @NodeID int, @LorR int
set @UserID=1
print( 'UserIDNodeIDLorR ')
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
end

go
drop function dbo.fnGetSubLayers
drop function dbo.fnGetSubNodes
drop procedure dbo.spGetNewNode
drop table BTree