Попытка придумать рекурсивную функцию для расширения дерева в Python

Question

У меня есть таблица, которая выглядит так:

id  | parentid | name
---------------------
 1  |    0     | parent1
---------------------
 2  |    0     | parent2
---------------------
 3  |    1     | child1
---------------------
 4  |    3     | subchild1

Сейчас я пытаюсь найти эффективный способ взять эти данные базы данных и создать словарь Python.

В принципе, я хочу иметь возможность:

tree = expand(Session.query(mytable).all())
print tree['parent2']['child2']

# result would be 'subchild1'

Я совершенно не понимаю, как это сделать ... Я возился со следующей функцией, но не могу заставить ее работать. Любая помощь будет оценена.

def expand(tree):

   parents = [i for i in tree if i.parentid == 0]

   for parent in parents:
      children = expand(parent)

Answer 1

Если я правильно понимаю, элемент, для которого родительский идентификатор равен 0, является корневым или первым уровнем?

Если так, ваш метод должен выглядеть следующим образом:

def expand(tree, id):
    expanded_tree = {}

    parents = [i for i in tree if i.parentid == id]

    for parent in parents:
        expanded_tree[parent.name] = expand(tree, parent.id)

    return expanded_tree

и вы начнете так:

tree = expand(Session.query(mytable).all(), 0)

Answer 2

Ваш пример не соответствует приведенным данным, но это должно быть тем, что вы хотите.

Это не рекурсивно, потому что рекурсия здесь не имеет смысла: входные данные не имеют рекурсивной структуры (это то, что мы создаем), поэтому все, что вы можете написать как рекурсию, это цикл ... и это довольно бессмысленно что делать в Python.

data = [ (1,0,"parent1"), (2,0,"parent2"), (3,1,"child1"), (4,3,"child2")]

# first, you have to sort this by the parentid
# this way the parents are added before their children
data.sort(key=lambda x: x[1])

def make_tree( data ):
    treemap = {} # for each id, give the branch to append to
    trees = {}
    for id,parent,name in data:
        # {} is always a new branch
        if parent == 0: # roots
            # root elements are added directly
            trees[name] = treemap[id] = {}
        else:
            # we add to parents by looking them up in `treemap`
            treemap[parent][name] = treemap[id] = {}

    return trees

tree = make_tree( data )
print tree['parent1']['child1'].keys() ## prints all children: ["child2"]