Как создать обход пост-заказа в SQL?

Question

Наличие древовидной структуры в базе данных (id, parentId, order) , где order означает какое-то значение для сортировки для каждого родителя (это означает порядок в родительском списке), как можно построить полный - SQL запрос для обхода этой таблицы в POST-ORDER?

Что такое порядок публикации, описанный в вики, но только для двоичных деревьев - 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 (боже, почему ?!), поэтому эта задача становится невозможно на моем текущем уровне без хранимых процедур.

Answer 1

Вот версия на основе 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

Answer 2

Нашел решение, просто реализовав его как есть:

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.