バイナリ ツリーの場合:ツリー ノードの値を考慮する必要はありません。「N」個のノードを持つさまざまなツリー トポロジにのみ関心があります。
二分探索ツリーの場合:ツリー ノードの値を考慮する必要があります。
178053 次
11 に答える
86
バイナリ ツリーの総数 =
i を合計すると、ノードが n 個ある二分探索木の総数が得られます。
基本ケースは t(0) = 1 および t(1) = 1 です。つまり、1 つの空の BST と 1 つのノードを持つ 1 つの BST があります。
したがって、一般に、上記の式を使用して二分探索木の総数を計算できます。この式に関連して、 Googleのインタビューで質問を受けました。問題は、頂点が 6 つある場合に可能な二分探索木の総数はいくつになるかということでした。答えは t(6) = 132
私はあなたにいくつかのアイデアを与えたと思います...
于 2012-09-21T13:57:23.847 に答える
42
同僚の Nick Parlante (彼がまだスタンフォードにいた頃) によるこの記事をお勧めします。構造的に異なるバイナリ ツリーの数 (問題 12) には、単純な再帰的な解決策があります (閉じた形式では、@codeka の回答が既に述べたカタロニア語の式になります)。
構造的に異なるバイナリサーチツリー (略して BST) の数が「プレーンな」バイナリ ツリーの数とどのように異なるかはわかりませんが、「ツリー ノードの値を考慮する」ということで、各ノードがたとえばBST 条件と互換性のある任意の数の場合、異なる (すべての構造が異なるわけではありません!-) BST の数は無限です。私はあなたがそれを意味しているとは思えないので、例を挙げてあなたが何を意味するのかを明確にしてください!
于 2010-06-15T04:02:45.317 に答える
14
いいえを与えられた場合。ノードの数は N です。
BST の数が異なる = カタロニア語(N)
構造的に異なるバイナリ ツリーの数が異なる = カタロニア語(N)
二分木の異なる数=N!*カタロニア語(N)
于 2013-10-20T11:55:14.933 に答える
10
Eric Lippertは最近、これに関する非常に詳細な一連のブログ投稿を行いました。
あなたの具体的な質問に答えて、彼は次のように述べています。
n 個のノードを持つ二分木の数は、多くの興味深い特性を持つカタロニア語数によって与えられます。n 番目のカタルーニャ数は、式 (2n) によって決定されます。/ (n+1)!n!、指数関数的に増加します。
于 2010-06-15T03:56:47.800 に答える
6
n 個のノードを持つさまざまな二分木:
(1/(n+1))*(2nCn)
ここで、C=コンビネーション。
n=6,
possible binary trees=(1/7)*(12C6)=132
于 2011-10-13T12:28:04.257 に答える
5
(2n)!/n!*(n+1)!
于 2010-11-24T15:49:43.937 に答える
1
The number of possible binary search tree with n nodes (elements,items) is
=(2n C n) / (n+1) = ( factorial (2n) / factorial (n) * factorial (2n - n) ) / ( n + 1 )
where 'n' is number of nodes (elements,items )
Example :
for
n=1 BST=1,
n=2 BST 2,
n=3 BST=5,
n=4 BST=14 etc
于 2012-07-07T13:44:46.570 に答える
0
二分木 :
値を考慮する必要はありません。構造体を見る必要があります。
(2乗n) - nで与えられる
例: 3 つのノードの場合、(2 乗 3) -3 = 8-3 = 5 つの異なる構造体
二分探索木:
ノード値も考慮する必要があります。私たちはそれをカタロニア番号と呼んでいます
2n C n / n+1 で与えられる
于 2014-08-18T17:45:56.347 に答える