基本二进制搜索树查询

Question

inorder的bst总是排序。但是，我们可以说二进制树是bst如果undord是排序的吗？我的意思是如果是排序，我们可以得出结论始终是bst吗？

Answer 1

如果高度为 $ 0 $ 它是真的。

假设inOrder的所有二进制树排序和高度小于 $ h $ 是bst。

考虑带有root $ x $ ，高度 $ h $ ，它的inOrder是排序的。特别是它的左和右子子树是排序的，并且具有小于 $ h $ 的高度。然后，通过假设，它们是BST。现在，在给定树的InOrder中，在其左子树的所有节点之后列出了Node $ x $ 。由于其Inorder被排序，然后 $ x $ 不小于其左子树的任何节点。同样， $ x $ 不大于其右子树的任何节点。因此，树是BST。

因此，通过在二叉树的高度上诱导，排序为inOrder的所有二进制树是bst。