Python 数据结构：二叉搜索树（BST）查找操作

# /*
# Python 数据结构：二叉搜索树（BST）查找操作
# --------------------------------------------------------
# 概念：
# BST 查找操作利用二叉搜索树的有序性：
# 1) 从根节点开始比较
# 2) 目标值 < 根节点 → 进入左子树
# 3) 目标值 > 根节点 → 进入右子树
# 4) 目标值 == 根节点 → 找到
# 5) 递归或迭代方式实现
# */

# ========================================================
# BST 节点定义
# ========================================================
class BSTNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# ========================================================
# BST 操作类（插入 + 查找）
# ========================================================
class BST:
    def __init__(self):
        self.root = None

    # 插入新节点
    def insert(self, data):
        self.root = self._insert_recursive(self.root, data)

    def _insert_recursive(self, node, data):
        if node is None:
            return BSTNode(data)
        if data < node.data:
            node.left = self._insert_recursive(node.left, data)
        elif data > node.data:
            node.right = self._insert_recursive(node.right, data)
        return node

    # 查找节点（返回 True / False）
    def search(self, target):
        return self._search_recursive(self.root, target)

    def _search_recursive(self, node, target):
        if node is None:
            return False
        if target == node.data:
            return True
        elif target < node.data:
            return self._search_recursive(node.left, target)
        else:
            return self._search_recursive(node.right, target)

# ========================================================
# 示例演示
# ========================================================
bst = BST()
for value in [50, 30, 70, 20, 40, 60, 80]:
    bst.insert(value)

search_values = [40, 25, 80, 90]
for val in search_values:
    found = bst.search(val)
    print(f"查找 {val} -> {'找到' if found else '未找到'}")

# ========================================================
# 要点总结：
# --------------------------------------------------------
# 1) BST 查找利用左 < 根 < 右 的有序性快速定位；
# 2) 时间复杂度平均为 O(log n)，最坏为 O(n)（退化为链表）；
# 3) 可递归或迭代实现；
# 4) 查找操作返回节点存在与否或节点本身；
# 5) 查找前可确保 BST 已正确构建。
# */

# 查找 40 -> 找到
# 查找 25 -> 未找到
# 查找 80 -> 找到
# 查找 90 -> 未找到