如何将Python元组列表转换为树形结构？

Question

我有一个类似的元组列表

list_of_tuples = [(number, name, id, parent_id),
     (number, name, id, parent_id),
    ]

我正在尝试将它按顺序结构排列，例如：

{
    parent: [(id, name), (id, name)],
    parent: {parent: [(id, name)]
{

因此，任何节点都可以有父节点和/或子节点。

我尝试过：

tree = defaultdict(lambda: [None, ()])
ancestors = set([item[3] for item in list_of_tuples])

for items in list_of_tuples:
    children_root = {}
    descendants = []
    number, name, id, parent = items
    if parent is None:
        tree[id] = [(id, name)]
    elif parent:
        if parent not in tree.keys():
            node = tree.get(parent)
            node.append((id, name))
        children = (id, name)
        tree[parent].append(children)

如果一个节点同时有父节点和子节点，那么我会丢失深层次的层级关系。

如何使排序正确工作？

- noise

---

如果您按parent_id对节点进行排序，并从叶节点开始向源节点移动，这可能会简化问题。 - Moses Koledoye

为什么不用一个键为id的字典呢？ - stark

你所追求的数据结构有点不太寻常。通常情况下，树节点会包含关于子节点的信息而非父节点信息。另外，在这个树/字典中，哪些信息对特定的节点是相关的呢？是ID？名称？但不包括数字？ - CristiFati

这个数字是用来做什么的？ - gavriel

订购时使用的数字，说实话数字并不是重要的元素。 - noise

Answer 1

我建议将树节点表示为元组((id,名称),子节点字典)。

list_of_tuples = [(1, 'name1', 1, None),
     (2, 'name2', 2, 1),
     (3, 'name3', 3, 1),
     (4, 'name4', 4, 2),
     (5, 'name5', 5, 2),
     (6, 'name5', 6, None),
     (7, 'name5', 7, 6),
    ]

def build_tree(list_of_tuples):
    """
    >>> import pprint
    >>> pprint.pprint(build_tree(list_of_tuples))
    {1: ((1, 'name1'),
         {2: ((2, 'name2'), {4: ((4, 'name4'), {}), 5: ((5, 'name5'), {})}),
          3: ((3, 'name3'), {})}),
     6: ((6, 'name5'), {7: ((7, 'name5'), {})})}
    """
    all_nodes = {n[2]:((n[2], n[1]), {}) for n in list_of_tuples}
    root = {}
    for item in list_of_tuples:
        number, name, id, parent = item
        if parent is not None:
            all_nodes[parent][1][id] = all_nodes[id]
        else:
            root[id] = all_nodes[id]
    return root

- gavriel

---

仅返回最深嵌套的一对，但它可以用于在浅列表或元组中打开嵌套层次结构！很好！ - noise

它只期望一个根节点，但可以修改以适用于多个根节点。 - gavriel

我已经编辑过了，现在它可以接受多个根节点。 - gavriel