試圖拿出一個遞歸函數來展開樹在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

如果我理解正確，那麼其父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) 

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"]