Binary Tree Получить Bottom крайний левый или правый

Question

У меня есть таблица, в которой хранится бинарное дерево следующим образом:

Id ParentId Level Placement 
47 -1  0  0 
23 47  1  0 
86 47  1  1 
5 23  2  0 
29 23  2  1 
68 86  2  0 
8 5  3  1 
31 29  3  1 
67 68  3  0 
. 
. 
. 

Использование MSSQL сейчас, мне нужно, чтобы получить BottomLeft данного идентификатора, в этом примере, для 47 его левый нижний - 5 , и мне нужно получить нижнее правое значение для данного идентификатора, в этом примере для 47 его нижнего правого 86:

Нижняя левая или правая сторона не является самым низким уровнем слева или справа, но вне пределов снаружи левый или правый лист.

Как написать sql, который дает мне нижнее левое или правое для данного идентификатора?

Над размещением 0 слева и 1 является правильным

Answer 1

Вы должны использовать рекурсивный запрос

здесь пример для левого запроса, вы можете легко изменить его на крайний правый запрос путем изменения размещения 1

with leftmost(ParentId,Id,depth) as (
    select t.Id,t.Id,0 
    from #BinaryTree t 
    union all 
    select lm.parentid,t.Id,lm.depth+1 
    from leftmost lm 
     join #BinaryTree t on lm.Id = t.ParentId 
    where t.Placement = 0 -- change to 1 for right most 
) 
select top 1 Id 
from leftmost 
where parentid = 47 --replace with the id you query 
order by depth desc 

Answer 2

Примечание: финал, где закомментирована проиллюстрировать полную иерархию.

Создание демонстративных Таблица

Declare @YourTable table (Id int,Pt int, Level int, Placement int) 
Insert Into @YourTable values 
(47,-1, 0,0), 
(23,47, 1,0), 
(86,47, 1,1), 
(5 ,23, 2,0), 
(29,23, 2,1), 
(68,86, 2,0), 
(8 , 5, 3,1), 
(31,29, 3,1), 
(67,68, 3,0) 

---

В SQL -

Declare @Top int = null   --<< Sets top of Hier Try 5 
Declare @MaxLvl int = 99 
Declare @Nest varchar(25) = ' ' --<< Optional: Added for readability 

;with cteHB (Seq,ID,Pt,Lvl,Title,Placement) as (
    Select Seq = cast(1000+Row_Number() over (Order by ID) as varchar(500)) 
      ,ID 
      ,Pt 
      ,Lvl=1 
      ,Title =concat('Item ',ID) 
      ,Placement 
    From @YourTable Where (Pt=-1 and isnull(@Top,-1) =-1) or (ID=@Top and isnull(@Top,0) <>0) 
    Union All 
    Select Seq = cast(concat(cteHB.Seq,'.',1000+Row_Number() over (Order by cteCD.ID)) as varchar(500)) 
      ,cteCD.ID 
      ,cteCD.Pt 
      ,cteHB.Lvl+1 
      ,Title = concat('Item ',cteCD.ID) 
      ,cteCD.Placement 
    From @YourTable cteCD 
    Join cteHB on cteCD.Pt = cteHB.ID and cteHB.Lvl+1<=@MaxLvl and cteCD.Placement=0) 

,cteR1 as (Select Seq,ID,R1=Row_Number() over (Order By Seq) From cteHB) 
,cteR2 as (Select A.Seq,A.ID,R2=Max(B.R1) From cteR1 A Join cteR1 B on (B.Seq like A.Seq+'%') Group By A.Seq,A.ID) 
Select B.R1 
     ,C.R2 
     ,A.ID 
     ,A.Pt 
     ,A.Lvl 
     ,Title = Replicate(@Nest,A.Lvl) + A.Title 
     ,A.Placement 
From cteHB A 
Join cteR1 B on A.ID=B.ID 
Join cteR2 C on A.ID=C.ID 
--Where R1=R2 
Order By B.R1    

Возвращает

R1 R2 ID Pt Lvl Title    Placement 
1 9 47 -1 1  Item 47    0 
2 6 23 47 2   Item 23   0 
3 4 5 23 3   Item 5   0 
4 4 8 5 4    Item 8  1 
5 6 29 23 3   Item 29  1 
6 6 31 29 4    Item 31  1 
7 9 86 47 2   Item 86   1 
8 9 68 86 3   Item 68  0 
9 9 67 68 4    Item 67  0