二分搜索树节点的查找

什么是二分搜索树？

二分搜索树（Binary Search Tree，简称BST）是一种特殊的二叉树，其中每个节点的值都比其左子树中的所有节点值大，而比右子树中的所有节点值小。这个性质使得在BST中可以高效地进行查找、删除、插入等操作。

节点的查找

在BST中，我们可以通过比较要查找的值和某个节点的值来决定接下来应该去哪个子树中寻找目标值。具体过程如下：

从根节点开始，比较要查找的值和当前节点的值。
如果要查找的值等于当前节点的值，则查找成功。
如果要查找的值小于当前节点的值，则在左子树中继续查找。
如果要查找的值大于当前节点的值，则在右子树中继续查找。
如果遇到空节点，说明查找失败。

代码实现如下：

pythonCopy Code
class TreeNode:
    def __init__(self, val=None, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class BST:
    def __init__(self):
        self.root = None
    
    def search(self, val):
        curr = self.root
        while curr:
            if curr.val == val:
                return True
            elif curr.val > val:
                curr = curr.left
            else:
                curr = curr.right
        return False

实例

假设我们要在如下图所示的BST中查找元素 6：

Copy Code
      5
     / \
    3   7
   / \   \
  2   4   8

按照上述查找方法，我们从根节点开始比较。首先与根节点的值 5 比较，因为 6 大于 5，所以我们需要继续在右子树中查找。接着比较节点 7 的值，因为 6 小于 7，所以我们需要继续在左子树中查找。然后比较节点 8 的值，发现到达了一个空节点，说明查找失败。

因此，在这个实例中，元素 6 在BST中不存在。