如何从元组列表构建符合层级关系的多级字典树？

给定表示节点关系的元组列表：

key_value = [('A', 'B'), ('B', 'C'), ('C', 'E'), ('C', 'D'), ('E', 'F')]

需要构建嵌套字典树，满足以下要求：

• 每个元组的第一个元素为父节点，第二个为子节点，结构形如 {"A": {"B": {} ...}}
• 未在其他元组中作为父节点出现的子节点（如D），对应值为空字典{}

预期输出：

dict_tree = {'A': {'B': {'C': {'D': {}, 'E': {'F': {}}}}}}

尝试了以下代码但未得到预期结果：

from collections import defaultdict
dict_tree = defaultdict(dict)
key_value = [('A', 'B'), ('B', 'C'), ('C', 'E'), ('C', 'D'), ('E', 'F')]

for level, value in key_value:
    dict_tree[level][value] = {}

print(dict_tree)

输出结果：

defaultdict(<class 'dict'>, {'A': {'B': {}}, 'B': {'C': {}}, 'C': {'E': {}, 'D': {}}, 'E': {'F': {}}})

你之前的代码问题在于：只是将每个父节点作为独立的顶级键存储，没有将子节点的结构嵌套到父节点的字典中。要构建嵌套树，需要先建立节点间的关联映射，再找到根节点并组装完整结构。

实现代码 #

key_value = [('A', 'B'), ('B', 'C'), ('C', 'E'), ('C', 'D'), ('E', 'F')]

# 1. 构建节点到子节点的映射，同时复用已存在的子节点结构
node_map = {}
children = set()

for parent, child in key_value:
    children.add(child)
    # 初始化父节点的字典（如果不存在）
    if parent not in node_map:
        node_map[parent] = {}
    # 子节点如果是父节点，就挂载它的已有结构；否则用空字典
    node_map[parent][child] = node_map.get(child, {})

# 2. 找到根节点：没有父节点的节点（不在children集合中）
root = next(node for node in node_map if node not in children)

# 3. 生成最终的嵌套字典树
dict_tree = {root: node_map[root]}
print(dict_tree)

输出结果 #

{'A': {'B': {'C': {'E': {'F': {}}, 'D': {}}}}}

代码说明 #

1. 节点映射node_map：遍历所有元组时，会将子节点的结构（如果子节点本身是父节点，就用它已有的子结构）挂载到父节点下，而不是简单创建空字典，这样保证了结构的嵌套性。
2. 根节点查找：根节点是没有被任何节点作为子节点的节点，通过对比node_map的键和children集合就能找到。
3. 组装树结构：以根节点为顶级键，对应的node_map值就是完整的嵌套字典树。

内容的提问来源于stack exchange，提问作者FarahR