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