どのノードが接続されているかだけを知っているバイナリツリーを構築するには？

Question

私はバイナリツリーを構築する必要がありますが、どちらのノードが親、左の子、または右の子か分かりません。私はどのノードが接続されているかだけ知っています。例：このような入力のために：

6 4 
5 7 
9 7 
1 5 
10 4 
3 4 
2 6 
7 8 
5 6 

は（1から1つのパスが常にある）ツリーは、そのように見えるはずです。

一つ、私はまた、ノード数を与えている入力。任意のアイデア、ヒント？

Answer 1

エッジのリストから、簡単にツリーを作成できます。

葉ノードはどれか見つけることができます。ただ一つの辺にしか現れないノードを検索するだけです。 しかし、リーフノードのどれがツリーの先頭であるのかを知ることはできません。 ツリー構造では、任意の葉を選択し、それを頭として選択し、ツリーの順序を変更することができます。有効なツリーになります。

ツリー同形の問題もあります。右と左のサブツリーを入れ替えて有効なツリーを取得できます。

要約すると、このリストから6つの頭部と4つの可能なスワップの合計24の有効な木を得ることができます。