0

手遅れかもしれませんが、解決するまで眠れません:

私はいくつかの親を持つツリーを持っています。親には子供がいて、子供もいます。

ここで、ツリーからすべてのノードを取得する関数が必要です。

これは現在機能しているものですが、深さは 1 レベルのみです。

def nodes_from_tree(tree, parent):
    r = []
    if len(tree.get_children(parent)) == 0:
        return parent
    for child in tree.get_children(parent):
        r.append(nodes_from_tree(tree, child))
    return r

次に、パススルーを試みたrので、子を覚えていますが、関数を複数回使用していて、rすべてのノードを累積的に保存していますが、次のように設定していr=[]ます。

def nodes_from_tree(tree, parent, r=[]):
    r = []
    if len(tree.get_children(parent)) == 0:
        return parent
    for child in tree.get_children(parent):
        r.append(nodes_from_tree(tree, child, r))
    return r

編集：これはツリー構造です：

parent1    parent2    parent3
   |          |          |
   |          |          |
 child        |          |
              |          |
      +--------------+   |
      |       |      |   |
    child   child  child |
      |                  |
  +---+---+              |
child   child        +---+---+
                     |       |
                   child     |
                             |
                       +-----+-----+-----+
                       |     |     |     |
                     child child child child

利用可能な方法:

tree.get_parents()       # returns the nodes of the very top level
tree.get_children(node)  # returns the children of parent or child
4

2 に答える 2

2

あなたの問題は、物事を間違って蓄積しているだけだと思います。

まず、中間ノードにヒットすると、各子はリストを返す必要がありますが、appendそのリストを ing ではなくextending しています。[1, 2, 3, 4]つまり、次のようなものを取得するのではなく、[[1, 2], [3, 4]]つまり、フラットなリストではなく、リストのリスト ツリーに変換するだけです。これを に変更しextendます。

次に、リーフ ノードにヒットした場合、リストはまったく返されませんparent。これを に変更しreturn [parent]ます。

第 3 に、中間ノードにヒットした場合、parentどこにも含めないため、最終的には葉だけになります。しかし、すべてのノードが必要でした。を に変更r = []しr = [parent]ます。

ifそして、その最後の変更により、ブロックはまったく必要ありません。子がいない場合、ループは 0 回発生し、[parent]希望どおりにそのまま返されます。

そう：

def nodes_from_tree(tree, parent, r=[]):
    r = [parent]
    for child in tree.get_children(parent):
        r.extend(nodes_from_tree(tree, child, r))
    return r

一方、このバージョンは動作しますが、まだ混乱しています。2 つの異なるスタイルの再帰を混同しています。アキュムレータをチェーンに渡し、途中で追加するのが 1 つの方法です。チェーンの上流に値を返し、途中で結果を蓄積するのはもう 1 つの方法です。あなたはそれぞれの半分をやっています。

結局のところ、上流の再帰を行っている方法では、下流の再帰がまったく効果がありません。r各子にダウンを渡しますが、それを変更したり、使用したりすることはありません。新しいrリストを作成して返すだけです。

これを修正する最も簡単な方法は、accumulator 引数を削除することです。

def nodes_from_tree(tree, parent):
    r = [parent]
    for child in tree.get_children(parent):
        r.extend(nodes_from_tree(tree, child))
    return r

(アップストリームの収集スタイルではなく、ダウンストリームのアキュムレータ スタイルで行う場合にのみ、分岐再帰をテール コール最適化できることに注意してください。しかし、Python ではテール コールの最適化を行わないため、Python ではそれは問題ではありません。したがって、 、あなたにとってより意味のある方を書いてください。）

于 2013-05-14T01:07:58.490 に答える
2

私があなたの質問を理解した場合、ツリー内のすべての値を含むフラット リストを作成する必要があります。この場合、タプルで表されるツリーは次のように機能します。

def nodes_from_tree(tree,nodes=list()):
    if isinstance(tree,tuple):
        for child in tree:
            nodes_from_tree(child,nodes=nodes)
    else:
        nodes.append(tree)

mynodes = []
tree = (('Root',
        ('Parent',(
            ('Child1',),
            ('Child2',)
            )
        ),
        ('Parent2',(
            ('child1',(
                ('childchild1','childchild2')
            )),
            ('child2',),
            ('child3',)
        )),
        ('Parent3',(
            ('child1',),
            ('child2',(
                ('childchild1',),
                ('childchild2',),
                ('childchild3',),
                ('childchild4',)
            ))
        ))
    ))
nodes_from_tree(tree,nodes=mynodes)
print(mynodes)

プロデュース

['Root', 'Parent', 'Child1', 'Child2', 'Parent2', 'child1', 'childchild1', 'childchild2',
 'child2', 'child3', 'Parent3', 'child1', 'child2', 'childchild1', 'childchild2', 'childchild3', 'childchild4']
于 2013-05-14T01:02:01.900 に答える