バイナリツリーの他の2つのトラバーサルを1つのトラバーサルが与えられたときに見つける

Question

私は、インオーダートラバーサルとプリオーダートラバーサルが文字列として与えられたときにバイナリツリーを再構築できますが、インオーダートラバーサルを考えれば？

Answer 1

いいえ、取寄せ・発注はインオーダートラバーサルからはできません。そうであれば、インオーダートラバーサルだけでバイナリツリーを再構築することは可能ですが、インオーダートラバーサルはいくつかの再構築バイナリツリーを与えることができないため不可能です。

Answer 2

あなたの入力はどのように見え、ツリーの目的は？

完全カッコで囲まれた順序付け式を使用している場合は、ユニークツリーがあり、ツリーを構築してツリーからプリオーダーとポストオーダーの用語を作成することによって、プリオーダーとポストオーダーが得られます。

あなたの式が完全な括弧で囲まれていない場合、これはあなたの順番に合った異なるツリー間に違いがないことを示します。例：算術式を表すツリーの場合、x+y+zは(x+y)+zとx+(y+z)と同じです。 これはつまり、あなたが使用するプレオーダーまたはポストオーダーがどちらでも同じであることを意味します。++xyzと+x+yzも同じです。

これは問題でなければ、あなたの順序でいくつかの表現を心配する必要はありません。表現の1つを選択してから、このツリーによって誘導された順序の前後を計算します。