学術的に言えば、データ構造ツリーとグラフの本質的な違いは何でしょうか? また、ツリーベースの検索とグラフベースの検索はどうでしょうか?
ベストアンサー1
ツリーはグラフの制限された形式にすぎません。
ツリーには方向性 (親/子関係) があり、循環は含まれません。ツリーは有向非巡回グラフ (または DAG) のカテゴリに該当します。したがって、ツリーは、子が 1 つの親しか持てないという制限がある DAG です。
指摘しておくべき重要な点の 1 つは、ツリーは再帰的なデータ構造ではないということです。上記の制限により、ツリーを再帰的なデータ構造として実装することはできません。ただし、一般的に再帰的ではない任意の DAG 実装も使用できます。私が推奨するツリー実装は、集中型のマップ表現であり、再帰的ではありません。
グラフは通常、幅優先または深さ優先で検索されます。ツリーにも同じことが当てはまります。