C＃の任意のノードから始まる一般的なツリー構造をトラバースする

Question

深度優先と幅優先優先の両方の順序で任意のツリーに対するツリートラバーサルアルゴリズムが必要です。トリッキーな部分は、任意のノードから開始し、別の特定のノードが通過するまで続ける必要があるということです。

私は開始ノードに到達して終了ノード（私が現在行っている）まで続けるまで、通常のアルゴリズムを使用して、通過ノードを無視できますが、これは醜く非効率的です。

ご提案ください。

更新：各ノードには、関連付けられたIDがあります。場合によっては、開始ノードと終了ノードの参照があります。他のケースでは、私は2つのIDを与えられている、私は指定されたノードが開始ノードかエンドノードかどうか、そのIDを調べることによってチェックする。私は深さ優先の探索を使って開始ノードを見つける。開始ノードと終了ノードの両方は、階層内のどこにでも配置できます。開始ノードと終了ノードの両方への参照がすでに与えられている場合のアイデアを思いつくことができれば幸いです。ところで、ツリー内のノードは、実際には、ノードのサブノードのそれぞれについて0から開始し、1つのルートノード

Answer 1

あなたがやっていることは、最も効率的なやり方だと思います。特に任意の木で作業している場合。

あなたは任意のツリーが与えられています。あなたは、トラバーサルを開始するノードを見つける必要があります。階層がない（バイナリツリーではない）ので、ノードをスキャンする必要があります（指定ノードがリーフノードである場合、またはツリー内にノードがない場合、ノードの半分以上をスキャンすることになります）あなたがノードを見つけるのを見つけるまで、ツリー全体を検索する必要があります）。ノードを見つけると、DF TraversalまたはBF Traversalを開始できます。

私はあなたができる最適化を見ません。

Answer 2

むしろより

Traverse(RootNode, StartNode, EndNode) 

パスが存在するソート順に従ってソートされルートとしての開始ノード

Traverse(StartNode, EndNode) 

ただし、開始ノードの子ではないノードを返す場合は、現在の方法を引き続き使用する必要があります。

Answer 3

無関係なクエリにたくさん答える必要があり、パスを提供する必要がある場合（単に存在するかどうかを知らせるのではなく）、AFAIKを今よりも上手くいくことはできません。

一方、少数の特定のノード（たとえば、AからB、C、D、E、F、およびGまでのパスは何ですか）を含む多数のクエリが必要な場合は、そのノードからminimum spanning treeを取得し、BFSをより効率的にします。