无需递归实现二叉树查询上线/下线节点的数据结构实现
4.92/5 (12投票s)
可用于多层次营销的二叉树（可相应修改用于 n 叉树）。
引言
我们有时会面临存储二叉树数据并进行查询的问题。我们通常依赖递归（因此成本高）来查询树结构。这里有一个简单的数据结构更改，可以使用简单的 SQL 语句查询树结构 - 无需递归。
背景
在某些情况下，我们希望将二叉树的节点与它们的父节点一起存储在数据库中，并带有位置信息（在这种情况下，是父节点的左节点或右节点）。当我们要查询数据库以获取某个节点上线或下线节点，或者我们想获取二叉树中每个级别的节点计数时，问题就出现了。
您可以考虑在此代码示例的实现中，为多级营销公司创建数据结构来维护成员及其层级关系。
Using the Code
提出的解决方案包含 2 个数据表和 1 个触发器。
注意：下面使用的字段命名约定有点奇怪，但遵循以下规则 - 字段名称的前 5 个字符对应表名，接下来的 2 个字符定义数据类型，接下来的 2 个字符定义约束，其余的字符是字段名。
表 1
tbl_BinaryTree_Nodes，存储节点详情（例如成员详情）的主表
字段
Nodes_IN_PK_Code-- 表的主键Nodes_IN_FK_ParentCode-- 父节点Nodes_CH_xx_Position-- 父节点下的位置，左或右Nodes_VC_xx_NodeData-- 节点数据 -（可以添加更多字段来容纳节点数据
表 2
tbl_BinaryTree_Hierarchy，存储节点层级信息的辅助表
字段
Hiera_IN_PK_Code-- 表的主键Hiera_IN_FK_ParentCode-- 外键Hiera_IN_FK_ChildCode-- 外键Hiera_CH_xx_Position-- 父节点下的位置，左或右Hiera_IN_xx_NodeLevel-- 树下的节点级别
触发器 1
trg_BinaryTree_Nodes_ADD，用于更新后续查询的树层级信息
创建表和触发器的 SQL 如下
Create Table tbl_BinaryTree_Nodes
(
Nodes_IN_PK_Code Int Identity(1,1) Constraint PK_Nodes Primary Key,
Nodes_IN_FK_ParentCode Int Constraint _
FK_Nodes_To_Nodes References tbl_BinaryTree_Nodes (Nodes_IN_PK_Code ),
Nodes_CH_xx_Position Char(1) Not Null Constraint CH_Nodes_Position Check _
(Nodes_CH_xx_Position = 'L' OR Nodes_CH_xx_Position = 'R'),
Nodes_VC_xx_NodeData Varchar(50)
)
GO
Create Table tbl_BinaryTree_Hierarchy
(
Hiera_IN_PK_Code Int Identity(1,1) Constraint PK_Hiera Primary Key,
Hiera_IN_FK_ParentCode Int Constraint _
FK_Hiera_Nodes_Parent References tbl_BinaryTree_Nodes(Nodes_IN_PK_Code ),
Hiera_IN_FK_ChildCode Int Constraint FK_Hiera_Nodes_Child References _
tbl_BinaryTree_Nodes(Nodes_IN_PK_Code ),
Hiera_CH_xx_Position Char(1) Not Null Constraint CH_Hiera_Position Check _
(Hiera_CH_xx_Position = 'L' OR Hiera_CH_xx_Position = 'R'),
Hiera_IN_xx_NodeLevel int
)
GO
Create Trigger trg_BinaryTree_Nodes_ADD
On tbl_BinaryTree_Nodes
For Insert
AS
Begin
IF (@@RowCount=1)
Begin
Insert Into tbl_BinaryTree_Hierarchy
(Hiera_IN_FK_ParentCode, Hiera_IN_FK_ChildCode, _
Hiera_CH_xx_Position, Hiera_IN_xx_NodeLevel)
Select (Case When Hiera_IN_FK_ParentCode Is Null _
Then Hiera_IN_FK_ChildCode Else Hiera_IN_FK_ParentCode End),
(Select Nodes_IN_PK_Code From Inserted), _
(Case When Hiera_IN_FK_ParentCode Is Null _
Then (Select Nodes_CH_xx_Position From Inserted) _
Else Hiera_CH_xx_Position End) ,
(Hiera_IN_xx_NodeLevel + 1 )
From tbl_BinaryTree_Hierarchy Where Hiera_IN_FK_ChildCode = _
(Select Nodes_IN_FK_ParentCode From Inserted)
Union ALL
Select NULL , Nodes_IN_PK_Code , Nodes_CH_xx_Position , 1 From Inserted
End
Else
Begin
RaisError ('Multiple Insertion Not Handled in Trigger to _
update tbl_BinaryTree_Hierarchy',1,1)
-- Code Using Cursor for Multiple insert
--...
--...
--...
--
End
End
GO
SQL 查询
我们将使用示例数据填充数据库以进行查询。我们将创建一个如下所示的树
--'------------------------------------------
--' The Binary Tree Representation
--'------------------------------------------
--' RootNode
--' --------|-------
--' | |
--' AL1 AL2
--' -----|-----
--' | |
--' AL2 AR2
--' ---|---
--' | |
--' AL3 AR3
--'------------------------------------------
生成上述树的 SQL 如下
Insert Into tbl_BinaryTree_Nodes (Nodes_IN_FK_ParentCode, Nodes_CH_xx_Position, _
Nodes_VC_xx_NodeData) Values(Null,'L','Root Node')
GO
Insert Into tbl_BinaryTree_Nodes (Nodes_IN_FK_ParentCode, Nodes_CH_xx_Position, _
Nodes_VC_xx_NodeData) Values(1,'L','AL1')
GO
Insert Into tbl_BinaryTree_Nodes (Nodes_IN_FK_ParentCode, Nodes_CH_xx_Position, _
Nodes_VC_xx_NodeData) Values(1,'R','AR1')
GO
Insert Into tbl_BinaryTree_Nodes (Nodes_IN_FK_ParentCode, Nodes_CH_xx_Position, _
Nodes_VC_xx_NodeData) Values(2,'L','AL2')
GO
Insert Into tbl_BinaryTree_Nodes (Nodes_IN_FK_ParentCode, Nodes_CH_xx_Position, _
Nodes_VC_xx_NodeData) Values(2,'R','AR2')
GO
Insert Into tbl_BinaryTree_Nodes (Nodes_IN_FK_ParentCode, Nodes_CH_xx_Position, _
Nodes_VC_xx_NodeData) Values(4,'L','AL3')
GO
Insert Into tbl_BinaryTree_Nodes (Nodes_IN_FK_ParentCode, Nodes_CH_xx_Position, _
Nodes_VC_xx_NodeData) Values(4,'R','AR3')
-- A. Get All Nodes directly under current Node
Select B.Nodes_VC_xx_NodeData, Hiera_IN_xx_NodeLevel From tbl_BinaryTree_Hierarchy H
Left Outer Join tbl_BinaryTree_Nodes B on H.Hiera_IN_FK_ChildCode = B.Nodes_IN_PK_Code
Where H.Hiera_IN_FK_ParentCode=1
-- B. Get All Nodes directly under current Node in left side
Select B.Nodes_VC_xx_NodeData, Hiera_IN_xx_NodeLevel From tbl_BinaryTree_Hierarchy H
Left Outer Join tbl_BinaryTree_Nodes B on H.Hiera_IN_FK_ChildCode = B.Nodes_IN_PK_Code
Where H.Hiera_IN_FK_ParentCode=1 And H.Hiera_CH_xx_Position ='L'
-- C. Get All Nodes directly under current Node in right side
Select B.Nodes_VC_xx_NodeData, Hiera_IN_xx_NodeLevel From tbl_BinaryTree_Hierarchy H
Left Outer Join tbl_BinaryTree_Nodes B on H.Hiera_IN_FK_ChildCode = B.Nodes_IN_PK_Code
Where H.Hiera_IN_FK_ParentCode=1 And H.Hiera_CH_xx_Position ='R'
-- D. Get All Nodes directly above the current
Select B.Nodes_VC_xx_NodeData, Hiera_IN_xx_NodeLevel From tbl_BinaryTree_Hierarchy H
Left Outer Join tbl_BinaryTree_Nodes B on H.Hiera_IN_FK_ParentCode = B.Nodes_IN_PK_Code
Where H.Hiera_IN_FK_ChildCode=7
-- E. Get count of Nodes at each level under a specific node
Select Hiera_IN_xx_NodeLevel, count(*) From tbl_BinaryTree_Hierarchy H
Left Outer Join tbl_BinaryTree_Nodes B on H.Hiera_IN_FK_ChildCode = B.Nodes_IN_PK_Code
Where H.Hiera_IN_FK_ParentCode=1
Group By Hiera_IN_xx_NodeLevel
-- F. To find out the Nodes which got balanced due to new node entry
-- Lets us assume that the newly added node is AR3 - (which makes AL2 balanced)
-- We can use simple SQL Query or Common Table Expressions (CTE)
-- on SQL 2005 to get the data
-- SQL Using Common Table Expressions (CTE) on SQL 2005
With CTE as (
Select B.Nodes_IN_PK_Code as PK, B.Nodes_VC_xx_NodeData as NodeData, _
Hiera_IN_xx_NodeLevel as NodeLevel,
'' as IsBalanced,
Power(2,Hiera_IN_xx_NodeLevel)-2 as TotalNodeForBalanceTree,
(Select Count(Hiera_IN_PK_Code) From tbl_BinaryTree_Hierarchy _
Where Hiera_CH_xx_Position = 'L' and _
Hiera_IN_FK_ParentCode=B.Nodes_IN_PK_Code) _
as TotalLeftChild,
(Select Count(Hiera_IN_PK_Code) From tbl_BinaryTree_Hierarchy _
Where Hiera_CH_xx_Position = 'R' and _
iera_IN_FK_ParentCode=B.Nodes_IN_PK_Code) _
as TotalRightChild
From tbl_BinaryTree_Hierarchy H
Left Outer Join tbl_BinaryTree_Nodes B on H.Hiera_IN_FK_ParentCode = B.Nodes_IN_PK_Code
Where H.Hiera_IN_FK_ParentCode is NOT NULL and H.Hiera_IN_FK_ChildCode = 7
-- (Primary key of Newly Added Node)
)
Select CTE.PK, CTE.NodeData, CTE.NodeLevel,
Case When ((CTE.TotalNodeForBalanceTree / 2 = TotalLeftChild) and _
(CTE.TotalNodeForBalanceTree / 2 = TotalRightChild)) then _
'Yes' Else' No' End As IsBalanced,
CTE.TotalNodeForBalanceTree , CTE.TotalLeftChild , CTE.TotalRightChild
From CTE
更多查询 - 2
--'------------------------------------------
--' TREE 2
--' The Binary Tree Representation Tree - 2
--'------------------------------------------
--' RootNode
--' --------|-------
--' | |
--' AL AR
--' -----|----- -----|-----
--' | | | |
--' ZL ZR BL BR
--' ---|--- ---|---
--' | | | |
--' CL CR DL *DR*
--'------------------------------------------
A. 如何根据新节点插入查找平衡节点（参考 Tree -2）
假设新添加的节点是 *DR* -（这使得 AR、BR 平衡）。
我们可以使用简单的 SQL 查询或 SQL 2005 上的通用表表达式 (CTE) 来获取数据
With CTE as (
Select B.Nodes_IN_PK_Code as PK, B.Nodes_VC_xx_NodeData as NodeData, _
Hiera_IN_xx_NodeLevel as NodeLevel,
'' as IsBalanced,
Power(2,Hiera_IN_xx_NodeLevel)-2 as TotalNodeForBalanceTree,
(Select Count(Hiera_IN_PK_Code) From tbl_BinaryTree_Hierarchy _
Where Hiera_CH_xx_Position = 'L' and _
Hiera_IN_FK_ParentCode=B.Nodes_IN_PK_Code) _
as TotalLeftChild,
(Select Count(Hiera_IN_PK_Code) From tbl_BinaryTree_Hierarchy _
Where Hiera_CH_xx_Position = 'R' and _
Hiera_IN_FK_ParentCode=B.Nodes_IN_PK_Code) _
as TotalRightChild
From tbl_BinaryTree_Hierarchy H
Left Outer Join tbl_BinaryTree_Nodes B on H.Hiera_IN_FK_ParentCode = _
B.Nodes_IN_PK_Code
Where H.Hiera_IN_FK_ParentCode _
is NOT NULL and H.Hiera_IN_FK_ChildCode = 7 -- (Primary key of Newly Added Node)
)
Select CTE.PK, CTE.NodeData, CTE.NodeLevel,
Case When ((CTE.TotalNodeForBalanceTree / 2 = TotalLeftChild) and _
(CTE.TotalNodeForBalanceTree / 2 = TotalRightChild)) then 'Yes' Else' No' _
End As IsBalanced,
CTE.TotalNodeForBalanceTree , CTE.TotalLeftChild , CTE.TotalRightChild
From CTE
B. 查找节点的极端左叶和右叶（参考 Tree -2）
要在任何节点的左侧或右侧添加新节点，您只需知道相应侧的最后一个节点（叶子节点）。您可以使用简单的 SQL 查询来获取此信息。
例如，在上面的树中，根节点的极端右侧是 *DR*，极端左侧是 ZL。类似地，节点 AR 的极端右侧是 *DR*，极端左侧是 CL。
;with CTE (ExtremeNode, Position, NodeLevel )As
(
Select Hiera_IN_FK_ChildCode, Hiera_CH_xx_Position, 1 from tbl_BinaryTree_Hierarchy
where Hiera_IN_xx_NodeLevel=2 and Hiera_IN_FK_ParentCode = _
?ParentNodePK? and Hiera_CH_xx_Position = ?LegSide?
UNION ALL
Select Hiera_IN_FK_ChildCode, Hiera_CH_xx_Position , CTE.NodeLevel + 1 _
from tbl_BinaryTree_Hierarchy
INNER JOIN CTE ON CTE.ExtremeNode = Hiera_IN_FK_ParentCode _
and CTE.Position = Hiera_CH_xx_Position
where Hiera_IN_xx_NodeLevel = 2
)
Select Top 1 * From CTE order By NodeLevel Desc;
C. 获取因新插入而成为平衡节点的节点列表（参考 Tree -2 和 MLM 佣金支付）
当 *DR* 被添加时，BR 和 AR 会获得报酬 - 但具体多少尚不清楚 - 根据一般的 MLM 趋势，我们可以计算出 BR 将获得 1 个对的收益，AR 将获得 1 个对的收益。
我们需要找出相对于新添加节点的父节点列表，这些节点将获得收益。
现在，获取需要支付报酬的节点列表如下。
下面的 SQL 查询将为您提供所有父节点的列表，最后一列 ShouldIPay （Pay 或 DoNotPay）指示哪个父节点需要支付报酬（根据需要修改字段列表）。
With CTE as (
Select B.Nodes_IN_PK_Code as PK, B.Nodes_VC_xx_NodeData as NodeData, _
Hiera_IN_xx_NodeLevel as NodeLevel, _
Hiera_CH_xx_Position as Position, '' as IsBalanced,
Power(2,Hiera_IN_xx_NodeLevel)-2 as TotalNodeForBalanceTree,
(Select Count(Hiera_IN_PK_Code) From tbl_BinaryTree_Hierarchy _
Where Hiera_CH_xx_Position = 'L' and _
Hiera_IN_FK_ParentCode=B.Nodes_IN_PK_Code) as TotalLeftChild,
(Select Count(Hiera_IN_PK_Code) From tbl_BinaryTree_Hierarchy _
Where Hiera_CH_xx_Position = 'R' and _
Hiera_IN_FK_ParentCode=B.Nodes_IN_PK_Code) as TotalRightChild
From tbl_BinaryTree_Hierarchy H
Left Outer Join tbl_BinaryTree_Nodes B on H.Hiera_IN_FK_ParentCode = _
B.Nodes_IN_PK_Code
Where H.Hiera_IN_FK_ParentCode is NOT NULL and _
H.Hiera_IN_FK_ChildCode = ?PKofNewnode? -- (Primary key of Newly Added Node)
)
Select CTE.PK, CTE.NodeData, CTE.NodeLevel, CTE.Position,
Case When ((CTE.TotalNodeForBalanceTree / 2 = TotalLeftChild) _
and (CTE.TotalNodeForBalanceTree / 2 = TotalRightChild)) _
then 'Yes' Else' No' End As IsBalanced,
CTE.TotalNodeForBalanceTree , CTE.TotalLeftChild , CTE.TotalRightChild,
Case When Position ='L' then (Case When TotalLeftChild<=TotalRightChild _
Then 'PAY' Else 'Do Not Pay' End )
When Position ='R' then (Case When TotalLeftChild>=TotalRightChild _
Then 'PAY' Else 'Do Not Pay' End )
End As ShouldIPay
From CTE
这些表可以轻松修改以存储有关节点信息的附加信息，但基本字段将保持不变。
目前，触发器仅针对单次插入编写，我们可以修改触发器以处理批量插入。我们需要编写触发器来处理节点移动，以修改层级表。
历史
- 修订 1：添加了更多查询 - 2 个部分