二叉搜索树Python代码

二叉搜索树（Binary Search Tree, BST）是一种常见的数据结构，其中每个节点都包含一个键值，并且左子树中的所有节点的键都小于该节点的键，右子树中的所有节点的键都大于该节点的键。以下是一个简单的二叉搜索树的 Python 实现，包括插入、查找和删除操作：

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

class BinarySearchTree:
    def __init__(self):
        self.root = None

    # 插入节点
    def insert(self, key):
        if not self.root:
            self.root = Node(key)
        else:
            self._insert_helper(self.root, key)

    def _insert_helper(self, node, key):
        if key < node.val:
            if node.left is None:
                node.left = Node(key)
            else:
                self._insert_helper(node.left, key)
        elif key > node.val:
            if node.right is None:
                node.right = Node(key)
            else:
                self._insert_helper(node.right, key)
        else:
            print("Value already exists in the tree!")

    # 查找节点
    def search(self, key):
        return self._search_helper(self.root, key)

    def _search_helper(self, node, key):
        if node is None or node.val == key:
            return node
        if key < node.val:
            return self._search_helper(node.left, key)
        return self._search_helper(node.right, key)

    # 删除节点（这里仅提供简单版本，未处理特殊情况）
    def delete(self, key):
        self.root = self._delete_helper(self.root, key)

    def _delete_helper(self, root, key):
        if root is None:
            return root

        if key < root.val:
            root.left = self._delete_helper(root.left, key)
        elif key > root.val:
            root.right = self._delete_helper(root.right, key)
        else:  # 找到要删除的节点
            if root.left is None:
                temp = root.right
                root = None
                return temp
            elif root.right is None:
                temp = root.left
                root = None
                return temp

            temp = self._find_min(root.right)  # 找到右子树中最小的节点
            root.val = temp.val
            root.right = self._delete_helper(root.right, temp.val)

        return root

    # 辅助函数：找到右子树中的最小节点
    def _find_min(self, node):
        while node.left is not None:
            node = node.left
        return node

# 示例
bst = BinarySearchTree()
bst.insert(50)
bst.insert(30)
bst.insert(70)
bst.insert(20)
bst.insert(40)
bst.insert(60)
print("Search for 40:", bst.search(40))  # 打印结果