python - How to build a recursive dictionary tree from an ordered adjacency list -

python - How to build a recursive dictionary tree from an ordered adjacency list -

i've been trying figure out day , im @ wits end. maybe i'm getting old this.

i'm trying build tree load_bulk feature on django-treebeard specified here

to save looking, should this:

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'}}, ]}, ]

'data' holds record, , if has children, 'children' list of more 'data' dicts (that can contain list of children , on recursively)

i info ordered list (ordered in depth first, not id):

e.g:

[ {'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'} ]

how can transform treebeard compliant dictionary (typo's excepted):

[ {'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'} ] }

]

i guess need kind of recursion function seeing recursive construction attempts have failed. brain doesnt recursion good.

i did lot of searching , found solutions pertaining lists or other structures cant mould fit. i'm relative noob. ps had more fun manually typing out illustration did rest of day (apart dinner time).

maybe there improve ways, here 1 solution:

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 = {} user in users: users_map[user['id']] = user users_tree = [] user in users: if user['parent'] 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 {data: user, childs: []} users_map = {} user in users: users_map[user['id']] = {'data': user, 'childs': []} users_tree = [] user in users: if user['parent'] none: users_tree.append(users_map[user['id']]) else: parent = users_map[user['parent']] parent['childs'].append(users_map[user['id']]) print(users_tree)

python django algorithm recursion dictionary