sql - 返回具有最顶层节点(根)的最低层节点(叶)

Question

我想从层次结构表中获取所有叶子及其根。叶子是最低层节点，根是最顶层节点。

给定一棵树:

A
--B
  --C
  --D
E
--F
--G
  --H

叶子是节点:C, D根是:A、E

该表如下所示(为清楚起见，我将 parent 姓名放在括号中):

Id | Parent | Name
0  | NULL   | A
1  | 0 (A)  | B
2  | 1 (B)  | C
3  | 1 (B)  | D
4  | NULL   | E
5  | 4 (E)  | F
6  | 4 (E)  | G
7  | 6 (G)  | H

我要找的结果是:

Id | Parent | Name
2  | 0 (A)  | C
3  | 0 (A)  | D
5  | 4 (E)  | F
7  | 4 (E)  | H

我已经设置了以下 CTE 查询，它能够找到每片叶子的所有根。

WITH Tree (Id, [Name], Parent) AS
(

      SELECT

            Id, [Name], Parent

      FROM

            dbo.Department

      WHERE 
           --Every leaf node, that is: a node that is never a parent
           Id IN (

            SELECT Id
            FROM Department
            WHERE Id NOT IN (
                SELECT Parent FROM Department
                WHERE Parent IS NOT NULL
            ))


      UNION ALL 

      SELECT

            dept.Id, dept.[Name], dept.Parent

      FROM

            dbo.Department dept

      INNER JOIN Tree ON 

            dept.Id = Tree.Parent

)
SELECT * FROM Tree
WHERE Parent IS NULL

但我不知道如何将叶子 ID 及其根添加到结果中。

Answer 1

有点像

WITH cte(id, name, root) AS
  (SELECT id, name, id FROM department WHERE parent IS NULL
   UNION ALL
   SELECT d.id, d.name, root
   FROM department AS d
   JOIN cte AS c ON d.parent = c.id)
SELECT id, root, name
FROM cte AS c
WHERE NOT EXISTS (SELECT 1 FROM department AS d WHERE c.id = d.parent)
ORDER BY id;

会给你所有的叶子和根:

id          root        name      
----------  ----------  ----------
2           0           C         
3           0           D         
5           4           F         
7           4           H         

db<>fiddle example

---

诀窍是在 cte 中有一个列，它以每个根的 id 开头，并依次传递给每个 child 、孙子等。然后过滤掉非叶行。