python - 在python中从嵌套字典创建层次树

我有一个大的RDF文件，其中包含大约600,000条Wikidata分类法记录。在此文件中，我仅对subclassOf关系（谓词）感兴趣，因此，我忽略了仅保留“ subclassOf”语句的所有其他语句。该语句就像：
a is a subclassOf b，
b is a subclassOf c
这样，c是b的父级，而b是a的父级。而且任何父母都可以有很多孩子。我想使用此分类法构建层次树。
 我检查了这个线程，它几乎解决了我的问题。
Recursively creating a tree hierarchy without using class/object
但是，有了这个，我在字典中得到了树，我想将其转换为树数据结构。以下是我尝试的方法：

data = [['a','x'], ['b','x'], ['c','x'], ['x','y'], ['t','y'], ['y','p'], ['p','q']]

roots = set()
mapping = {}
for child,parent 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

for root in roots:
    print(mapping[root])

tree = { id : mapping[id] for id in roots }
print(tree)

树的输出如下所示：

{'q': {'p': {'y': {'t': {}, 'x': {'c': {}, 'b': {}, 'a': {}}}}}}

我想将此字典转换为树。所以例如当我说print（mapping ['y']）时，它应该给我Node y即

q
├── p
    └── y

当前，如果我说mapping ['y']，它给我的根是y的子树。我认为对此有一些简单的解决方案，但我无法理解。我也找到了此链接https://gist.github.com/hrldcpr/2012250，可将字典转换为树，但不确定在我的情况下如何使用它。替代地，如果有人知道根据我上面给出的RDF数据直接构建一棵树，那么将是非常受欢迎的。 python的anytree API可能会解决我的问题。

最佳答案

如果您不介意额外的O（N）空间，则可以保留一个parents词典，为每个关键子级存储值父级。并将其填充在主for循环中。

现在，找到所有祖先非常容易。递归地找到父级的所有祖先，并将当前节点附加到该结果中。

data = [['a','x'], ['b','x'], ['c','x'], ['x','y'], ['t','y'], ['y','p'], ['p','q']]
parents = {} #to store parents
roots = set()
mapping = {}
for child,parent in data:
    parents[child] = parent #populate parents
    childitem = mapping.get(child,None)
    ................................

def ancestors(node): #the ancestor-finding function
    if not node: return []
    return ancestors(parents.get(node))+[node]

def first_k_ancestor(node,k=5):
    ances = ancestors(node)
    ances.reverse()
    return ances[:k]


print(ancestors('a'))

打印：

['q', 'p', 'y']