Basic Binary Search Tree-Abfrage

Question

Inorder-Traversal von BST ist immer sortiert. Aber können wir sagen, dass binärer Baum BST ist, wenn und nur, wenn in Ordnung sortiert ist? Ich meine, wenn in Ordnung sortiert ist, können wir abschließend schließen

Answer 1

Wenn die Höhe $ 0 $ ist, ist es wahr.

Nehmen Sie an, dass alle Binärbäume, für deren Inordner sortiert ist, und die Höhe kleiner als $ H $ sind BST.

Betrachten Sie einen Baum mit der Wurzel $ x $ , Höhe $ H $ und sein Inorder ist sortiert. Insbesondere ist der linke und rechte TeilBee-Inorder sortiert und haben Höhen, der kleiner ist als der $ H $ . Dann sind sie nach der Annahme BST. Nun, im Inordnen des angegebenen Baums, wird der Knoten $ x $ nach allen Knoten des linken Teilbahnens aufgelistet. Da sein Inorder sortiert ist, ist der $ x $ nicht kleiner als jeder Knoten des linken Teilbahnens. Ebenso ist $ x $ nicht größer als jeder Knoten des rechten Teilbahnens. Daher ist der Baum ein BST.

Somit, durch Induktion auf der Höhe des Binärbaums, sind alle binären Bäume, für die in ordnungsgemäß sortiert ist, sind bst.