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的左邊父親。