二叉搜索树的最小值不能是最左边的条目吗？

Question

如果我像下面这样构建一个二叉搜索树，对吗？或者这样的树不是有效的二叉搜索树？

    7
   / \
  5   8
     / \
    4  10

因为我遵循了左小右大的原则。所以我想这是一个二叉搜索树？

Answer 1

尝试手动走树；假装你是一个正在寻找 4.

的函数

• 您从树的根部开始：7。
• 4 小于 7，所以你向左转到 5。
• 4 小于 5 所以你又往左走。
• 那里什么都没有，所以你会得出 4 不在树中的结论。

当然这是不正确的，所以不，这不是 BST 的有效设置。不仅仅是每个值只需要位于相对于其直接父级的正确位置。每个值还需要位于相对于树中其他节点的正确位置。

确切的位置取决于每个值的插入顺序，但是对于这种值配置，4 应该在 5 的左边。

Answer 2

绝对是一棵二叉树，因为每个节点只有两个叶子。

但正如其他人所说，它不是二叉搜索树。一种判断方式是对于每个节点，所有左叶的值都应该小于self的值，所有右叶的值都应该大于self的值。只有这样才能进行二分查找。