我正在尝试向应用程序添加类似 reddit 的评论，因此我决定采用闭包表模式来组织数据库。我的应用程序数据库看起来有点像这样:
帖子
+----+-------+
| id | title |
+----+-------+
| 1 | Hello |
+----+-------+
评论
+----+-----------+---------+------+
| id | parent_id | post_id | text |
+----+-----------+---------+------+
| 1 | NULL | 1 | ... |
| 2 | 1 | 1 | ... |
| 3 | 2 | 1 | ... |
| 4 | 3 | 1 | ... |
| 5 | 3 | 1 | ... |
| 6 | 5 | 1 | ... |
| 7 | NULL | 1 | ... |
| 8 | 7 | 1 | ... |
| 9 | 4 | 1 | ... |
+----+-----------+---------+------+
评论路径
+-----------+----------+-------+
| parent_id | child_id | depth |
+-----------+----------+-------+
| 1 | 1 | 0 |
| 2 | 2 | 0 |
| 1 | 2 | 1 |
| 3 | 3 | 0 |
| 2 | 3 | 1 |
| 1 | 3 | 2 |
| 4 | 4 | 0 |
| 3 | 4 | 1 |
| 2 | 4 | 2 |
| 1 | 4 | 3 |
[...snip...]
现在，我正在运行这个查询:
SELECT c.*, p.*
FROM comments AS c
JOIN comment_paths AS p
ON c.id = p.child_id
WHERE p.parent_id IN
(SELECT c2.id FROM comments AS c2 WHERE c2.parent_id IS NULL AND c2.post_id = 1)
根据他们的 post_id 获取评论列表。返回数据为:
+------+-------------+-----------+--------+-------------+------------+---------+
| c.id | c.parent_id | c.post_id | c.text | p.parent_id | p.child_id | p.depth |
+------+-------------+-----------+--------+-------------+------------+---------+
| 1 | NULL | 1 | ... | 1 | 1 | 0 |
| 2 | 1 | 1 | ... | 1 | 2 | 1 |
| 3 | 2 | 1 | ... | 1 | 3 | 2 |
| 4 | 3 | 1 | ... | 1 | 4 | 3 |
| 5 | 3 | 1 | ... | 1 | 5 | 3 |
| 6 | 5 | 1 | ... | 1 | 6 | 4 |
| 9 | 4 | 1 | ... | 1 | 9 | 4 |
| 7 | NULL | 1 | ... | 7 | 7 | 0 |
| 8 | 7 | 1 | ... | 7 | 8 | 1 |
+------+-------------+-----------+--------+-------------+------------+---------+
这代表树:
[1]
|[2]
| |[3]
| |[4]
| | |[9]
| [5]
| |[6]
[7]
|[8]
但是，我正在努力将返回的数据转换为 Python 树结构。本质上，我的目标是 this question和 this question就最终输出 (HTML) 而言，但我真的不想求助于递归 SQL 语句，因为我已经掌握了这些信息。我认为某种递归是必要的，因为我希望最终得到类似于这样的结构:
[
{
'id': 1,
...
'children': [
{
'id': 2,
...
'children': [ ... ]
}
]
},
{
'id': 7,
...
'children': [
{
'id': 8,
...
}
]
}
]
基本上是一个嵌套的字典列表，所以我可以使用 Jinja's recursive loop 遍历它们.有人有想法吗？
谢谢!
编辑 2013-04-17
四处乱逛，我有一个“有效”的解决方案，尽管它进行了很多次迭代，所以我不想将其标记为该问题的答案。我使用的解决方案是:
comment_set = ... # previous query to grab data set
def create_tree(parent):
parent['children'] = []
for record in comment_set:
if record['parent_id'] == parent['id']:
parent['children'].append(create_tree(record))
return parent
comment_tree = []
for record in comment_set:
if record['parent_id'] is None: # if this is the start of a tree
comment_tree.append(create_tree(record))
这并不理想，因为每次调用 create_tree() 时它都会遍历 comment_set，这是集合中的每条记录。但是，这是我现在拥有的最好的。有人有什么想法吗？
最佳答案
你不需要递归，你只需要能够通过引用处理节点对象。
这是一个在线性时间内创建嵌套数据结构的代码示例。将其视为伪代码，因为我还没有对此进行测试，而且我对 python 还不是很流利。
我使用两个 for 循环的原因是，否则我们将不得不假设树顶部的节点在树深处的节点之前被处理。对于如下所示的两个循环，不需要这样的假设。
for record in comment_set:
nodes[record['id']] = record
for record in comment_set:
if record['parent_id'] in nodes:
nodes[record['parent_id']]['children'].append(record)
else
top = record;
return top
在该循环结束时:
nodes将是层次结构中所有节点的一维字典。- 每个节点都有自己的直接子节点列表。
top应该是唯一没有父节点的节点(即根节点)。
这类似于我在过去的 SO 帖子 Turn database result into array 中发布的示例:
关于python - 从闭包表 SELECT 语句渲染树？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/16069840/