如何通过SQL递归CTE生成BST每个节点从根到自身的遍历路径

测试数据准备 #

创建表的代码如下：

create table BST
(
    N Int,
    P Int
)

插入测试数据的代码：

insert into BST values 
(1,3),
(3,8),
(4,6),
(6,3),
(7,6),
(8,NULL),
(10,8),
(13,14),
(14,10)

该二叉搜索树（BST）的层级结构如下：

需求与现有实现问题 #

需要编写查询，返回每个节点从根节点到该节点的遍历路径。目前尝试用递归CTE实现的代码如下：

WITH NodeCTE (N, P, [Level])
  AS
(
  SELECT N,
         P,
         1
  FROM BST
  
  WHERE P IS NULL
  
  UNION ALL
  
  SELECT BST.N,
         BST.P,
         NodeCTE.[Level] + 1
  FROM BST
    JOIN NodeCTE ON BST.P = NodeCTE.N
)
SELECT CTE1.N AS Node,
       CTE1.[Level]
FROM NodeCTE CTE1
  LEFT JOIN NodeCTE CTE2 ON CTE1.P = CTE2.N

已知需要用STRING_AGG格式化路径，但不清楚如何生成符合要求的中间数据，预期输出格式如下：

|   N   |  TraversalPath |
|-------|----------------|
|1      |8->3->1         |
|3      |8->3            |
|4      |8->3->6->4      |
|6      |8->3->6         |
|7      |8->3->6->7      |
|8      |8               |
|10     |8->10           |
|13     |8->10->14->13   |
|14     |8->10->14       |

解决方案 #

不需要额外通过STRING_AGG聚合历史节点，直接在递归CTE中维护路径字段即可，实现代码更简洁高效，和预期输出完全匹配：

WITH NodeCTE AS
(
  -- 递归锚点：取根节点，路径为根节点本身的值
  SELECT 
    N,
    P,
    CAST(N AS VARCHAR(MAX)) AS TraversalPath
  FROM BST
  WHERE P IS NULL
  
  UNION ALL
  
  -- 递归逻辑：关联父节点，将当前节点值拼接到父节点路径末尾
  SELECT 
    b.N,
    b.P,
    CONCAT(c.TraversalPath, '->', b.N) AS TraversalPath
  FROM BST b
  INNER JOIN NodeCTE c ON b.P = c.N
)
SELECT 
  N,
  TraversalPath
FROM NodeCTE
ORDER BY N

内容的提问来源于stack exchange，提问作者Teja Goud Kandula