バイナリ ツリー上のルートから特定のノードまでのパスを取得する方法を見つけようとしています。
二分探索木ではありません。
各非リーフノードには、その子へのポインタが 2 つだけあります。
インオーダー、プレオーダー、ポストオーダーのトラバーサルは機能しません。
事前順序付けを試みましたが、方法がわかりません。たとえば、バイナリ ツリーがあります。これはバイナリ検索ツリーではありません。パスを見つけやすくするために、ソート順序ノードを使用します。
1
/ \
2 3
/ \ / \
4 5 6 7
1 から 7 までのパスを見つけたいとします。
事前注文の場合、次の特典があります:
1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7
フローから、すべてのノードを含む 1 -> 7 へのパスを取得します。
明らかに、そうであってはなりません。
どのような助けでも本当にありがたいです。
ベストアンサー1
事前順序探索、または深さ優先探索とも呼ばれるする仕事。
事前順序トラバーサルを再帰的に実装すると、目的のノードに到達したときに、スタック (再帰呼び出し) を巻き戻し、逆順にパスを構築できます。
事前順序トラバーサルを非再帰的に実装すると、スタックが直接構築されるため、この場合は目的のノードに到達すると、パスがすでに存在します。
上記の質問のツリーでは、1 から 7 までのパスを見つけるアルゴリズムは次のように進行します。
- 1から始めてスタックにプッシュすると、スタックは[1]になります。
- 左に2まで行き、スタックにプッシュします。スタックは[1 2]になります。
- 左に4まで移動して押すと、スタックは[1 2 4]になります。
- 4の子はなく、これはあなたが望むものではないので、ポップすると、スタックは[1 2]になります。
- 2に戻って、すでに左に行ったので、今度は右に行くと、スタックは[1 2 5]になります。
- 5の子はないので、ポップ、スタックは[1 2]になります。
- 2の子を使い果たしたので、それをポップすると、スタックは[1]になります。
- これで1に戻り、左は完了です。右の3まで進み、プッシュすると、スタックは[1 3]になります。
- 左に行くとスタックは[1 3 6]になります
- 6は葉っぱなので、探しているものではないので、ポップしてスタックすると[1 3]になります。
- 3から右に移動して押すと、スタックは[1 3 7]になります。
- でも待ってください！見てください！探していたノードに到着しました！スタックを見てください！それがあなたが望むパスです。