def get_children(parent, relations):
children = (r[1] for r in relations if r[0] == parent)
return {c: get_children(c, relations) for c in children}
the_list = [('john','marry'),('mike','john'),('mike','hellen'),('john','elisa')]
parents, children = map(set, zip(*the_list))
the_tree = {p: get_children(p, the_list) for p in (parents - children)}
print(the_tree)
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': {}}}}
data = [('john','marry'),('mike','john'),('mike','hellen'),('john','elisa')]
roots = set()
mapping = {}
for parent,child in data:
childitem = mapping.get(child,None)
if childitem is None:
childitem = {}
mapping[child] = childitem
else:
roots.discard(child)
parentitem = mapping.get(parent,None)
if parentitem is None:
mapping[parent] = {child:childitem}
roots.add(parent)
else:
parentitem[child] = childitem
tree = {id : mapping[id] for id in roots}
print (tree)
假设它行为良好(没有循环、没有重复的名称或一个子对象有多个父对象),您可以简单地使用“有向图”并遍历它。为了找到根,我还使用了一个包含布尔值的字典,该布尔值表示该名称是否有父项:
无论如何都可以选择:
结果:
^{pr2}$记入@WillemVanOnsemRecursively creating a tree hierarchy without using class/object
相关问题 更多 >
编程相关推荐