尝试在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

你的例子和给出的数据不太一致，但这应该是你想要的结果。

这里并不是在使用递归，因为递归在这种情况下没有意义：输入的数据没有递归的结构（我们正是要创建这样的结构），所以你能写的递归其实就是一个循环……在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"]

Answer 2

如果我没理解错的话，父级ID为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)