python 将树列表转换为层次结构字典
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/757244/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Converting tree list to hierarchy dict
提问by Alexandr
I have a list of elements with attrs: parent, level, is_leaf_node, is_root_node, is_child_node.
我有一个带有属性的元素列表：parent、level、is_leaf_node、is_root_node、is_child_node。
I want to convert this list to hierarchy dict. Example of output dict:
我想将此列表转换为层次结构字典。输出字典示例：
{
'Technology':
{
'Gadgets':{},
'Gaming':{},
'Programming':
{
'Python':{},
'PHP':{},
'Ruby':{},
'C++':{}
},
'Enterprise':{},
'Mac':{},
'Mobile':{},
'Seo':{},
'Ui':{},
'Virtual Worlds':{},
'Windows':{},
},
'News':{
'Blogging':{},
'Economics':{},
'Journalism':{},
'Politics':{},
'News':{}
},}
I don't know algorithm. How to do it?
我不懂算法。怎么做？
回答by Matt S.
Here's a less sophisticated, recursive version like chmod 700 described. Completely untested of course:
这是一个不太复杂的递归版本，如描述的 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)
回答by Trey Stout
Everything without a parent is your top level, so make those dicts first. Then do a second pass through your array to find everything with a parent at that top level, etc... It could be written as a loop or a recursive function. You really don't need any of the provided info besides "parent".
没有父母的一切都是你的顶级，所以先做这些dicts。然后再次遍历您的数组以查找具有该顶级父级的所有内容，等等......它可以写为循环或递归函数。除了“父母”之外，您真的不需要任何提供的信息。
回答by Jason Baker
It sounds like what you're basically wanting to do is a variant of topological sorting. The most common algorithm for this is the source removal algorithm. The pseudocode would look something like this:
听起来您基本上想要做的是拓扑排序的变体。最常见的算法是源删除算法。伪代码如下所示：
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])
This obviously is broken in a couple of places (at least as actual Python code). However, hopefullythat will give you an idea of how the algorithm will work. Note that this will fail horribly if there's a cycle in the items you have (say item a has item b as a parent while item b has item a as a parent). But then that would probably be impossible to represent in the format you're wanting to do anyway.
这显然在几个地方被破坏了（至少作为实际的 Python 代码）。但是，希望这能让您了解该算法的工作原理。请注意，如果您拥有的项目中有一个循环，这将非常失败（假设项目 a 将项目 b 作为父项，而项目 b 将项目 a 作为父项）。但是，无论如何，这可能无法以您想要的格式表示。
回答by rhettg
Something simple like this might work:
像这样简单的事情可能会奏效：
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
回答by DanielM
a nice recursive way to do it:
一个很好的递归方式来做到这一点：
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
