Python中二叉搜索树__contains__方法的工作原理及递归实现报错问题排查

先直接解决你的报错问题——你的代码里有两个明显的错误，直接导致了"__contains__未定义"的提示：

报错原因拆解 #

1. 错误的方法调用方式：你直接写了__contains__(...)，但这个方法是属于类实例的，必须通过对象来调用。直接裸写__contains__会被Python当成全局函数查找，自然找不到对应的定义。
2. 属性访问逻辑错误：self.root.key.left完全是错的！self.root.key是节点存储的键值（比如你例子里的"table"），它本身没有left属性——left是Node类的属性，你应该访问的是self.root.left（左子节点对象）。

你原来代码里的这两行：

return __contains__(self.root.key.left,key)
return __contains__(self.root.key.right,key)

不仅调用方式错了，连访问的属性都不对。而且就算改了属性，还得先判断子节点是否为None，否则遇到叶子节点时会触发AttributeError。

先搞懂__contains__方法的工作原理 #

Python里的in运算符本质上就是调用对象的__contains__特殊方法。比如当你写"table" in tree时，Python会自动执行tree.__contains__("table")，根据这个方法返回的True/False来判断元素是否存在。

对于二叉搜索树（BST）来说，__contains__的核心逻辑完全依赖BST的特性：

• 任意节点的左子树所有节点的key都小于该节点的key
• 任意节点的右子树所有节点的key都大于该节点的key
• 左、右子树本身也是合法的BST

所以标准的查找流程是：

1. 如果树是空的（根节点为None），直接返回False
2. 如果目标key等于当前节点的key，返回True
3. 如果目标key小于当前节点的key，递归查找左子树
4. 如果目标key大于当前节点的key，递归查找右子树
5. 直到找到匹配的key，或者遍历到空节点（返回False）

正确的递归实现方案 #

这里提供两种常用的递归实现方式，你可以根据自己的代码结构选择：

方案1：在BinarySearchTree类内封装辅助递归函数

这种方式不需要修改Node类，把递归逻辑完全封装在树类内部，更符合树作为整体的设计逻辑：

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

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

    def store(self, key, data=None):
        # 假设你的插入逻辑已经正确实现，这里给出参考实现
        if self.root is None:
            self.root = Node(key, data)
        else:
            self._insert_recursive(self.root, key, data)

    def _insert_recursive(self, current_node, key, data):
        if key < current_node.key:
            if current_node.left is None:
                current_node.left = Node(key, data)
            else:
                self._insert_recursive(current_node.left, key, data)
        elif key > current_node.key:
            if current_node.right is None:
                current_node.right = Node(key, data)
            else:
                self._insert_recursive(current_node.right, key, data)
        # 若key已存在，可选择更新data或忽略

    def __contains__(self, key):
        # 内部辅助递归函数，负责遍历节点
        def _search_recursive(current_node):
            if current_node is None:
                return False
            if key == current_node.key:
                return True
            elif key < current_node.key:
                return _search_recursive(current_node.left)
            else:
                return _search_recursive(current_node.right)
        
        return _search_recursive(self.root)

方案2：在Node类中实现__contains__

这种方式让每个节点都具备查找能力，树类的__contains__只需要调用根节点的方法即可：

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

    def __contains__(self, key):
        if key == self.key:
            return True
        elif key < self.key and self.left is not None:
            return key in self.left  # 等价于self.left.__contains__(key)
        elif key > self.key and self.right is not None:
            return key in self.right
        return False

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

    def store(self, key, data=None):
        # 同样假设插入逻辑正确
        if self.root is None:
            self.root = Node(key, data)
        else:
            self._insert_recursive(self.root, key, data)

    def _insert_recursive(self, current_node, key, data):
        if key < current_node.key:
            if current_node.left is None:
                current_node.left = Node(key, data)
            else:
                self._insert_recursive(current_node.left, key, data)
        elif key > current_node.key:
            if current_node.right is None:
                current_node.right = Node(key, data)
            else:
                self._insert_recursive(current_node.right, key, data)

    def __contains__(self, key):
        if self.root is None:
            return False
        return key in self.root  # 调用根节点的__contains__方法

这两种方式都能完美支持if "table" in tree:的写法，且递归逻辑清晰。

最后再总结你原来代码的问题 #

1. 混淆了节点对象和节点的key属性：应该访问self.root.left而非self.root.key.left
2. 错误地直接调用__contains__函数：必须通过节点对象调用该方法
3. 未处理子节点为None的边界情况：会导致遍历到叶子节点时触发属性错误

修正这些问题后，你的递归实现就能正常运行了。

内容的提问来源于stack exchange，提问作者gojira