树的深度优先预排序遍历

Depth-first pre-order traversal of a tree

提问人：Dante 提问时间：10/14/2022 最后编辑：Dante 更新时间：10/21/2022 访问量：104

问：

请看这个闭包表：

祖先 后代 path_length
1 1 0
2 2 0
3 3 0
4 4 0
2 4 1
5 5 0
2 5 1
6 6 0
4 6 1
2 6 2
7 7 0
4 7 1
2 7 2
8 8 0
6 8 1
4 8 2
2 8 3

enter image description here

现在我想要这个顺序：

1
2
4
6
8
7
5
3

请注意，节点的所有祖先可能没有较低的节点编号。SQL查询可能吗？

我的尝试：使用 PostgreSQL 文档第 7.8.2.1 节。搜索顺序，我找到了以下解决方案：

WITH RECURSIVE search_tree(descendant, path) AS (
SELECT descendant, ARRAY[ROW(ct.ancestor, ct.descendant)]
FROM closure_table ct WHERE descendant = 2
UNION ALL
SELECT
ct.descendant, path || ROW(ct.ancestor, ct.descendant)
FROM closure_table ct, search_tree st
WHERE ct.ancestor = st.descendant AND ct.path_length = 1
)
SELECT * FROM search_tree ORDER BY path;

你可以在这里看到。但我不知道它的效率如何。

SQL PostgreSQL 树

评论

0赞 lemon 10/14/2022
是表格式问题，还是您的表有 9 个字段，其中 3 个相同的字段重复了 3 次（在架构级别）？
0赞 Dante 10/14/2022
它只是一个包含三列和 17 行的表。
0赞 lemon 10/14/2022
检查更新表的正确性，并考虑添加有关当前正在使用的 DBMS 和尝试的查询（如果有）的信息。
0赞 Dante 10/14/2022
@lemon 实际上，您的解决方案是正确的。请再次重新发布您的答案。只是不需要按降序排列。
0赞 Ciro Santilli OurBigBook.com 11/9/2023
相关，没有使用递归查询的闭包表：stackoverflow.com/questions/65247873/...

答：

1赞 lemon 10/14/2022 #1

第 1 步：找到树的根

给定您的输入表，您可以通过选择

  • 所有具有“path_length = 0”的祖先（仅选择一次）
  • 在具有“path_length > 0”的后代中找不到（至少从级别 = 1 开始找到的节点）。
SELECT ancestor AS root FROM tab WHERE path_length = 0
EXCEPT
SELECT descendant FROM tab WHERE path_length > 0
根
1
2
3

第 2 步：为您的二叉树实现深度优先搜索。

这可以通过以下方式完成

  • 通过联接上一个表来扫描其“祖先”值仅属于根表的行（以避免重复的“后代”值）
  • 应用深度优先排序。

深度优先排序将根据以下条件进行排序：

  • 祖先至上
  • 以递归（深度优先）方式使用窗口函数中的排名值，每个子项的第一个子项，ROW_NUMBER
  • 当它深入到叶子时，path_length向上上升，当它向上向根部移动时，同样path_length向下，使用结构来处理这两种情况。CASE
WITH roots AS (
    SELECT ancestor AS root FROM tab WHERE path_length = 0
    EXCEPT
    SELECT descendant FROM tab WHERE path_length > 0
), ranked_nodes AS (
    SELECT *, ROW_NUMBER() OVER(PARTITION BY ancestor, path_length
                                ORDER     BY descendant           ) AS rn
    FROM tab
    INNER JOIN roots
            ON tab.ancestor = roots.root
)
SELECT descendant
FROM ranked_nodes
ORDER BY ancestor, 
         rn, 
         CASE WHEN rn = 1 THEN path_length ELSE -path_length END

在此处查看演示。

上面的一个是广义解决方案，但如果您假设预先知道根（1、2 和 3）的值，则可以简化查询，如下所示：

WITH ranked_nodes AS (
    SELECT *, ROW_NUMBER() OVER(PARTITION BY ancestor, path_length
                                ORDER     BY descendant           ) AS rn
    FROM tab
    WHERE ancestor <= 3
)
SELECT descendant
FROM ranked_nodes
ORDER BY ancestor, 
         rn, 
         CASE WHEN rn = 1 THEN path_length ELSE -path_length END

评论

1赞 Dante 10/14/2022
非常感谢。但是在我寻找时，您的查询返回了.1, 8, 6, 4, 2, 7, 5, 31, 2, 4, 6, 8, 7, 5, 3
0赞 lemon 10/14/2022
这不是DFS，我更改的最后一件事是在后代上添加最后，尽管这打破了最后值的顺序。DESC
1赞 lemon 10/14/2022
绝对。它们是 sql 查询中最有效的工具之一。我建议您点击此链接，因为它提供了完整的详细描述，并带有方便的示例>>postgresqltutorial.com/postgresql-window-function。对于官方文档，您可以在此处查看>>postgresql.org/docs/current/tutorial-window.html。
1赞 Dante 10/14/2022
我希望我能做更多的赞成票：-）
1赞 lemon 10/15/2022
没错。在这篇文章的特定情况下，占位符和排序值是相同的，而在这种情况下，你提到的占位符和排序值会有所不同。如果你没有这种排序，你必须事先生成它（除了它们的占位符值），并带有更多的子查询（至少还有一个，我会说）。

上一个：无法从线程类获取 100% 的 CPU 使用率

下一个：命名空间包的注意事项是什么