题
我有ATTRS元素的列表:父母,水平,is_leaf_node,is_root_node,is_child_node
。我想转换此列表层次字典。 输出字典的示例:
{
'Technology':
{
'Gadgets':{},
'Gaming':{},
'Programming':
{
'Python':{},
'PHP':{},
'Ruby':{},
'C++':{}
},
'Enterprise':{},
'Mac':{},
'Mobile':{},
'Seo':{},
'Ui':{},
'Virtual Worlds':{},
'Windows':{},
},
'News':{
'Blogging':{},
'Economics':{},
'Journalism':{},
'Politics':{},
'News':{}
},}
我不知道算法。怎么做?
解决方案
下面是一个不太复杂,递归版本等中描述CHMOD 700。完全未测试当然:
def build_tree(nodes):
# create empty tree to fill
tree = {}
# fill in tree starting with roots (those with no parent)
build_tree_recursive(tree, None, nodes)
return tree
def build_tree_recursive(tree, parent, nodes):
# find children
children = [n for n in nodes if n.parent == parent]
# build a subtree for each child
for child in children:
# start new subtree
tree[child.name] = {}
# call recursively to build a subtree for current node
build_tree_recursive(tree[child.name], child, nodes)
其他提示
没有父母的一切都是你的顶层,所以首先使这些类型的字典。又做了第二次通过您的数组在这个顶层找到与父母的一切,等...它可以写成一个循环或递归函数。你真的不需要任何提供信息的除了“父”。
这听起来像你基本上想要做的是拓扑排序变体。造成这种情况的最常见的算法是源去除算法。伪代码会是这个样子:
import copy
def TopSort(elems): #elems is an unsorted list of elements.
unsorted = set(elems)
output_dict = {}
for item in elems:
if item.is_root():
output_dict[item.name] = {}
unsorted.remove(item)
FindChildren(unsorted, item.name, output_dict[item.name])
return output_dict
def FindChildren(unsorted, name, curr_dict):
for item in unsorted:
if item.parent == name:
curr_dict[item.name] = {}
#NOTE: the next line won't work in Python. You
#can't modify a set while iterating over it.
unsorted.remove(item)
FindChildren(unsorted, item.name, curr_dict[item.name])
这显然是在几个地方(至少实际Python代码等)来划分。然而,希望的,这将使你的算法如何工作的想法。请注意,如果有一个在你的项目(比如一个项目具有项目B作为父母,而项B项为父母)一个周期,这将可怕的失败。但是,那将可能是不可能在你想无论如何做的格式来表示。
像这样简单的可能工作:
def build_tree(category_data):
top_level_map = {}
cat_map = {}
for cat_name, parent, depth in cat_data:
cat_map.setdefault(parent, {})
cat_map.setdefault(cat_name, {})
cat_map[parent][cat_name] = cat_map[cat_name]
if depth == 0:
top_level_map[cat_name] = cat_map[cat_name]
return top_level_map
一个很好的递归方式来做到这一点:
def build_tree(elems):
elem_with_children = {}
def _build_children_sub_tree(parent):
cur_dict = {
'id': parent,
# put whatever attributes here
}
if parent in elem_with_children.keys():
cur_dict["children"] = [_build_children_sub_tree(cid) for cid in elem_with_children[parent]]
return cur_dict
for item in elems:
cid = item['id']
pid = item['parent']
elem_with_children.setdefault(pid, []).append(cid)
res = _build_children_sub_tree(-1) # -1 is your root
return res
不隶属于 StackOverflow