尽管这个问题很久以前就有了答案,但我想提供另一个解决方案,对我来说似乎更加简洁。我主要将其用于将父母和子项列表一起压缩的情况。例如:
parents = [None, 1, 2, 3, 3, 2, 6, 6, 1, 9, 10, 10, 9, 13, 13]
children = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
# {1: {2: {3: {4: {}, 5: {}}, 6: {7: {}, 8: {}}}, 9: {10: {11: {}, 12: {}}, 13: {14: {}, 15: {}}}}}
实现:
def create_tree(node_map, root=None):
""" Given a list of tuples (child, parent) return the nested dictionary representation.
"""
def traverse(parent, node_map, seen):
children = {}
for edge in node_map:
if edge[1] == parent and edge[0] not in seen:
seen.add(edge[0])
children[edge[0]] = traverse(edge[0], node_map, seen)
return children
return traverse(root, node_map, {root})
使用方法:
排除根节点的示例。
我们希望将根节点设置为“a”,但由于根节点应被指定为没有父节点(None
),因此被排除在外。
parents = ["a", "b", "c", "a", "b", "e", "e"]
children = ["b", "c", "d", "e", "f", "g", "h"]
edges = list(zip(children, parents))
test_tree = create_tree(edges, "a")
print(test_tree)
将根节点添加到没有父节点的设计中,将该节点指定为根节点。
parents = [None, "a", "b", "c", "a", "b", "e", "e"]
children = ["a", "b", "c", "d", "e", "f", "g", "h"]
edges = list(zip(children, parents))
test_tree = create_tree(edges, None)
print(test_tree)
多个树可以通过有多个根节点来表示。
parents = [None, "a", "b", "c", None, "b", "e", "e"]
children = ["a", "b", "c", "d", "e", "f", "g", "h"]
edges = list(zip(children, parents))
test_tree = create_tree(edges, None)
print(test_tree)
为了从原始帖子中获得所需的输出,我们需要找到并指定根目录。
edges = [
#first value is child, second is parent
(0, 1),
(1, 3),
(8, 7),
(3, 6),
(4, 3),
(5, 3)
]
roots = {edge[1] for edge in edges} - {edge[0] for edge in edges}
edges += [(root, None) for root in roots]
test_tree = create_tree(edges, None)
print(test_tree)
# result: {6: {3: {1: {0: {}}, 4: {}, 5: {}}}, 7: {8: {}}}
{6: {3: {1: {0: {}}, 4: {}, 5: {}}}, 7: {8: {}}}
吗?你在元组中展示了3有子节点1、5、4,但输出结果似乎让人以为1有子节点5、4、0。 - Matt