1

「ツリー内のすべてのパスを列挙する」という質問への回答に触発されて、私は適応バージョンを書きました(ルート化されていないパスは必要ありません):

def paths(tree):
    #Helper function
    #receives a tree and 
    #returns all paths that have this node as root
    if not tree:
        return []
    else: #tree is a node
        root = tree.ID
        rooted_paths = [[root]]
        for subtree in tree.nextDest:
            useable = paths(subtree)
            for path in useable:
                rooted_paths.append([root]+path)
    return rooted_paths

ここで、「ツリー」オブジェクトには、各ノードに関連付けられた番号 (tree.number) があります。私はこのように見えます：

     A,2
    /   \
  B,5   C,4
   |    /  \
  D,1  E,4 F,3

生成された各パスの合計を知るために、パスを 0 値で初期化し、パスのすべての tree.numbers を合計したいと思います。

A-B-D: 8
A-C-E: 10
A-C-F: 9

この結果を得るには、コードをどのように変更すればよいですか? 私はそれを行う方法を見ていません。

4

1 に答える 1

1

目的を達成するには、再帰にもう 1 つの引数を渡します。これは、これまでに取得した合計になります。また、パスごとにもう 1 つの値を返します - その合計:

def paths(tree, sum_so_far):
    #Helper function
    #receives a tree and 
    #returns all paths that have this node as root
    if not tree:
        return []
    else: #tree is a node
        root = tree.ID
        val = tree.Value
        rooted_paths = [[[root], value]]
        for subtree in tree.nextDest:
            useable = paths(subtree, sum_so_far + val)
            for path in useable:
                rooted_paths.append([[root]+path[0], path[1]])
    return rooted_paths

このようなものがうまくいくはずです。パスと整数値のペアの配列を返すことに注意してください。整数値は、そのパスに沿った合計です。

それが役立つことを願っています。

于 2012-04-18T07:52:25.410 に答える