algorithm - 葉の左から右への順序が固定されている場合、二分木はいくつありますか?

Question

リストを介してツリーを表現しましょう。

葉の数が A と B の 2 枚の場合、木は 1 本 (AB) になります。

葉の数が 3 枚の場合、A、B、C となります。すると、2 つの木 ((AB) C) と (A (BC)) ができます。

では、葉が N 枚ある場合、木は何本ありますか?

Answer 1

N葉を持つ二分木の数を とするT(N)。

すぐにT(1) = T(2) = 1わかるように、 がありN > 2、ルートで分割できるため、葉が少ない 2 つのサブツリーを取得できます。または、同等に、 と の葉を持つN2 つの空でない二分木から葉をk持つ二分木を組み立てることができN-kます。両方のサブツリーが空でないという条件は、 に変換され1 <= k <= N-1ます。したがって、再帰があります

      N-1
T(N) = ∑  T(k) * T(N-k)
      k=1

再帰がまだわかっていない場合、最初のいくつかの値を計算することは難しくありません

1,1,2,5,14,42,132,429,1430,4862,16796

それらをググってください。これらはカタロニア語の数字であることがわかります。

C(n) = (2*n)! / (n! * (n+1)!)

1つオフセットするので、

T(N) = C(N-1)

これは、再帰よりもはるかに高速に計算できます。