基本的な二分探索ツリー クエリ

Question

BST の inorder トラバースは常にソートされます。しかし、inorder がソートされている場合に限り、バイナリ ツリーは BST であると言えますか? つまり、inorder がソートされている場合、常に BST であると結論付けることができますか?

Answer 1

高さがある場合 $0$ それは本当です。

inorder がソートされ、高さが以下のすべてのバイナリ ツリーであると仮定します。 $h$ BSTです。

根のある木を考えてみましょう $x$, 、 身長 $h$ そしてその順序はソートされます。特に、その左と右のサブツリーの順序はソートされており、高さは以下の値よりも小さくなります。 $h$. 。そして、仮定により、それらは BST です。さて、指定されたツリーの順序で、ノード $x$ は、その左側のサブツリーのすべてのノードの後に​​リストされます。順序はソートされているので、 $x$ は、その左側のサブツリーのどのノードよりも小さくありません。同じく、 $x$ は、その右側のサブツリーのどのノードよりも大きくありません。したがって、ツリーは BST です。

したがって、二分木の高さに関する帰納法により、順序がソートされるすべての二分木は BST になります。