0

二分探索木を再構築する関数に取り組んでいます。まずは手作りしてみます。

私が持っているとしましょう: pre- 10,3,5,4,15,7,8,2,9,20 in- 4,5,3,15,10,20,8,7,9,20

私はそれを理解することはできません。ルートは 10 である必要があり、順序どおりのシーケンスで 10 の左側にあるすべての数字は右側のサブツリーにある必要があることを知っています。

それは私に4,5,3,15を与えるでしょう

15 は 10 よりも大きく、バイナリ サーチ ツリーであるためには、左側のサブツリーのすべてのノードがルートよりも小さくなければなりません。

これは、この 2 つのシーケンスが無効な二分探索木を形成するということですか?

4

1 に答える 1

0

あなたは正しいです。与えられた順序でのトラバーサルに基づいて、ツリーは BST ではないようです。10 はルート ノードである必要があります。これは、事前注文トラバーサルの最初のノードを見て収集したものです。順序通りの走査で 10 の左側にあるものはすべて左側のサブツリーにあり、10 の右側にあるものはすべて右側のサブツリーにある必要があります。あなたが指摘したように、15 が 10 の左側にある (または 7、8、9 が 10 の右側にある) ことはあり得ません。そうは言っても、このデータからツリーを再構築することはできます。ソートされた順序でノードがありません。

于 2013-04-14T01:28:31.173 に答える