Проверьте, сколько детей в кортеже

Question

Я хотел бы найти, сколько детей у родителя есть в кортеже, например

tree = ('a', (
    ('b',()), 
    ('c', (
    ('e',()), 
    ('f',()), 
    ('g',()), 
)), 
    ('d',()), 
)) 

так что если a имеет 3 детей и c имеет 3 детей, я хотел бы запустить код , До сих пор я понятия не имел, как это можно сделать.

От детей - Я имею в виду длину кортежа ПОСЛЕ строки? e.g: ('c', (..., ..., ...)) - 'c' - это строка и (..., ..., ...) является кортежем длиной 3?

Answer 1

Давайте сначала ввести простой способ перебора всех узлов дерева (DFS):

def walk(t): 
    yield t 
    for child in t[1]: 
     for p in walk(child): 
      yield p 

Давайте посмотрим, как это работает ...

>>> import pprint 
>>> pprint(list(walk(tree))) 
[('a', (('b',()), ('c', (('e',()',()), ('g',()))), ('d',()))), 
('b',()), 
('c', (('e',()), ('f',()), ('g',()))), 
('e',()), 
('f',()), 
('g',()), 
('d',())] 

Затем нам нужно найти свой учитывая родитель и подсчитывать своих детей. Давайте начнем с общей находкой рутиной:

def find(pred, seq): 
    '''returns the first element from seq that satisfied pred''' 
    for elem in seq: 
     if pred(elem): 
      return elem 
    # not found? 
    raise Exception('Not found') 

Тогда давайте адаптировать его для поиска узлов с заданным именем в данном дереве:

def findNode(t, label): 
    return find(lambda node: node[0] == label, walk(t)) 

Для подсчета детей узла, мы просто нужно считать второе значение кортежа:

def childrenCount(node): 
    return len(node[1]) 

Давайте смешивать два вместе:

for label in "abcdefg": 
    print label, childrenCount(findNode(tree, label)) 

Результат:

a 3 
b 0 
c 3 
d 0 
e 0 
f 0 
g 0 

---

@ thg435 предложил использовать словарь вместо. Давайте сделаем так:

def childrenNames(parent): 
    return tuple(child[0] for child in parent[1]) 

treedict = {t[0] : childrenNames(t) for t in walk(tree)} 

Это дает хороший словарь, в который вы можете посмотреть непосредственно (как @ thg435 уже предложенный).

>>> pprint(treedict) 
{'a': ('b', 'c', 'd'), 
'b':(), 
'c': ('e', 'f', 'g'), 
'd':(), 
'e':(), 
'f':(), 
'g':()} 
>>> pprint(sorted(treedict.keys())) 
['a', 'b', 'c', 'd', 'e', 'f', 'g'] 
>>> pprint(len(treedict['a'])) 
3 

Answer 2

Сначала давайте преобразовать структуру данных на что-то более подходящее:

def convert(node, d): 
    key, sub = node 
    d[key] = [convert(s, d) for s in sub] 
    return d[key] 

newtree = {} 
convert(tree, newtree) 

Это создает словарь как {key: list of children}, который вы можете запросить непосредственно:

print len(newtree['c']) # 3