检查元组中有多少个子项

Question

我想知道一个元组中有多少个父级，例如

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

因此，如果a有3个孩子，c有3个儿子，我想运行一些代码，但到目前为止，我还不知道如何处理这个问题。

所谓的children，我指的是字符串之后元组的长度？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