二叉树获取底部极左或右 [英] Binary Tree Get Bottom extreme Left or Right

问题描述

我有一个存储二叉树的表，如下所示:

I have a table that stores a binary tree as follows:

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 现在，我需要获取给定id的BottomLeft，在此示例中，对于47，其左下角是5 并且我需要获取给定id的右下角，在本例中为47，其右下角是86

Using MSSQL now, I need to get BottomLeft of a given id, in this example, for 47 its bottom left is 5 and I need to get the bottom right of a given id, in this example for 47 its bottom right is 86

左下或右下不是左下或右下的最低级别，而是左或右叶子的外侧.

Bottom left or right is not the lowest level left or right, but extreme outside left or right leaf.

我该如何编写一条给定ID给我左下角或右下角的sql?

位于0上方和1右侧的上方

Above placement of 0 is left and 1 is right

推荐答案

您应该使用递归查询

这是最左侧查询的示例，您可以通过将展示位置更改为1来轻松地将其更改为最右侧查询.

here is example for leftmost query, you can easy change it to rightmost query by changing the placement to 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

这篇关于二叉树获取底部极左或右的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！