1

我想找出一个父母在一个元组中有多少个孩子，例如

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

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

通过孩子 - 我的意思是字符串之后元组的长度？e.g: ('c', ( ..., ..., ...) )-'c'是字符串(..., ..., ...)还是长度为 3 的元组？

4

2 回答 2

3

让我们首先介绍一种简单的方法来遍历所有树节点（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
于 2012-08-21T07:35:01.830 回答
0

首先让我们将数据结构转换为更合适的形式：

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
于 2012-08-21T08:30:13.197 回答