1

これは宿題です、私はそれを考えるのが難しいです。再帰とDPソリューションに関するアイデアを教えてください。どうもありがとう

n個の葉が点線の括弧で囲まれた構造的に異なるすべての完全な二分木を生成して印刷します。「完全」とは、すべての内部（非葉）ノードに正確に2つの子があることを意味します。

たとえば、それぞれ4枚の葉を持つ5つの異なる完全な二分木があります。

4

4 に答える 4

3

Pythonではこれを行うことができます

def gendistinct(n):
    leafnode = '(.)'
    dp = []
    newset = set()
    newset.add(leafnode)
    dp.append(newset)
    for i in range(1,n):
        newset = set()
        for j in range(i):
            for leftchild in dp[j]:
                for rightchild in dp[i-j-1]:
                    newset.add('(' + '.' + leftchild + rightchild + ')')
        dp.append(newset)
    return dp[-1]

alltrees = gendistinct(4)
for tree in alltrees:
    print tree
于 2012-09-06T06:52:51.603 に答える
2

別の戦略を持つ別のPythonの例。

これは再帰的であり、ジェネレーターを使用します。ここでの他の実装よりも低速ですが、一度に1つのリストのみがメモリに存在する必要があるため、使用するメモリは少なくなります。

#!/usr/bin/env python

import itertools

def all_possible_trees(n):
    if n == 1:
        yield 'l'
    for split in range(1, n):
        gen_left = all_possible_trees(split)
        gen_right = all_possible_trees(n-split)
        for left, right in itertools.product(gen_left, gen_right):
            yield [left, right]

if __name__ == '__main__':
    import sys
    n = int(sys.argv[1])
    for thing in all_possible_trees(n):
        print(thing)
于 2017-01-12T15:46:48.243 に答える
1

再帰を使ってそれを行う明確な方法はわかりませんが、間違いなくあります。

むしろ、動的計画法のアプローチを試してみます。

フルツリーの定義では、葉がn個あるツリーにはn-1個の内部ノードがあることに注意してください。また、左側に1〜n-1枚の葉、右側にn-1〜1枚の葉のサイズの2つの木をルートで結合することにより、小さい木から木を生成できることにも注意してください。

また、さまざまなサイズの「ツリー」を点線の括弧文字列として格納できることにも注意してください。これらから新しいツリーを構築するには、連結します（左、右）。

したがって、1つのリーフを持つ単一のツリー（つまり、単一のノード）から始めます。nまでサイズが大きくなる木のリストを作成します。k-leafツリーのリストを作成するには、j = 1からk-1ごとに、jリーフのツリーごとに、kjリーフのツリーごとに、連結してツリー（kリーフ付き）を作成し、リストに追加します。

n-leafツリーを作成するときに、保存するのではなく、印刷することができます。

5 * 1 + 2 * 1 + 1 * 2 + 1 * 5=14本の木と5枚の葉があります。

14 * 1 + 5 * 1 + 2 * 2 + 1 * 5 + 1 * 14=42本の木と6枚の葉があります。

于 2012-09-06T05:20:39.883 に答える
0

Uは再帰を使用できます。i番目のステップでuはツリーのi番目のレベルを考慮し、制約に従ってこのレベルに存在するノードを選択します。-前のレベルに親が存在します-単一の子は存在しません（ 「フル」ツリー）

uに正確にN個のノードがある場合、再帰は終了します。

于 2012-09-06T05:22:41.380 に答える