提问人：Shravan 提问时间：9/28/2020 最后编辑：EvgShravan 更新时间：4/11/2022 访问量：91
二叉搜索树的最小值不能是最左边的条目吗？
Can the minimum value of a binary search tree not be the leftmost entry?
问：
如果我像下面这样构造一个二叉搜索树，对吗？或者这样的树不是有效的二叉搜索树？
7
/ \
5 8
/ \
4 10
因为我遵循了左边小元素和右边大元素的规则。所以我想这是一个二叉搜索树？
答：
1赞
Carcigenicate
9/28/2020
#1
尝试手动走树;假装你是一个寻找 4 的函数。
- 你从树的根开始：7。
- 4 小于 7，因此向左转到 5。
- 4 小于 5，所以你再次向左走。
- 那里什么都没有，所以你会得出结论，4 不在树中。
当然，这是不正确的，所以不，这不是 BST 的有效设置。这不仅仅是每个值只需要相对于其直接父级处于正确的位置。每个值还需要相对于树中的其他节点处于正确的位置。
确切的位置取决于每个值的插入顺序，但对于这种值配置，4 应该在 5 的左侧。
1赞
Steven C
9/28/2020
#2
这绝对是一棵二叉树，因为每个节点只有两片叶子。
但就像其他人说的，它不是一个二叉搜索树。一种判断方法是，对于每个节点，所有左叶的值都应该小于 self 的值，所有右叶的值都应该大于 self 的值。只有这样才能进行二分搜索。
评论