BST 的查找操作及实现

# 1. 什么是二叉搜索树（BST）？

二叉搜索树（Binary Search Tree，简称BST）是一种常用的数据结构，具有以下特点：节点的左子树中的所有节点的值均小于该节点的值；节点的右子树中的所有节点的值均大于该节点的值；左右子树也分别为二叉搜索树。二叉搜索树的查找、插入、删除等操作都比较高效，因此在实际开发中被广泛应用。

为什么常用二叉搜索树进行查找操作呢？在BST中，查找操作的时间复杂度为O(logn)，这是因为每次查找都会将搜索范围缩小为原来的一半，使得查找效率很高。因此，BST作为一种高效的数据结构，能够快速地实现数据的查找和排序，很好地满足了实际应用中对于查找的需求。

# 2. 二叉搜索树的基本操作

二叉搜索树（Binary Search Tree，简称BST）是一种常用的数据结构，具有以下几种基本操作：插入、删除和查询。在本章节中，我们将详细介绍这些基本操作的实现方式以及其应用场景。接下来，让我们依次介绍这些操作：插入操作、删除操作和查询操作。

# 3. BST 的查找操作实现

二叉搜索树的查找操作是其最基本的功能之一，本章将介绍BST中查找操作的实现方式及其复杂度分析。

#### 3.1 递归查找算法

在BST中，递归查找算法是最常见的方式之一。其实现思路如下：
1. 从根节点开始，若根为空或者根节点的值等于目标值，则返回根节点；
2. 若目标值小于根节点的值，则递归在左子树中查找；
3. 若目标值大于根节点的值，则递归在右子树中查找。

下面是Python语言实现递归查找算法的示例代码：

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

def searchRecursive(root, target):
    if not root or root.val == target:
        return root
    if root.val > target:
        return searchRecursive(root.left, target)
    else:
        return searchRecursive(root.right, target)

通过递归查找算法，我们可以在BST中高效地查找目标值。

#### 3.2 迭代查找算法

除了递归方式，迭代查找算法也是BST中常用的一种方式。实现方式如下：
1. 从根节点开始，若根为空，则返回空值；
2. 循环遍历BST，直到找到目标值或者遍历完整个BST。

以下是Java语言实现迭代查找算法的示例代码：

class TreeNode {
    int val;
    TreeNode left, right;
    public TreeNode(int val) {
        this.val = val;
        this.left = this.right = null;
    }
}

public TreeNode searchIterative(TreeNode root, int target) {
    while (root != null && root.val != target) {
        if (root.val > target) {
            root = root.left;
        } else {
            r