给定（父，子）的平面列表，创建一个分层字典树

我有一个包含名称的元组的列表。这些名字是父母和孩子的名字，我想用他们的名字创建一个分层的字典树。比如我有以下列表：给定（父，子）的平面列表，创建一个分层字典树

[('john','marry'),('mike','john'),('mike','hellen'),('john','elisa')]

，我想创建这样的：

{ 
    'mike':{ 
     'john':{ 
      'marry':{} 
      'elisa':{} 
     } 
     'hellen':{} 
     } 
}

来源

2017-08-02 Dim_iliop

如果还有一个元素，说'（'elisa'，'mike'）'，应该发生什么？ – MSeifert

你到目前为止尝试过什么？你具体在哪里卡住？ – CoryKramer

我相信这是错误的，因为迈克是约翰和海伦的父亲，约翰是艾丽莎的父亲，这意味着艾莉莎是迈克的孙子，不能是迈克的母亲。 –

假设它的乖巧（无周期，不重名或多个家长一个孩子），你可以简单地使用“有向图”并遍历它。为了找到根（S）我也使用含有一个布尔值，表示是否存在用于名称的任何父的字典：

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': {}}}}

来源

2017-08-02 12:54:36 MSeifert

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)

来源

2017-08-02 13:11:21 frogcoder

替代反正：

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)

结果：

{'mike': 
     { 
     'hellen': {}, 
     'john': { 
        'elisa': {}, 
        'marry': {}}}}

贷给@WillemVanOnsem Recursively creating a tree hierarchy without using class/object

来源

2017-08-02 13:55:38 citizen2077

给定（父，子）的平面列表，创建一个分层字典树

回答

相关问题