-1

私は見つけるための式を書き込もうとしています：

「子が 0 または 1 のノードで存在できる、構造的に異なるバイナリ ツリーの数」。

どうすればこれを行うことができますか？

4

1 に答える 1

1

子が 0 個または 1 個しかないノードを持つ「バイナリ ツリー」はチェーンのように思えます。「構造的に異なる」とは、特定の非終端ノードに左の子または右の子があるかどうかを異なる方法で扱うことを意味する場合、N-1 ビット長の 2 進数でそのツリーを記述できることに注意してください。したがって、特定の N に対する異なるツリーの数は 2**N-1 になります。

(そして、明らかに、与えられた N に対して「ツリー」の異なる「形状」がいくつ存在できるかを意味する場合、答えは 1 です。)

于 2012-05-12T22:25:49.537 に答える