1

親がタプルに何人の子供を持っているかを知りたいです。

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

したがって、a3人の子供がいて、3人の子供がいる場合c、コードを実行したいと思いますが、これにアプローチする方法についてはこれまでのところわかりませんでした。

子供たちによって - 文字列の後のタプルの長さを意味しますか? 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))

ノードの子をカウントするには、タプルの 2 番目の値をカウントするだけです。

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

2 つを混ぜてみましょう。

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 に答える