algorithm - 为什么二叉搜索树的中序遍历保证非降序？

Question

TL;DR 我的最终问题是在适当的二叉树上找到两个节点(即它本身至少有两个节点)，一个只大于输入，另一个只小于输入。 (线下续)

---

为了实现这一点，我个人断言如果你画一棵树(体面地)，你水平地看到右边的树一定比左边的树大。

换句话说，引用自维基百科(二叉搜索树):

The key in each node must be greater than all keys stored in the left sub-tree, and smaller than all keys in the right sub-tree.

而且它似乎只能保证在本地是真实的。像这样的图:

          A
       /    \
      B      C
    /   \  /   \
   D     E F    G
 /   \
H     I

(字母没有顺序，即只是为了结构)

我所说的局部是指当我们谈论节点 E 时，可以保证 D(具有 F 和 G)小于 E，但是 C、F、G 与 E 相比，是否也可以保证？

这似乎很直观(F、C、G 都大于 E)，但我没有找到证明这一点的方法，那么有任何反例或理论证明吗？有什么定理或建议吗？

---

编辑:我终于发现这等同于为什么二叉搜索树的中序遍历具有非递减顺序。

Answer 1

This seems quite intuitive (that F,C,G are all greater than E), but I don't find anyway to prove that, so is there any counterexample or theoretical proof? Any existed theorems or suggestions?

1. F > A — BST 的定义(“每个 节点中的键必须......小于右子树中的所有 键”)
2. E < A — BST 的定义(“每个 节点中的键必须大于存储在左子树中的所有 键”)
3. E < A < F — 传递性

C 和 G 依此类推