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

Question

已关闭 。这个问题需要更加集中。它当前不接受答案。

想改善这个问题吗？ 更新问题，使其仅通过编辑此帖子来关注一个问题。

3年前关闭。

改善这个问题

我有一个包含元组的列表，其中包含名称。这些名称是父名称和子名称，我想用它们的名称创建一个分层的字典树。例如，我有以下列表：

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

我想创建这个：

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

Answer 1

假设它的行为良好（没有循环，没有重复的名称或一个孩子有多个父母），您可以简单地使用“有向图”并遍历它。为了找到根，我还使用了一个包含布尔值的字典，该布尔值指示该名称是否存在任何父项：

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