如何实现函数来获取元素在复杂数据结构中的位置

Question

我在Python中使用列表和字典实现了以下数据结构。

data = [
{
"id": "1",
"children": [
{
"id": "2",
"children": [
{
"id": "3",
"children": []
}
]
}
]
},
{
"id": "4",
"children": [
{
"id": "5",
"children": [
{
"id": "6",
"children": []
},
{
"id": "7",
"children": [
{
"id": "8",
"children": []
},
{
"id": "9",
"children": []
}
]
}
]
}
]
}
]

如何实现下面的函数来通过id检索节点的位置？

def get_location(id, data):
pass

因此，这个函数会返回一个列表，我可以使用它来引用数据中的节点，如-

get_location(1, data) => [0]
get_location(2, data) => [0, 0]
get_location(3, data) => [0, 0, 0]
get_location(4, data) => [1]
get_location(5, data) => [1, 0]
get_location(6, data) => [1, 0, 0]
get_location(7, data) => [1, 0, 1]
get_location(8, data) => [1, 0, 1, 0]
get_location(9, data) => [1, 0, 1, 1]

Answer 1

这样？

这将返回Tuple[int]，而不是List[int]。但我认为元组更符合目的(也许…(。而且，id是str，而不是int，因为数据中id=的类型是str。

from typing import Dict, Tuple, Any, Iterable

def get_location(id: str, data: Dict[str, Any])
-> Tuple[int]:
def handler(d: Dict[str, Any], prefix: Tuple[int])
-> Iterable[Tuple[str, Tuple[int]]]:
for i, item in enumerate(d):
yield (item['id'], (*prefix, i))
yield from handler(item['children'], (*prefix, i))

// you can also initialize flatten and re-use it
flatten = dict(handler(data, ()))
return flatten.get(id, None)