>我可以证明按顺序遍历二叉搜索树会产生值的排序级数，而无需使用归纳法吗？
这不是一个真正的家庭作业问题。
这是我对矛盾证明的草图。
我们的目标是证明有限有序二叉树的有序遍历会产生有序序列。
为了通过矛盾来证明这一点，我们首先假设相反：存在一些有序的二叉树，使得它的有序遍历产生一个无序序列。 由于我们的树是有限的，因此必须有一个最小的实例。 我们称这棵树为T。
现在，T 不能是单例(即只是一片叶子(，因为单例的遍历会产生一个长度为 1 的序列，这是平凡有序的。
因此，T 必须具有某种形状，L-x-R，其中 x 是分别连接左右子树 L 和 R 的顶点值。
由于 T 是最小且有序的，因此 L 和 R 必须是有序树，其有序遍历产生有序序列。 此外，我们知道 L 中的所有项不能大于 x，R 中的所有项都不能小于 x。 现在，T 的遍历是 [T] = [L] ++ [x] ++ [R]。 但是这个序列必须是有序的，这与我们最初关于T的假设相矛盾。
因此不存在这样的 T，因此任何有序二叉树的有序遍历都必须产生有序序列。
霍扎特？