インオーダートラバーサルとプレオーダートラバーサルを文字列として指定すると、バイナリツリーを再構築できることは知っていますが、インオーダートラバーサルのみを指定すると、ポストオーダートラバーサルやプレオーダートラバーサルを見つけることができますか？
質問する
614 次
2 に答える
3
いいえ、インオーダートラバーサルのみからポストオーダー/プレオーダーを取得することはできません。もしそうなら、順序のないトラバーサルだけで二分木を再構築することは可能ですが、1つの順序のないトラバーサルでいくつかの可能な再構築された二分木が得られるため不可能です。
于 2012-11-22T09:32:59.663 に答える
1
入力はどのように見えますか、そしてツリーの目的は何ですか？
完全に括弧で囲まれた順序式がある場合は、一意のツリーがあり、ツリーを構築し、ツリーから事前順序と事後順序の用語を構築することで、事前順序と事後順序を取得します。
式が完全に括弧で囲まれていない場合、これは、順序に一致するさまざまなツリー間に違いがないことを示しています。たとえば、算術式を表すツリーの場合、 とはとx+y+z同じです。ただし、これは、どちらの事前注文または事後注文を使用するかは問題ではなく、同じであることを意味します。(x+y)+zx+(y+z)++xyz+x+yz
これが問題にならない場合は、順序のいくつかの可能な表現について心配する必要はありません。表現の1つを選択してから、このツリーによって誘導される事前順序と事後順序を計算します。
于 2012-11-22T09:52:05.563 に答える