CODEWITHSUNDEEP
pythonpython-2.7
curiousguy
curiousguy

Reputation: 3262

Python tree structure dictonary creation issue

i have created a tree data like :

nodeData=    [{'child': 'x', 'parent': '', 'key': '', 'title': 'w'}, 
 {'child': 'y', 'parent': 'w', 'key': '', 'title': 'x'}, 
 {'child': 'z', 'parent': 'x', 'key': '', 'title': 'y'}, 
 {'child': '', 'parent': 'y', 'key': '', 'title': 'z'}, 
 {'child': '', 'parent': 'z', 'key': '1', 'title': 'a'}, 
 {'child': '', 'parent': 'z', 'key': '2', 'title': 'b'}, 
 {'child': '', 'parent': 'z', 'key': '3', 'title': 'c'}, 
 {'child': '', 'parent': 'z', 'key': '4', 'title': 'd'}]

Here parent: means the parent element and child: means the child element. for ex: the second element x will come under w as for x 'parent':'w' and the child will be y as 'child':'z'

Now my desired data structure is like this :

treeData = [        
    {"title": "w", 
        "children": [
            {"title": "x",
                "children": [
                    {"title": "y", 
                        "children":[
                          {"title": "z",
                             "children":[
                               {"title" : "a"},
                               {"title" : "b"},
                               {"title" : "c"},
                               {"title" : "d"}
                            ]
                         }
                      ]

                    }                   
                ]
            }
        ]
    }]

I have tried with this code :

r=0
treeList = []
for key in nodeData:
    innerDict = {}
    innerDict['title']= key['title']
    innerDict['key']= key['key']
    if key['child'] !='':
        childList =[]
        childList.append(nodeData[r+1])
        innerDict['children']=childList

    treeList.append(innerDict)
    r+=1

But it is creating desired data tree dictionary upto 1st level. What modification I have to made.

Upvotes: 1

Views: 95

Answers (1)

bigblind
bigblind

Reputation: 12867

Does this do anything like what you want to do?

nodes =    [{'child': 'x', 'parent': '', 'key': '', 'title': 'w'}, 
 {'child': 'y', 'parent': 'w', 'key': '', 'title': 'x'}, 
 {'child': 'z', 'parent': 'x', 'key': '', 'title': 'y'}, 
 {'child': '', 'parent': 'y', 'key': '', 'title': 'z'}, 
 {'child': '', 'parent': 'z', 'key': '1', 'title': 'a'}, 
 {'child': '', 'parent': 'z', 'key': '2', 'title': 'b'}, 
 {'child': '', 'parent': 'z', 'key': '3', 'title': 'c'}, 
 {'child': '', 'parent': 'z', 'key': '4', 'title': 'd'}]


treeData = []

def insert_in_tree(node, parent, tree=None):
    if tree == None:
        tree = treeData

    for subnode in tree:
        if not 'children' in subnode:
            subnode['children'] = []
        elif insert_in_tree(node, parent, subnode['children']):
            return True

        if subnode['title'] == parent:
            subnode['children'].append(node)
            return True
    return False

for node in nodes:
    parent = node['parent']
    del node['parent']
    del node['child']
    if parent == '':
        treeData.append(node)
    else:
        result = insert_in_tree(node, parent)
        if not result:
            insert_in_tree(node, parent, nodes)

import json
print json.dumps(treeData, indent=4)

I'm not sure what you're using the keyproperty for, but it looks like this makes the tree you want. The json.dumps at the end was just to check. Here's the output I got:

[
    {
        "title": "w", 
        "key": "", 
        "children": [
            {
                "title": "x", 
                "key": "", 
                "children": [
                    {
                        "title": "y", 
                        "key": "", 
                        "children": [
                            {
                                "title": "z", 
                                "key": "", 
                                "children": [
                                    {
                                        "title": "a", 
                                        "key": "1", 
                                        "children": []
                                    }, 
                                    {
                                        "title": "b", 
                                        "key": "2", 
                                        "children": []
                                    }, 
                                    {
                                        "title": "c", 
                                        "key": "3", 
                                        "children": []
                                    }, 
                                    {
                                        "title": "d", 
                                        "key": "4"
                                    }
                                ]
                            }
                        ]
                    }
                ]
            }
        ]
    }
]

in case you want to sort the children of a node by key you can iteratively sort the tree

def sort_tree(tree):
    for node in tree:
        node["children] = sort_tree(node)
    return sorted(tree, key=lambda x:x['key'])

treeData = sort_tree(treeData)

Upvotes: 2

Related Questions