новообращенный вложен список в словарь в Python

Question

Это не строгий вложенный список, он представляет собой древовидную структуру, которая выглядит следующим образом:

A = [a, [b, c,[d,e]]] 

и соответствующее дерево:

   a 
      /\ 
       b c 
       /\      
       d e 

Всякий раз, когда есть подсписок после одного элемента, подсчет соответствует дочерним узлам этого элемента. В противном случае элементы находятся на одном уровне. Я хочу создать словарь с каждым узлом в качестве ключа, соответственно, как:

child[a] = [b,c,d,e] 
child[c] = [d,e] 

Как я могу сделать это в Python? Или есть другое лучшее предложение о преобразовании древовидной структуры?

Answer 1

Я все еще думаю, что вы должны использовать/вдохновиться существующей реализации, но это может быть то, что вы ищете, если вам это нужно для работы:

#!/usr/bin/env python 

# added a test case 
B = ['a', ['b', 'c',['d','e']], 'f', ['g', 'h']] 
A = ['a', ['b', 'c',['d','e']]] 

# found on stack overflow - flatten list of kids for parent 
def flatten(iterable): 
    """Recursively iterate lists and tuples. 
    """ 
    for elm in iterable: 
     if isinstance(elm, (list, tuple)): 
      for relm in flatten(elm): 
       yield relm 
     else: 
      yield elm 

# add data to an existing tree (recursive) 
def treeify(tree, l): 
    if isinstance(l, list): 
     # avoid looking back 
     l.reverse() 
    for index in range(len(l)): 
     if isinstance(l[index], list): 
      parent_name = l[index+1] 
      # flatten kids to a list 
      tree[parent_name] = list(flatten(l[index])) 
      # continue in deeper lists 
      treeify(tree, l[index]) 

tree = {} 
treeify(tree, A) 
print tree 
tree = {} 
treeify(tree, B) 
print tree 

это переворачивает list, чтобы избежать оглядки когда пересекаешь его. Tt задает имя как следующий член, если текущий - list, и перемещает дочерние элементы немедленно (рекурсивно).

Answer 2

Если вы собираетесь делать много манипуляций с графами, я бы подумал об импорте networkx, так как это упростит ситуацию. Для того, чтобы разобрать ваш вложенный список в networkx дерева:

import networkx as nx 

def parse_tree(node_list): 
    """Parses a nested list into a networkx tree.""" 
    tree = nx.DiGraph() 
    root = node_list[0] 
    tree.add_node(root) 

    queue = [(root, node_list[1])] 

    while queue: 
     parent, nodes = queue.pop(0) 
     prev = None 
     for node in nodes: 
      if isinstance(node, list): 
       queue.append((prev, node)) 
      else: 
       tree.add_node(node) 
       tree.add_edge(parent, node) 

      prev = node 

    return tree 

С помощью этой функции, это просто, чтобы получить словарь потомков каждого узла:

>>> l = ["a", ["b", "c",["d","e"]]] 
>>> tree = parse_tree(l) 
>>> {node: nx.descendants(tree, node) for node in tree} 
{'a': {'b', 'c', 'd', 'e'}, 
'b': set(), 
'c': {'d', 'e'}, 
'd': set(), 
'e': set()}