graph-theory - プレオーダーのトラバーサルがポストオーダーのトラバーサルと同じ順序になる可能性はありますか?

Question

T が複数のノードを持つ順序付けられたツリーである場合。T の事前順序トラバーサルが、T の後順序トラバーサルと同じ順序でノードを訪問することは可能ですか? 「はい」の場合、例を教えてください。また、「いいえ」の場合、なぜそれが発生しないのか説明していただけますか?

Answer 1

痛々しいほど明らかな何かを見逃していない限り、答えはノーです。1 つ以上のノード (たとえば、2 つのノード) を持つ順序付きツリーは、次のようになります。

    A    
 B                     

また

    A
        C

ポスト オーダー トラバーサルは、左-右-ルートの順序でノードを訪問し、プレオーダー トラバーサルは、ルート-左-右の順序でノードを訪問します。それらが同じ出力を生成するためには、「左」は「ルート」と等しくなければなりませんが、これは意味がありません。上記の例では、予約注文ではそれぞれ AB または AC が生成され、ポスト オーダーでは BA および CA が生成されます。