python - python中元组的多嵌套字典

Question

我有这个元组列表

list_of_tuples = [('0', '1'), ('1', '1.1'), ('1', '1.2'), ('1', '1.3'), ('1', '1.4'), ('0', '3'), ('3', '3.1'), ('3', '3.2'), ('3', '3.3'), ('3', '3.4'), ('3', '3.5'), ('0', '4'), ('4', '4.1'), ('4', '4.2'), ('4', '4.3'), ('4', '4.4'), ('4', '4.5'), ('4', '4.6'), ('4', '4.7'), ('4', '4.8'), ('4', '4.9'), ('0', '5'), ('5', '5.1'), ('5', '5.2'), ('5', '5.3'), ('5', '5.4'), ('0', '6'), ('6', '6.1'), ('6', '6.2'), ('6', '6.3'), ('6', '6.4'), ('6', '6.5'), ('0', '7'), ('7', '7.1'), ('7', '7.2'), ('7', '7.3'), ('7.3', '7.3.1'), ('7.3', '7.3.2'), ('7.3', '7.3.3'), ('0', '8'), ('8', '8.1.1'), ('8', '8.1.2'), ('8', '8.2'), ('0', '9'), ('9', '9.1'), ('9', '9.2'), ('0', '10'), ('10', '10.1'), ('10', '10.2'), ('10', '10.3'), ('10.3', '10.3.2'), ('10.3', '10.3.3'), ('10.3', '10.3.4'), ('10.3', '10.3.5'), ('10.3', '10.3.6')

元组中的第一个值是父级，第二个是值。

(parent,child)

我希望输出是这样的。

{ '0':
     {'1':
         {'1.1':None,
          '1.2':None......
         }
     {'3':
         {'3.1':None/[]..
         }
     }
}

我可以将它添加到字典中，但我希望它像一棵有多个 child 的树一样嵌套。

d = defaultdict(list)
for k, v in h:
   d[k].append(v)

感谢任何帮助。

Answer 1

Patrick 的解决方案是通用的和面向对象的。但是，它是 O(N^2)(N 是边的数量)，因为它为每条边遍历整个树。因为你知道你得到的边缘是深度优先的，所以你可以通过记住你在树中的当前位置，插入你所在的位置，然后返回来节省很多时间(对于大树:很多!)如果需要，树。

下面是更简洁的O(N)，没有您自己的类和额外转换的额外开销:

from pprint import pprint

d = {}
crnt = d  # memo the crnt subtree
stck = []  # stack of (sub)trees along current path
for k, v in list_of_tuples:
  while stck and k not in crnt:
    crnt = stck.pop()
  if k not in crnt:
    crnt[k] = {}
  stck.append(crnt)
  crnt = crnt[k]
  crnt[v] = {}

pprint(d)

{'0': {'1': {'1.1': {}, '1.2': {}, '1.3': {}, '1.4': {}},
       '10': {'10.1': {},
              '10.2': {},
              '10.3': {'10.3.2': {},
                       '10.3.3': {},
                       '10.3.4': {},
                       '10.3.5': {},
                       '10.3.6': {}}},
       '3': {'3.1': {}, '3.2': {}, '3.3': {}, '3.4': {}, '3.5': {}},
       '4': {'4.1': {},
             '4.2': {},
             '4.3': {},
             '4.4': {},
             '4.5': {},
             '4.6': {},
             '4.7': {},
             '4.8': {},
             '4.9': {}},
       '5': {'5.1': {}, '5.2': {}, '5.3': {}, '5.4': {}},
       '6': {'6.1': {}, '6.2': {}, '6.3': {}, '6.4': {}, '6.5': {}},
       '7': {'7.1': {},
             '7.2': {},
             '7.3': {'7.3.1': {}, '7.3.2': {}, '7.3.3': {}}},
       '8': {'8.1.1': {}, '8.1.2': {}, '8.2': {}},
       '9': {'9.1': {}, '9.2': {}}}}