Python树结构字典创建问题

Question

我创建了一个树数据，例如:

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

这里 parent: 表示父元素，child: 表示子元素。例如:第二个元素 x 将位于 w 下，对于 x 'parent':'w' 并且 child 将 y 为 'child':'z'

现在我想要的数据结构是这样的:

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

                    }                   
                ]
            }
        ]
    }]

我尝试过这段代码:

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

但它正在创建所需的数据树字典直至第一级。我必须进行哪些修改。

Answer 1

这是否符合您的要求？

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)

我不确定您使用 key 属性做什么，但看起来这会生成您想要的树。最后的 json.dumps 只是为了检查。这是我得到的输出:

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

如果您想按key对节点的子节点进行排序，您可以迭代地对树进行排序

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)