python - 具有动态深度和仅叶子数据的树结构

Question

我有以下层次结构:

- A
    - X : [1, 2, 3]
    - Y : [4, 5]
    - Z : [10, 11]
- B
    - X : [6, 7]
    - Y : [8]

我想要的是以下查询给出以下结果:

get(A) ==> [1,2,3,4,5,10,11]
get(A,Y) ==> [4,5]
get(B) ==> [6,7,8]
get(B,X) ==> [6,7]

到目前为止，这似乎很容易。我可以通过使用一个 Dictionary> 来实现这一点，它可以是 Python 中的 defaultdict(lambda : defaultdict(list)) 。 但是，如果我需要使其更通用并具有另一个级别或另外 2 个级别怎么办？ 类似于:

- A
    - X
        - i  : [1]
        - ii : [2,3]
    - Y
        - i  : [4, 5]
    - Z
        - ii : [10, 11]
- B
    - X
        - ii  : [6]
        - iii : [7]
    - Y
        - i   : [8]

在此示例中，第一个层次结构是第二个层次结构的“投影”，其中最后一个级别合并到父级中。因此，第一个层次结构的所有查询都应给出相同的结果。

新级别的一些示例查询:

get(B, X, ii) ==> [6]
get(B,X) ==> [6,7]          (same query and result as before)

请注意，数据仅存在于叶节点中。因此，对于插入，必须给出完整路径:

insert(A, X, i, 20)

这也意味着，我们可以在数据结构的构造函数中给出树的深度。

编辑:我意识到我需要验证深度:

• 插入操作:必须给出整个路径，并且len(path)必须等于深度
• 获取操作:不允许比结构深度“更深”的路径

Answer 1

from collections import defaultdict
def tree(): return defaultdict(tree)

def get_(t):
    L = []
    if isinstance(t, list):
            L.extend(x for x in t)
    else:
        for k in t:
            L.extend(get_(t[k]))
    return sorted(L)

t = tree()
t['A']['X']['i'] = [1]
t['A']['X']['ii'] = [2,3]
t['A']['Y']['i'] = [4,5]
t['A']['Z']['ii'] = [10,11]

t['B']['X']['ii'] = [6]
t['B']['X']['iii'] = [7]
t['B']['Y']['i'] = [8]

print get_(t)
print get_(t['A'])
print get_(t['A']['X'])
print get_(t['A']['X']['i'])
print get_(t['B']['Y']['i'])

>>> 
[1, 2, 3, 4, 5, 6, 7, 8, 10, 11]
[1, 2, 3, 4, 5, 10, 11]
[1, 2, 3]
[1]
[8]
>>>