从元组列表创建树

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, '...')

任何提示都非常感谢。提前谢谢大家。

Answer 1

Oliver，如果我理解得没错，我觉得你可以选择以下两种方法：

(a) 把数据库里的所有数据取出来，放到一个字典或列表里，然后再构建树；

或者

(b) 在取数据的时候使用一个ORDER BY的命令，这样取出来的数据顺序就和你添加到树里的顺序一致。

如果你的应用程序可能会对树进行修改，然后再把这些修改更新到数据库里，我建议你选择第一种方法。但如果修改总是通过在数据库里插入、更新或删除数据来完成，并且除了这些操作外，你的树是只读的，那么第二种方法会更快，消耗的资源也更少。

Roland

Answer 2

我不太明白你到底想做什么，但如果你有一个节点的列表表示一片森林，难道你不能直接读取这个列表，构建出树的结构，然后按照广度优先遍历的方式把所有树写出来吗？有什么特别的原因不想这样做吗？

Answer 3

Python在排序元组时是从左到右进行的，所以如果你把元组的排序关键字放在第一个位置，然后依次往后排，这样排序会比较高效。

你提到的从元组列表到树的映射不太清楚。请画出来，或者更详细地解释一下。比如，你的例子看起来是这样的：

_{(来源: sabi.net)}

如果你有两个没有父节点的节点，那更像是一片森林，而不是一棵树。你想用这棵树表示什么呢？在这个上下文中，“排序”是什么意思呢？