1

n 個のノードを持つ二分木を考えてみましょう。考えられる二分木構造はいくつありますか?

私は次のようなものを試しました：

n   number of different structure:

1        1
2        4
3        16

n >1 の場合は 4(n-1) です。n == 1 の場合は 1?

4

2 に答える 2

5

n 個のノードを使用して形成できるさまざまなバイナリ ツリーの数は、n 番目のカタロニア語数で表されます。

number of nodes (n)   binary trees C(n)  
1                     1  
2                     2  
3                     5  
4                     14

見る：

http://en.wikipedia.org/wiki/Binary_tree
http://en.wikipedia.org/wiki/Catalan_number

于 2011-03-26T03:03:00.517 に答える
5

Adrian Toman による以前の回答は、ノードの値が重要ではなく、ツリーの構造のみが考慮される場合に当てはまります (同じウィキペディアのリンクを参照してください)。

ノード値も重要な場合は、計算が異なります。カタロニア数は、ツリーの可能なさまざまな構造の数を示します。これで、これらの構造のそれぞれにノードを配置できます (順列)。したがって、ノードの値が重要な n ノードの異なるツリーの総数は、次の式で与えられます -

n 番目のカタロニア語 * n!

nodes (n)    trees C(n) * n!
1            1
2            4 (= 2 * 2)
3            30 (= 5 * 6)
4            336 (= 14 * 24)
于 2011-07-26T07:02:44.373 に答える