数据库中有一个树结构(id,parentId,order),其中order表示每个父级要排序的某个值(表示父级列表中的顺序),如何构建完整的SQL查询以在POST中遍历该表-订购?
维基百科上描述了什么是后序,尽管仅适用于二叉树 - https://en.wikipedia.org/wiki/Tree_traversal
并非所有这些都适用于自定义树(例如 IN-ORDER),但 POST-ORDER 实际上适用:
A
/ \
B C
/|\
D E F
输出将是:
B D E F C A
SQL数据表中同样:
|Id |ParentId | Order
|___|_________|______
|A |null |0
|B |A |0
|C |A |1
|D |C |0
|E |C |1
|F |C |2
我已经为此苦苦挣扎了很长一段时间,但看起来 CTE 不允许内部 ORDER BY 子句(天啊,为什么?!),所以在我目前的水平上,如果没有存储过程,这项任务就变得不可能了。
这里是一个基于 CTE 的版本,更多的是作为概念证明而不是可用的答案。它使用
STRING_AGG
按顺序连接每个节点的子节点,然后递归地将每个节点替换为其子节点以构建输出字符串 - 这意味着它在节点键是彼此的子字符串的情况下不起作用。
DECLARE @t TABLE
(id CHAR(1) NOT NULL PRIMARY KEY,
parentid CHAR(1) NULL,
roworder TINYINT NOT NULL
)
INSERT @t (id, parentid, roworder)
VALUES('A', NULL, 0),
('B','A',0),
('C','A',1),
('D','C',0),
('E','C',1),
('F','C',2),
('G','E',0),-- two extra nodes to prove that this isn't a one-off
('H','E',1)
;WITH aggCTE
AS
(
SELECT parentid, STRING_AGG(CONVERT(VARCHAR(MAX), id), ' ') WITHIN GROUP (ORDER BY Roworder) AS children
FROM @t
GROUP BY parentid
)
,recCTE
AS
(
SELECT a.parentid,
a.children,
CAST(ISNULL(a.parentid,'') AS VARCHAR(MAX)) AS processed, --to prevent loops
0 AS seq, --to pick the right output row
a.children AS firstnode --to disambiguate if the data contains multiple trees
FROM aggCTE AS a
WHERE a.parentid IS NULL
UNION ALL
SELECT a.parentid,
REPLACE(a.children, b.parentid, CONCAT(b.children, ' ', b.parentid)) AS children,
CONCAT(a.processed, b.parentid) AS processed,
a.seq + 1 AS seq,
a.firstnode
FROM recCTE AS a
JOIN aggCTE AS b
ON CHARINDEX(b.parentid, a.children) > 0
AND CHARINDEX(b.parentid, a.processed) = 0
)
,rnCTE
AS
(
SELECT children,
ROW_NUMBER() OVER (PARTITION BY firstnode ORDER BY seq DESC) AS rn
FROM recCTE
)
SELECT children AS post_order_traversal
FROM rnCTE
WHERE rn = 1
通过简单地按原样实现找到解决方案:
If(OBJECT_ID('tempdb..#result') Is Not Null) Drop Table #result;
If(OBJECT_ID('tempdb..#stack') Is Not Null) Drop Table #stack;
create table #result (id int not null identity primary key, [value] bigint null);
create table #stack (id int not null identity primary key, [value] bigint null);
INSERT INTO #stack values(null) --inserting root identifiers here
WHILE EXISTS (SELECT * FROM #stack)
BEGIN
declare @stack_id int, @stack_value bigint
select top 1 @stack_id=id, @stack_value=value from #stack order by id desc
delete from #stack where id=@stack_id
INSERT INTO #stack
-- here comes our query, which should fetch children of specified id and order it
select tos.id
from inputTable as t
where (ISNULL(@stack_value, 0) = 0 AND t.ParentId IS NULL) OR (ISNULL(@stack_value, 0) != 0 AND t.ParentId = @stack_value)
order by t.[order] asc
insert into #result values(@stack_value)
END
select [value] from #result order by id desc
If(OBJECT_ID('tempdb..#result') Is Not Null) Drop Table #result;
If(OBJECT_ID('tempdb..#stack') Is Not Null) Drop Table #stack;
到目前为止,使用 CTE 似乎是不可能的。
这是使用标准 SQL SELECT 语句的示例解决方案。
DROP TABLE tab1 PURGE;
CREATE TABLE tab1
(
id NUMBER,
parent_id NUMBER,
CONSTRAINT tab1_pk PRIMARY KEY (id),
CONSTRAINT tab1_tab1_fk FOREIGN KEY (parent_id) REFERENCES tab1 (id)
);
CREATE INDEX tab1_parent_id_idx
ON tab1 (parent_id);
INSERT INTO tab1
VALUES (1, NULL);
INSERT INTO tab1
VALUES (2, 1);
INSERT INTO tab1
VALUES (3, 2);
INSERT INTO tab1
VALUES (4, 2);
INSERT INTO tab1
VALUES (5, 4);
INSERT INTO tab1
VALUES (6, 4);
INSERT INTO tab1
VALUES (7, 1);
INSERT INTO tab1
VALUES (8, 7);
INSERT INTO tab1
VALUES (9, 1);
INSERT INTO tab1
VALUES (10, 9);
INSERT INTO tab1
VALUES (11, 10);
INSERT INTO tab1
VALUES (12, 9);
INSERT INTO tab1
VALUES (13, 10);
INSERT INTO tab1
VALUES (14, 10);
INSERT INTO tab1
VALUES (15, 6);
INSERT INTO tab1
VALUES (16, 6);
COMMIT;
-- 后序树遍历(左子树 - 右子树 - 父树)SELECT语句 -- 使用 Oracle 风格的“connect by”后序 -- '/99999999' 是树中的最大节点数
SELECT b.id, b.parent_id, b.pth
FROM ( SELECT a.id,
a.parent_id,
LEVEL lvl,
CONNECT_BY_ISLEAF lf,
SYS_CONNECT_BY_PATH (id, '/') pth,
CASE WHEN CONNECT_BY_ISLEAF = 0 THEN SYS_CONNECT_BY_PATH (id, '/') || '/99999999' ELSE SYS_CONNECT_BY_PATH (id, '/') END postorder -- 9999999 is max number of nodes in tree
FROM tab1 a
START WITH parent_id IS NULL
CONNECT BY PRIOR id = parent_id
ORDER SIBLINGS BY id) b
ORDER BY postorder;
-- 后序树遍历(左子树 - 右子树 - 父树)SELECT语句 -- 使用递归WITH语句
SELECT b.id,
b.parent_id,
b.lf,
pth
FROM (WITH
t1 (id,
parent_id,
lvl,
root_id,
pth)
AS
( -- Anchor member.
SELECT id,
parent_id,
1 AS lvl,
id AS root_id,
TO_CHAR (id) AS pth
FROM tab1
WHERE parent_id IS NULL
UNION ALL
-- Recursive member.
SELECT t2.id,
t2.parent_id,
lvl + 1,
t1.root_id,
t1.pth || '/' || t2.id AS pth
FROM tab1 t2, t1
WHERE t2.parent_id = t1.id)
SEARCH DEPTH FIRST BY id SET order1
SELECT id,
parent_id,
lvl,
CASE WHEN LEAD (lvl, 1, 1) OVER (ORDER BY order1) <= lvl THEN 1 ELSE 0 END lf,
pth,
CASE
WHEN CASE WHEN LEAD (lvl, 1, 1) OVER (ORDER BY order1) <= lvl THEN 1 ELSE 0 END = 0 THEN pth || '/99999999'
ELSE pth
END postorder
FROM t1
ORDER BY order1) b
ORDER BY b.postorder;