そのエッジ（ノードペア）のリストからバイナリツリーを構築する

Question

非常に珍しい入力からバイナリツリーを構築したいと思います。入力には以下が含まれます。

1. ノードの総数。

2. ルートの整数ラベル。

3. すべてのエッジのリスト（各 に接続されている頂点/ノード）。リスト内のエッジは未分類です。 の左/右の子を決定するルールは1つのみです。 - 最初にリスト内にある が最初に表示されるエッジの子が左側に表示されます。頂点ペアの子/親の順序もランダムです。

私はいくつかのstraighforwardソリューションを作ってみたけど、彼らは（私は基本的にそれらにラベルされたルートを持っている2つのエッジを見つけて、すべてのためにこのプロセスを繰り返したいすべてのエッジのリストを複数の検索を必要としますサブツリー）

この単純なアプローチはと非常に効率的ですノード数が多いツリーの場合、効率的ではありませんが、他に何も思い付きません。

これを解決するためのより効率的なアルゴリズムのアイデアはありますか？

ここよりよい視覚化のため例だ：

INPUT：5つのノード、エッジのルート、2 LABELED LIST：[（1,0）、（1,2）、（2,3）、 （1,4）]

ツリーは次のようになります。

 2 
    1  3 
0  4 

Answer 1

与えられたエッジリストが向けたりしていないと記載されているかどうかを明らかにすることが重要です。

エッジが有向様式で与えられる場合（すなわち、任意の与えられたエッジABは、AがBの親であるという情報も含む）、adjacency listにエッジを格納しながら、各頂点配列で十分であるはずです。入ってくるエッジの配列を通過すると、入ってくるエッジ（つまり親）が0の頂点がルートになります。次に、直線的な時間の複雑さでDFSを実行してグラフをトラバースし、必要に応じて任意のデータ構造に配置することができます。

与えられたエッジが無向であると述べられている場合、スキームは少し変化します。その場合、着信と発信の概念はありません。その場合、配列の構造体が指定されていないので（例えば、BSTなど）、上記のように基本的にルートとして3未満のエッジを持つノードを考え、DFSを実行することができます。 （単一の子ノードを持つすべてのリーフと中間ノード）

Answer 2

単純な解決策は次のとおりです。「ツリー内のすべてのエッジをリンクする！

辞書の準備を開始します。ノードが開始点と終了点によって存在しない場合は、ノードを作成します。本質的にランダムなので、最初に左と右のポインタをNULLに設定できます。 ルールがあります。 "リストの最初に表示されるエッジの子は常に左にあります。"それに応じて子供を作る。 また、ツリーのルートをすでに知っているので、これまで構築したノードを繰り返し処理できます。

これにより、ワンショットでツリーを生成することができます。

希望すると便利です。