如何將元組的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) 

但我失去了深層次，當一個節點既有父母和子女

如何使訂購工作正確？

Answer 1

我建議將樹節點表示爲元組（（id，name），dict_of_children）。

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