несколько вложенных словарь из кортежей в 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': {}}}} 

Если вы хотите, чтобы эти пустые dicts быть 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

Решение Патрика является общим и объектно-ориентированным. Тем не менее, это 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': {}}}}