php - ツリー トラバーサル - 2 つの葉の間を探す

Question

ネットワーク ノード マップがあり、2 点間のノードのリストを作成する必要があります。最初は簡単に思えましたが、答えがわかりません:(

次の (簡略化された) データ構造を考えると、

Id    Name        LeftId  RightId
1     Skagway     3
2     Klukwan     3
3     Haines      2       4
4     Juneau      3       5
5     Petersburg  4       6
6     Wrangell    5       7
7     Kasaan      6       4
8     Portage     4       6

ノードをトラバースし、2 点間のすべてのノードのリストを作成するアルゴリズムを作成するにはどうすればよいですか (またはアルゴリズムを提案できますか)。木は、そうでないいくつかの場所を除いて、ほとんど直線です。

彼らは、枝または葉の端から始まるノードを識別できるようにしたいと考えています。

Answer 1

あるノードから別のノードへのパスである場合は、パスのログを記録する開始ノードのルート ノードを持つサブツリーで preorder を使用することをお勧めします。更新: 実際、人工知能アルゴリズム (およびグラフ内の検索パス) も役立つ場合があります。たとえば、非常に単純なものである BFS が役立つ可能性があります。