Python рекурсия для сортировки списка кортежей в древовидную структуру

Question

Я новичок в кодировании и застрял, пытаясь рекурсивно отсортировать список кортежей. Вот мой код:

# table consists on [(code, parent), (code, parent), ...]
table = [('1', ''),
      ('1.1', '1'),
      ('2', ''),
      ('2.1','2'),
      ('2.1.1','2.1'),
      ('3',''),
      ('3.1','3'),
      ('4',''),
      ('4.1','4'),
      ('4.1.1','4.1'),
      ('4.1.2','4.1')]
content = {}
def rec(table, parent=None):
    while True:
        try:
            _code = table[0][0]
            _parent = table [0][1]
            if _parent == '':
                content[_code] = _parent
                return rec(table[1:])
            else:
                if _parent in content:
                    if content[_parent] == '':
                        content[_parent] = table[0]
                    else:
                        content[_parent] = content[_parent], table[0]
                    return rec(table[1:], parent=_parent)
                else:
                    content[_parent] = table[0]
                    return rec(table[1:], parent=_parent)           
        except IndexError:
            break
    return content

print(rec(table))

Вывод, который я получаю:

{'1': ('1.1', '1'), '2': ('2.1', '2'), '2.1': ('2.1.1', '2.1'), '3':('3.1', '3'), '4': ('4.1', '4'), '4.1': (('4.1.1', '4.1'), ('4.1.2','4.1'))}

Но желаемый вывод будет:

{'1': ('1.1', '1'), '2': ('2.1', '2'), {'2.1': ('2.1.1', '2.1')}, '3': ('3.1','3'), '4': ('4.1', '4'), {'4.1': ('4.1.1', '4.1'), ('4.1.2', '4.1')}

Мне нужно что-то вроде :

{'node_id': '1', 'name':'somename', 'children': [{'node_id': '1.1' ,'name':'somename', 'children': [{'node_id': '1.1.1', 'name':'somename', 'children': [{'node_id': '1.1.1.1', 'name':'somename', 'children': []}]}, {'node_id': '1.1.2', 'name':'somename', 'children': []}, {'node_id': '1.1.3', 'name':'somename', 'children': []}]}, {'node_id': '1.2', 'name':'somename', 'children': []}]}

Есть мысли о том, как достичь того, к чему я стремлюсь?

Answer 1

Чтобы ваш вывод был деревом вложенных словарей, он должен иметь регулярную структуру, в которой каждый узел представляет собой словарь со значениями, представляющими словарь дочерних элементов вплоть до конечных узлов, в которых был бы пустой словарь для их дочерних элементов.

Вот простой l oop, который будет строить дерево:

table = [('1', ''),
      ('1.1', '1'),
      ('2', ''),
      ('2.1','2'),
      ('2.1.1','2.1'),
      ('3',''),
      ('3.1','3'),
      ('4',''),
      ('4.1','4'),
      ('4.1.1','4.1'),
      ('4.1.2','4.1')]

tree = { node:dict() for link in table for node in link }
for child,parent in table:
    tree[parent].update({child:tree[child]})

output:

print(tree[""])  # "" is te root

{
 '1': { '1.1': {}},
 '2': {
        '2.1': { '2.1.1': {}}
      },
 '3': { '3.1': {}},
 '4': {
        '4.1': {
                 '4.1.1': {},
                 '4.1.2': {}
               }
      }
}

В качестве дополнительного преимущества эта структура дает индекс для всех узлов дерева

Со словарями атрибутов (одним из которых является список дочерних элементов) можно использовать тот же подход:

tree = { node:{"id":node,"children":[]} for link in table for node in link }
for child,parent in table:
    tree[parent]["children"].append(tree[child])

выходные данные:

print(tree[""]["children"]) # children of root

[ { 'id': '1',
    'children': [ { 'id': '1.1', 'children': []} ]
  },
  { 'id': '2',
    'children': [
                  { 'id': '2.1',
                    'children': [ {'id': '2.1.1', 'children': []} ]
                  } 
                ]
  },
  { 'id': '3',
    'children': [ { 'id': '3.1','children': []} ]
  },
  { 'id': '4',
    'children': [
                  { 'id': '4.1',
                    'children': [
                                  { 'id': '4.1.1', 'children': []},
                                  { 'id': '4.1.2', 'children': []}
                                ]
                  }
                ]
  }
]

Рекурсивный подход хорош, но он преформируется намного медленнее и не создает индекс для доступа к узлам по их идентификаторам:

def tree(links,node=""):
    return {"id":node, "children":[tree(links,child) for child,parent in links if parent==node] }

root = tree(table)

Answer 2

Вы можете использовать рекурсию:

table = [('1', ''), ('1.1', '1'), ('2', ''), ('2.1', '2'), ('2.1.1', '2.1'), ('3', ''), ('3.1', '3'), ('4', ''), ('4.1', '4'), ('4.1.1', '4.1'), ('4.1.2', '4.1')]
def to_dict(d):
  return {'node_id':d, 'children':[*map(to_dict, [a for a, b in table if b == d])]}

result = [to_dict(a) for a, b in table if not b]

Вывод:

[{'node_id': '1', 'children': [{'node_id': '1.1', 'children': []}]}, {'node_id': '2', 'children': [{'node_id': '2.1', 'children': [{'node_id': '2.1.1', 'children': []}]}]}, {'node_id': '3', 'children': [{'node_id': '3.1', 'children': []}]}, {'node_id': '4', 'children': [{'node_id': '4.1', 'children': [{'node_id': '4.1.1', 'children': []}, {'node_id': '4.1.2', 'children': []}]}]}]

Редактировать: если ваши кортежи в table имеют дополнительную информацию:

table = [('1', '', 'someval0'), ('1.1', '1', 'someval1'), ('2', '', 'someval2'), ('2.1', '2', 'someval3'), ('2.1.1', '2.1', 'someval4'), ('3', '', 'someval5'), ('3.1', '3', 'someval6'), ('4', '', 'someval7'), ('4.1', '4', 'someval8'), ('4.1.1', '4.1', 'someval9'), ('4.1.2', '4.1', 'someval10')]
def to_dict(d):
  return {**(dict(zip(['node_id', 'name'], d))), 'children':[*map(to_dict, [(a, *c) for a, b, *c in table if b == d[0]])]}

result = [to_dict((a, *c)) for a, b, *c in table if not b]

Выход:

[{'node_id': '1', 'name': 'someval0', 'children': [{'node_id': '1.1', 'name': 'someval1', 'children': []}]}, {'node_id': '2', 'name': 'someval2', 'children': [{'node_id': '2.1', 'name': 'someval3', 'children': [{'node_id': '2.1.1', 'name': 'someval4', 'children': []}]}]}, {'node_id': '3', 'name': 'someval5', 'children': [{'node_id': '3.1', 'name': 'someval6', 'children': []}]}, {'node_id': '4', 'name': 'someval7', 'children': [{'node_id': '4.1', 'name': 'someval8', 'children': [{'node_id': '4.1.1', 'name': 'someval9', 'children': []}, {'node_id': '4.1.2', 'name': 'someval10', 'children': []}]}]}]