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/[]..
         }
     }
}

我可以将它添加到字典中,但我希望它像一个有多个孩子的树一样嵌套.

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

任何帮助表示赞赏.

Answer 1

我要打开一个快速的树类,可以接受这个输入并用它构建一个树,然后我将为该类编写一个方法,将它们转换回字典

class Tree:
    def __init__(self, name, parent=None): #parent is None to detect root
        self.name = name
        self.parent = parent
        self.children = []    
    def add(self, target , child):
        '''
        Does DFS until it finds Tree with name target.  Creates a Tree(child)
        as child of Tree name
        '''
        if self.name == target:
            self.children.append(Tree(child, self))
            return True
        else:
            for subtree in self.children:
                if subtree.add(target, child):
                    return True
        if self.parent:
            return False
        raise ValueError('Bad Parent no such node {}'.format(target))    
    def dictify(self):
        d = {}
        for child in self.children:
          d.update(child.dictify())
        return {self.name: d}

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')]

root = Tree('0')
for parent, child in list_of_tuples:
  root.add(parent, child)
print(root.dictify())

这是pprint(漂亮的印刷)

{'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': {}}}}

如果你想那些空类型的字典是None只是改变dictify到return {self.name: d if d else None}

编辑:schwobaseggl对插入复杂性提出了一个很好的观点.这是一个利用有序输入的Tree类的版本

class Tree:
    def __init__(self, name, parent=None): #parent is None to detect root
        self.name = name
        self.parent = parent
        self.children = []        
    def add(self, target , child):
        '''
        Accepts additions in DFS order.  Relies on the fact that every node will
        be the direct descendant of the previous node or one of its ancestors.
        '''
        if self.name == target:
            kiddo = Tree(child, self)
            self.children.append(kiddo)
            return kiddo
        elif self.parent:
            return self.parent.add(target, child)
        else:
            raise ValueError('Bad Parent no such node {}'.format(target))    
    def dictify(self):
        d = {}
        for child in self.children:
          d.update(child.dictify())
        return {self.name: d}
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')]

root = Tree('0')
curr = root
for parent, child in list_of_tuples:
  curr = curr.add(parent, child)
print(root.dictify())

Answer 2

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': {}}}}