c++ - エッジから二分木を作る方法は？

Question

fromの入力からバイナリツリーのすべてのエッジを取得しています

   parentId childId
   e.g. 0 3 // means from node 0 to node 3
   // 0 does not mean root of the tree.

これからツリーを構築するにはどうすればよいですか？

Answer 1

これを行う1つの方法は、2つのパスでこれを行うことです。

1. ツリー内のすべてのリンクをアセンブルします。
2. 木の根を見つけます。

すべてのリンクを組み立てるには、各ノードのID（または、IDがすべて0〜Nの範囲にあることがわかっている場合は適切なサイズの巨大な配列）でキー設定されたハッシュテーブルを作成することから始めることができます。 Nの）。ファイルから1行を読み取るときはいつでも、次のことを実行できます。

1. 開始点と終了点で指定されたIDを持つノードがまだ存在しない場合は、それらのノードを作成し、最初にそれらの左右のポインターをNULLに設定します。
2. 最初のノードの子として2番目のノードを追加します。（これは二分探索木ではないと仮定しているので、子の順序は重要ではありません。これが二分探索木である場合は、見つけたものに基づいて適切な子ポインターを設定できます）。

ツリーのルートを見つけるために、ルートノードの候補となるノードのセットを作成できます。これは、最初はツリー内のすべてのノードです。次に、これまでに構築したノード間で反復処理できます。ノードvが別のノードuの子であることがわかるたびに、候補ルートのセットからノードvを削除できます（子であるため）。完了すると、すべての可能なルートのセットが残ります。エッジのリストが実際に二分木を定義している場合、これは1つのノードになります。二分木のフォレストを定義する場合、これにより、フォレスト内のすべてのツリーのルートが返されます。

全体として、これにはO（n）時間がかかります。ここで、nはエッジの数です（バイナリツリーのエッジの数はノードの数から1を引いたものであるため、ツリーのノードの数でもあります）。

必要に応じて、これら2つのパスを1つのパスにまとめることができます。プレゼンテーションを簡単にするために、これらを個別に説明しました。

お役に立てれば！

Answer 2

最初にノードID
のマップを作成し、接続されているノードのリストを作成してから、マップを反復処理して、マップ内の情報からfrom、toへのリンクを作成します。

それが二分木である場合、ファイルに不足している情報があり、形式である必要があります

parent、leftChild、rightChild、
またはleftとrightは常に同じ順序（左が最初）で、ノードごとに2つの行があり、2番目は次の行にあります。