2012-05-12 13 views
-1

私が見つけて式を記述しようとしています: バイナリ検索ツリー式

構造的に異なるバイナリツリーの数

」ということができます0または1の子を持つノードが存在します。

は、どのように私はこれを行うに行きますか?

+0

あなたが式を探しているなら、その式おそらくいくつかの入力変数に依存します。ノードの数は* n *ですか?または他のパラメータ?また、「構造的に異なる」を定義できますか?それには鏡像が含まれるかどうか? –

+0

こんにちは、数式はノード数であるNに依存します。構造的に異なるとは、ツリーのいくつの形が存在するかを意味します。 –

答えて

1

0または1の子のみのノードを持つ「バイナリツリー」がチェーンであると思われます。指定された非終端ノードに左の子か右の子があるかどうかを違う方法で扱うということは、「構造的に異なる」ことを意味する場合は、そのツリーをN-1ビット長のバイナリ番号で記述することができます。従って、与えられたNに対する異なる木の数は2 ** N-1となる。

(そして、明らかに、あなたは「木」の異なる「形状は」答えは1である、与えられたNのために存在することができますどのように多くを意味している場合)

+0

こんにちは、あなたの答えに感謝します。 2 ** N-1は2^N-1か2 * N-1を意味しますか? –

+0

'**'はFortranと他のいくつかの言語でべき乗です。 –

関連する問題