SQL查询来获取一个二进制左侧或右侧位置

Question

我已经二叉树在表格呈现在SQL Server 2014数据库：

UserID ParentUserID Position 
------------------------------ 
1  null   null  <-- ROOT 
2  1   Left 
3  1   Right <-- Last right for ID=1 (query should return 3) 
4  2   Left 
5  4   Left 
6  2   Left 
7  6   Left  <-- Last left for ID=1 (query should return 6) 

下面是图形表示：

我需要编写2个查询。上图中的红线显示我需要检索哪些节点;

1. 最后左腿ID。
2. 最后右腿ID

我如何能实现我的目标。我应该使用递归查询？

您能否提供我需要的查询示例？

Answer 1

可以递归下来递归公用表表达式的左边或右边（CTE）使用select top 1 * ... order by depth你可以找到最深的节点：

; with left_hand_recurse as 
     (
     select UserID 
     ,  ParentUserID 
     ,  1 as depth 
     from Table1 where ParentUserID is null 
     union all 
     select child.UserID 
     ,  child.ParentUserID 
     ,  parent.depth + 1 
     from left_hand_recurse parent 
     join Table1 child 
     on  parent.UserID = child.ParentUserID 
       and position = 'Left' 
     ) 
select top 1 * 
from left_hand_recurse 
order by 
     depth desc 
; 

Example at SQL Fiddle.

附：你的示例数据使得6和4都是2的左边父亲。我假设6是5的左边父亲。