如何從一個有序的鄰接表中構建一個遞歸字典樹

Question

我一直想弄明白這一點，並在我的智慧結束。也許我正在爲此而變老。

我想作爲指定here

爲了節省您希望建立對Django的樹胡的load_bulk功能一棵樹，它應該是這樣的：

data = [{'data':{'desc':'1'}}, 
     {'data':{'desc':'2'}, 'children':[ 
      {'data':{'desc':'21'}}, 
      {'data':{'desc':'22'}}, 
      {'data':{'desc':'23'}, 'children':[ 
      {'data':{'desc':'231'}}, 
      ]}, 
      {'data':{'desc':'24'}}, 
     ]}, 
     {'data':{'desc':'3'}}, 
     {'data':{'desc':'4'}, 'children':[ 
      {'data':{'desc':'41'}}, 
     ]}, 
] 

「數據」持有記錄，如果它有孩子，'孩子'是更多的'數據'字典列表（也可以包含一個孩子列表等遞歸）列表

我得到的數據作爲有序列表深度優先，而不是編號）：

如：

[ 
    {'id': 232, 'name': 'jon', 'parent': 'None'} 
    {'id': 3522, 'name': 'dave', 'parent': '232'} 
    {'id': 2277, 'name': 'alice', 'parent': '3522'} 
    {'id': 119, 'name': 'gary', 'parent': '232'} 
    {'id': 888, 'name': 'gunthe', 'parent': '119'} 
    {'id': 750, 'name': 'beavis', 'parent': 'None'} 
    {'id': 555, 'name': 'urte', 'parent': '750'} 
] 

我怎樣才能將其轉化爲一個樹胡兼容的字典，應該是這樣的（錯字的除外）：

[ 
{'data': {'id': 232, 'name': 'jon', 'parent': 'None'}, 
'children': [ 
       {'data': {'id': 3522, 'name': 'dave', 'parent': '232'}, 
       'children': [ 
          {'data': {'id': 2277, 'name': 'alice', 'parent': '3522'}} 
          ] 
       } 
       {'data': {'id': 119, 'name': 'gary', 'parent': '232'}, 
       'children': [ 
          {'id': 888, 'name': 'gunthe', 'parent': '119'} 
          ] 
       } 
      ] 
{'data': {'id': 750, 'name': 'beavis', 'parent': 'None'}, 
'children': [ 
       {'id': 555, 'name': 'urte', 'parent': '750'} 
      ] 
} 

]

我想我需要一些遞歸函數看起來像遞歸結構，但我所有的嘗試都失敗了。我的大腦不會做遞歸很好。

我做了大量的搜索，發現大多數解決方案屬於列表或其他結構，我不能塑造適合。我是一個相對的菜鳥。 ps我有更多的樂趣手動打字的例子比我剩下的一天（除了晚餐時間）。

Answer 1

也許有更好的方式，但在這裏是一個解決辦法：

users = [ 
    { 
     'id': 232, 
     'name': 'jon', 
     'parent': None 
    }, 
    { 
     'id': 3522, 
     'name': 'dave', 
     'parent': 232 
    }, 
    { 
     'id': 2277, 
     'name': 'alice', 
     'parent': 3522 
    }, 
    { 
     'id': 119, 
     'name': 'gary', 
     'parent': 232 
    }, 
    { 
     'id': 888, 
     'name': 'gunthe', 
     'parent': 119 
    }, 
    { 
     'id': 750, 
     'name': 'beavis', 
     'parent': None 
    }, 
    { 
     'id': 555, 
     'name': 'urte', 
     'parent': 750 
    } 
] 

users_map = {} 
for user in users: 
    users_map[user['id']] = user 

users_tree = [] 
for user in users: 
    if user['parent'] is None: 
     users_tree.append(user) 
    else: 
     parent = users_map[user['parent']] 
     if 'childs' not in parent: 
      parent['childs'] = [] 
     parent['childs'].append(user) 

print(users_tree) 

#user as {data: user, childs: []} 

users_map = {} 
for user in users: 
    users_map[user['id']] = {'data': user, 'childs': []} 

users_tree = [] 
for user in users: 
    if user['parent'] is None: 
     users_tree.append(users_map[user['id']]) 
    else: 
     parent = users_map[user['parent']] 
     parent['childs'].append(users_map[user['id']]) 

print(users_tree)