4

私はインターネット上でさまざまな答えを得ています

  1. https://in.answers.yahoo.com/question/index?qid=20100508110438AAbKyMj
  2. http://wiki.answers.com/Q/How_many_ordered_trees_are_possible_with_3_nodes?#slide=2

私もSOで質問を見ましたが、あまり役に立ちませんでした

答えは何ですか？

  • また、これは木ですか？

        a
   /
  b
 /
c
4

2 に答える 2

1

まず、はい、どこにも言及されていないツリーを「完全」にする必要がない限り、あなたの例は合理的な定義の下のツリーです。したがって、これらのページの両方の回答は (当然のことながら) 間違っているのではないかと思います。

第二に、平等の意味が明確になっていないため、2 番目のリンクでの質問の言い回しが気に入りません。トポロジー的に同じツリー (同じ構造、つまりノードの配置) を探しているだけですか、それとも最初のリンクのように、3 つの特定のノードのセットを含むツリーの等価性を探しています。したがって、最初のリンクの質問に固執します。

順序付けられたツリーの次の定義を使用しています。この質問には関係ないので、空のツリーのエッジ ケースは無視しますが、必要に応じて空のツリーを候補として含める定義を作成することもできます。順序付けられたツリーは、ルート ノードと、空の可能性がある子のリスト (順序付けられたシーケンス) で構成され、それぞれが順序付けられたツリーでもあります。

この定義には明らかにあなたの例が含まれています。ルートは A で、単一の子 B があり、その子 B には子を持たない単一の子 C があります (子の空のリスト)。

ツリーに配置するノードの数 N について再帰的に進めましょう。T(N) を、N 個の (ラベル付けされた) ノードの固定セットから構築できる個別の順序付けられたツリーの数とします。

基本ケース: N = 1. ノードが 1 つだけある場合、そのノードがルートであるツリーを 1 つだけ構築できます。したがって、T(1) = 1 です。

2 番目のケース: N = 2。ルート ノードには 2 つの選択肢があります。残りのノードは、必然的にルートの最初で唯一の子になります。したがって、T(2) = 2 です。

3 番目のケース: N = 3。ルート ノードには 3 つの選択肢があります。ルート ノードを選択したら、再び 2 つのケースがあります。

  • ケース A: ルート ノードには 2 つの子があり、それぞれが 2 つの要素を持つ順序付きツリーです。残りの 2 つのノードを注文する方法は 2 つあります。したがって、ルート ノードに 2 つの子がある場合、3 つのノードを持つ 3*2 = 6 の可能な順序付きツリーがあります。

  • ケース B: ルート ノードには 1 つの子があり、これは必然的に 2 つの要素を持つ順序付きツリーです。残りの 2 つの要素から順序付けされたツリーを構築する方法は T(2) = 2 通りあります。そのため、ルート ノードに子が 1 つしかない場合、3 つのノードを持つ合計 3*2 = 6 つの順序付けられたツリーが可能です。

これらの 2 つのサブケースは、すべての可能性をカバーし、重複していません (可能性のある順序付けられたツリーを 3 つのノードで分割します)。したがって、それらを追加するだけで済みます: T(3) = 6 + 6 = 12.

より一般的な質問に興味がある場合は、少しトリッキーで、答えがわかりません。また、答えがわかっているかどうかもわかりません。私が取るアプローチは次のようなものになります：

一般的なケース: N. ルートは 1 つです。残りの N - 1 個のノードは、ルートのサブツリーにある必要があります。したがって、N - 1 の分割数 (N - 1 をグループに分割する方法の数) を調べます。次に、各グループに入るアイテムを選択する方法の数を調べる必要があります。次に、各グループにあるノードの数から作成できる順序付きツリーの数を調べます。

とにかく、他のアプローチがあります。しかし、それはおそらくこの質問の範囲を超えています。

注: 発生する可能性のある質問の 1 つは、次のようなものを数え忘れたかどうかです。

    A                      A
   /                        \
  B           and            B
 /                            \
C                              C

しかし、順序付けられたツリーとして、これらは同じです。ここでは、バイナリ ツリーのように表示されています (各ノードには、空のサブツリーである可能性がある 2 つの子があります)。しかし、順序付けされたツリーでは、ルートが同じであることと、対応する子が等しいことだけを気にします。上記の 2 つのケースでは、ルートは両方とも A です。どちらの場合も、ルートには 1 つの子 B があります。また、どちらの場合も、その子には 1 つの子 C があります。したがって、ツリーは同じです。

于 2015-02-12T01:54:49.910 に答える