如何在Python中将元组转换为字典树

Question

有一个像这样的元组：

t = (
  (1, -1, 'python'),
  (2, -1, 'ruby'),
  (3, -1, 'php'),
  (4, -1, 'lisp'),
  (5,  1, 'flask'),
  (6,  1, 'django'),
  (7,  1, 'webpy'),
  (8,  2, 'rails'),
  (9,  3, 'zend'),
  (10, 6, 'dblog')
)

我想把它改成一个列表，每个列表项都是一本字典。这本词典有一本钥匙子是另一本词典。如何改变元组t，我希望是这样的列表字典树：

^{pr2}$

]

非常感谢

Answer 1

如果初始列表的顺序正确，那么可以看看Martijn Pieters解决方案。但是，如果不能保证顺序，则解决方案之一是在初始列表上循环两次：

children = {}
objs = []
l = []
for id, parent, title in t:
    obj = {
        "id": id,
        "fid": parent,
        "title": title
    }
    objs.append(obj)

    if parent == -1:  # keep only roots
        l.append(obj)

    if parent not in children:  # append to children
        children[parent] = []
    children[parent].append(obj)

for obj in objs:
    if obj["id"] in children:
        obj["son"] = children[obj["id"]]

Answer 2

创建一个单独的字典，将ID映射到本地ID fid title子dictionary。在单独的词典中找到fid后，将本地词典缝合在一起。如果本地字典的fid为-1，则将其添加到列表中。这是因为本地字典是同一个对象，而不管它包含什么。在

Answer 3

l = []
entries = {}

for id, fid, title in t:
    entries[id] = entry = {'id': id, 'fid': fid, 'title': title}
    if fid == -1:
        l.append(entry)
    else:
        parent = entries[fid]
        parent.setdefault('son', []).append(entry)

这里entries跟踪到目前为止创建的所有条目，这样您就可以直接向它们添加子条目，而不必搜索树。在

这假设您的列表t是按id正确排序的，并且只有子元素是较低ID的子级。在

演示：

^{pr2}$

如果“fid after id”假设不成立，您需要添加一个仍要处理的子id队列：

l = []
entries = {}
queue = {}

for id, fid, title in t:
    entries[id] = entry = {'id': id, 'fid': fid, 'title': title}
    if id in queue:
        entry['sons'] = queue[id]
        del queue[id]
    if fid == -1:
        l.append(entry)
    elif fid in entries:
        parent = entries[fid]
        parent.setdefault('son', []).append(entry)
    else:
        queue.setdefault(fid, []).append(entry)

if queue:
    raise ValueError('No entries found for fid(s) {}'.format(queue.keys()))

现在，t中的条目顺序可以完全随机：

>>> import random
>>> t = list(t)
>>> random.shuffle(t)
>>> l = []
>>> entries = {}
>>> queue = {}
>>> for id, fid, title in t:
...     entries[id] = entry = {'id': id, 'fid': fid, 'title': title}
...     if id in queue:
...         entry['sons'] = queue[id]
...         del queue[id]
...     if fid == -1:
...         l.append(entry)
...     elif fid in entries:
...         parent = entries[fid]
...         parent.setdefault('son', []).append(entry)
...     else:
...         queue.setdefault(fid, []).append(entry)
... 
>>> if queue:
...     raise ValueError('No entries found for fid(s) {}'.format(queue.keys()))
... 
>>> pprint(l)
[{'fid': -1,
  'id': 1,
  'son': [{'fid': 1, 'id': 7, 'title': 'webpy'},
          {'fid': 1, 'id': 5, 'title': 'flask'},
          {'fid': 1,
           'id': 6,
           'sons': [{'fid': 6, 'id': 10, 'title': 'dblog'}],
           'title': 'django'}],
  'title': 'python'},
 {'fid': -1,
  'id': 2,
  'son': [{'fid': 2, 'id': 8, 'title': 'rails'}],
  'title': 'ruby'},
 {'fid': -1,
  'id': 3,
  'son': [{'fid': 3, 'id': 9, 'title': 'zend'}],
  'title': 'php'},
 {'fid': -1, 'id': 4, 'title': 'lisp'}]

fid可以是任何id，只要该id在序列t中的某个地方命名为或者是根条目的-1。在