根据二叉树的祖先向左或向右

Question

我有一个 table 存储二叉树如下：

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 我需要 sql 给定 parentId 和 childId，它告诉 parentId 是在左侧还是右侧。例如

FindPoistion(parentId:47,childId: 34) returns 离开

FindPoistion(parentId:23,childId: 8) returns 离开

FindPoistion(parentId:29,childId:30) returns 对

FindPoistion(parentId:47,childId: 5) returns 离开

FindPoistion(parentId:47,childId: 62) returns 对 FindPoistion(parentId:47,childId: 86) returns 对

我如何写一个 sql 给我基于祖先的位置？

上方位置0为左，1为右

这是我目前所拥有的

    WITH name_tree
     AS (SELECT Id,
                Parentid,
                 Placement               
         FROM   BinaryTree
         WHERE  Parentid = 47 and Id= 31
         -- this is the starting point you want in your recursion
         UNION ALL
         SELECT c.Id,
                c.Parentid,
                c.Placement

         FROM   BinaryTree c
                JOIN name_tree p
                  ON p.Id = c.ParentId -- this is the recursion
                     AND c.Id <> c.Parentid

                     )
SELECT distinct Id, parentId, Placement 

FROM   name_tree

Answer 1

Declare @YourTable table (id int,ParentId  int)
Insert into @YourTable values  (47,-1),(23,47),(86,47),( 5,23),(29,23),(68,86),( 8, 5),(31,29),(67,68),(62,67),(30,31),(34,31),(42,34),(40,42)

Declare @Top    int         = 47 
Declare @Fetch  int         = 31 

;with cteP as (
      Select ID
            ,ParentId 
            ,Level=1
      From   @YourTable 
      Where  ID=@Fetch
      Union  All
      Select r.ID
            ,r.ParentId 
            ,p.Level+1
      From   @YourTable r
      Join   cteP p on r.ParentId  = p.ID)
Select ID = @Top
      ,ParentID = -1
      ,Level = 0
      ,Placement = 0
Union All
Select A.ID
      ,ParentID = case when A.Level=1 then @Top else A.ParentId end
      ,A.Level
      ,Placement = case when A.Level=1 then IIF(A.ID<@Top,0,1) 
                   else case when IsNull(B.ID,A.ParentId) < A.ID then 1 else 0
                   end end
From cteP A
Left  Join cteP B on (A.ParentId=B.ParentId and B.ID<> A.ID)

Returns

而下面的Returns

Declare @Top    int         = 47 
Declare @Fetch  int         = 31

根据二叉树的祖先向左或向右

Get Left or Right Based on ancenstor for a binary tree

sql

sql-server

binary-tree