从元组列表创建树形结构

Question

我现在似乎有点糊涂，所以需要在这里问一下。我想要对一个包含元组的列表进行排序，元组看起来像这样：

(id, parent_id, value)

希望翻译成：这意味着将树表示为平铺的树节点列表的列表。

例如，输入如下：

(1, None, '...')
(3, 2', '...')
(2, 1, '...')
(4, 1, '...')
(5, 2, '...')
(6, None, '...')

以后应该这样排序

(1, None, '...')
(2, 1, '...')
(3, 2', '...')
(5, 2, '...')
(4, 1, '...')
(6, None, '...')

任何提示都将不胜感激。提前致谢。

- Oliver Andrich

---

什么样的树？你到目前为止尝试了什么？...为什么不使用现有的实现？ - Joe Phillips

这是什么样的排序方式？它是一个有多个根节点的不平衡树吗？我感到困惑。 - Joe Phillips

基本上，我从数据库中获取这个。什么样的树无法被终止，因为它更加平衡或类似于文件系统树。你所说的当前实现是什么意思？ - Oliver Andrich

这是一个父子关系列表，我想对其进行排序以在网页上显示为树形结构或类似的形式。 - Oliver Andrich

Answer 1

Python对元组进行从左到右的排序，所以如果您将元组排列为第一个排序键是第一个项目，依此类推，它将是相当高效的。

从您描述的内容中，列表元组到树的映射并不清晰。请画出它，或者更详细地解释一下。例如，您的示例似乎是：
_{(来源：sabi.net)} 如果您有两个没有父级的节点，那就更像是森林而不是树了。您试图用树来表示什么？在这种情况下，“已排序”是什么意思？

- Nicholas Riley

---

是的，本质上它是一片树林。列表中的每个元组都是一个项，可以有另一个元组作为其父级。你的图片正确地模拟了这种情况。这类似于一个文件系统视图，这就是我想创建的东西。 - Oliver Andrich

好的，那么你想如何对这个森林进行排序呢？看起来你正在进行一种先序遍历，然后按ID对根节点进行排序？如果是这样，我建议你考虑使用另一种表示方法，使它们更容易排序，例如嵌套字典，其键是节点ID。然后，如果需要，你可以将字典展平为元组列表表示。 - Nicholas Riley

Answer 2

我不确定我完全理解您正在尝试做什么，但如果您有一个节点列表作为森林，难道不能读取它并构建树结构，然后将其写出作为所有树的广度优先遍历？ 有任何特殊原因要避免这样做吗？

- simon

---

不，我想我必须采取这种方法。 我唯一想跳过的情况是，我有一个包含10,000个元组（也称为数据库行）的列表，我将其放入一个基于字典的森林中，然后再次创建元组列表。 - Oliver Andrich

Answer 3

Oliver，如果我理解正确的话，我认为你可以选择以下两种方式： (a) 从数据库中检索所有元组到字典或列表中，然后构建树， 或者 (b) 在检索元组时使用ORDER BY子句，以便它们按照添加到树中的顺序排列。

如果在应用程序中可能对树进行更改，然后传播到数据库中，我会选择a，但如果更改始终作为数据库插入、更新或删除进行，并且除此之外，您的树是只读的，则选项b应该更快并且需要更少的资源。

Roland

- Roland