5

私は次のような「非標準」形式の辞書ツリーを持っています。

tree = {'0': {'A': {'B': {'C': {}}}},
             {'D': {'E': {}},
                   {'F': {}}}}

リーフノードは、値が空のディクショナリであるディクショナリのキーと値のペアとして定義されます。次のようなリストのリストとして、すべてのリーフからルートへのパスを抽出したいと思います。

paths_ = [['C', 'B', 'A', '0'],
          ['E', 'D', '0'],
          ['F', 'D', '0']]

それが役立つ場合は、パスを逆にすることもできます。

paths_ = [['0', 'A', 'B', 'C'],
          ['0', 'D', 'E'],
          ['0', 'D', 'F']]

私はそれを再帰的に行わなければならないことを知っており、パスごとにアキュムレータリストが必要です。関数がパスリストを生成するのもいいでしょう。私がこれまでに持っているのはこれです：

def paths(node, subtree, acc=[]):
    if not subtree:
        yield [node]+acc
    for n, s in subtree.items():
        yield paths(n, s, acc)

それは本当に私が望むことをしません：

paths_ = list(paths('0', tree['0']))

理想的には、これはリストのリストを返すはずです。どんな助けでも大歓迎です。

4

3 に答える 3

8

あなたが実際に次の構造を意図していると仮定しますtree：

tree = {'0': {'A': {'B': {'C': {}}},
              'D': {'E': {},
                    'F': {}}}}

paths()これがあなたが望むことをするはずの同様の関数です：

def paths(tree, cur=()):
    if not tree:
        yield cur
    else:
        for n, s in tree.items():
            for path in paths(s, cur+(n,)):
                yield path

結果：

>>> list(paths(tree))
[('0', 'A', 'B', 'C'), ('0', 'D', 'E'), ('0', 'D', 'F')]

リストの代わりにデフォルト引数としてタプルを使用したことに注意してください。これは、可変のデフォルト引数が問題を引き起こす可能性があるためです。

于 2012-07-19T23:23:07.490 に答える
2

選択した回答と同様に、このようなものを使用できます。

 import collections

 def iter_paths(tree, parent_path=()):
     for path, node in tree.iteritems():
         current_path = parent_path + (path,)
         if isinstance(node, collections.Mapping):
             for inner_path in iter_paths(node, current_path):
                 yield inner_path
         else:
             yield current_path

次のdictの場合：

tree = {'A':1, 'B':{'B1':1, 'B2':2}, 'C':{'C1':{'C11':1, 'C12':2},'C2':{'C21':1, 'C22':2}}}

出力は次のようになります（歩留まりの順序は異なる場合があります）。

('A',)
('C', 'C2', 'C22')
('C', 'C2', 'C21')
('C', 'C1', 'C12')
('C', 'C1', 'C11')
('B', 'B1')
('B', 'B2')
于 2017-02-18T10:08:22.303 に答える
0

ツリー構造が次の形式であると仮定します：{'0'：{'A'：{}、'B'：{}}}次に、このようなものでうまくいくはずです。

def paths(nodeId, children, ancestors, allPaths):
    ancestors.append(nodeId)
    if len(children) == 0:
        allPaths.append(ancestors)
    else:
        for childId in children:
            paths(childId, children[childId], ancestors[:], allPaths)

allPaths = []
paths('0', tree['0'], [], allPaths)

そのようなものが機能するはずです。通常は最初にこれを試してみますが、今はiPadを使用しています。それがうまくいかない場合、それはあなたにいくつかのアイデアを与えるはずです。

于 2012-07-19T23:23:17.677 に答える