给定一个(父,子)的平面列表,创建一个分层的字典树 [英] Given a flat list of (parent,child), create a hierarchical dictionary tree
本文介绍了给定一个(父,子)的平面列表,创建一个分层的字典树的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我有一个包含元组的列表,其中包含名称.这些名称是父名称和子名称,我想用它们的名称创建一个分层的字典树. 例如,我有以下列表:
I have a list with tuples that containing names. These names are parent and child names and I want to create a hierarchical dictionary tree with their names. For example I have the following list:
[('john','marry'),('mike','john'),('mike','hellen'),('john','elisa')]
我想创建这个:
{
'mike':{
'john':{
'marry':{}
'elisa':{}
}
'hellen':{}
}
}
推荐答案
假设它行为良好(没有循环,没有重复的名称,也没有一个孩子的多个父母),您可以简单地使用有向图"进行遍历.为了找到根,我还使用了一个包含布尔值的字典,该布尔值指示名称是否存在任何父项:
Assuming it's well-behaved (no cycles, no duplicate names or multiple parents for one child) you could simply use a "directed graph" and traverse it. To find the root(s) I also used a dictionary containing a boolean that indicates if there is any parent for the name:
lst = [('john','marry'), ('mike','john'), ('mike','hellen'), ('john','elisa')]
# Build a directed graph and a list of all names that have no parent
graph = {name: set() for tup in lst for name in tup}
has_parent = {name: False for tup in lst for name in tup}
for parent, child in lst:
graph[parent].add(child)
has_parent[child] = True
# All names that have absolutely no parent:
roots = [name for name, parents in has_parent.items() if not parents]
# traversal of the graph (doesn't care about duplicates and cycles)
def traverse(hierarchy, graph, names):
for name in names:
hierarchy[name] = traverse({}, graph, graph[name])
return hierarchy
traverse({}, graph, roots)
# {'mike': {'hellen': {}, 'john': {'elisa': {}, 'marry': {}}}}
这篇关于给定一个(父,子)的平面列表,创建一个分层的字典树的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文