6

[上一个问题]

我正在尝试向应用程序添加类似 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 树结构。本质上，我的目标是这个问题和这个关于最终输出 (HTML) 的问题，但我真的不想求助于递归 SQL 语句，因为我已经有了这些信息。我认为某种递归是必要的，因为我希望最终得到与此类似的结构：

[
  {
    'id': 1,
    ...
    'children': [
                  {
                    'id': 2,
                    ...
                    'children': [ ... ]
                  }
                ]
  },
  {
    'id': 7,
    ...
    'children': [
                {
                  'id': 8,
                  ...
                }
              ]
  }
]

基本上是一个嵌套的字典列表，所以我可以使用Jinja 的递归循环遍历它们。有人有想法吗？

谢谢！

编辑 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))

comment_set这并不理想，因为它会在每次调用时迭代create_tree()，即集合中的每条记录。然而，这是我目前拥有的最好的。有人有什么想法吗？

4

2 回答 2

5

你不需要递归，你只需要能够通过引用来处理节点对象。

这是一个在线性时间内创建嵌套数据结构的代码示例。将其视为伪代码，因为我尚未对此进行测试，而且我还不精通 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 帖子中发布的示例，将数据库结果转换为数组：

于 2013-04-19T01:16:44.450 回答
0

你可以做一些小的改变来帮助你改进你的代码::

comment_set = ... order by parent_id asc

def create_tree(parent, list):
    parent['children'] = []
    for record in comment_set:
        if record['parent_id'] == parent['id']:
            parent['children'].append(create_tree(record, list[1:]))
    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, comment_set))
于 2014-05-27T14:08:00.160 回答