Python二叉搜索树Search函数报错：NoneType无search属性及参数误解

问题重现 #

实现Python二叉搜索树的search函数时，搜索不存在的键（如26）会抛出AttributeError: 'NoneType' object has no attribute 'search'，同时疑惑为何会有「search()需2个参数却传入3个」的误解。相关代码与报错如下：

节点类与Search函数代码 #

class Node: 
    def __init__(self, key, parent = None): 
        self.key = key
        self.parent = parent 
        self.left = None 
        self.right = None
        if parent != None:
            if key < parent.key:
                parent.left = self
            else:
                parent.right = self

    def search(self, key):
        if self == None:
            return (False, None)
        if self.key == key:
            return (True, self)
        elif self.key > key:
            return self.left.search(key)
        elif self.key < key:
            return self.right.search(key)
        else:
            return (False, self)

测试代码与报错 #

t1 = Node(25)
t2 = Node(12, t1)
t3 = Node(18, t2)
t4 = Node(40, t1)

print('-- Testing search -- ')
(b, found_node) = t1.search(18)
assert b and found_node.key == 18, 'test 8 failed'
(b, found_node) = t1.search(25)
assert b and found_node.key == 25, 'test 9 failed'
(b, found_node) = t1.search(26)
assert(not b), 'test 10 failed'
assert(found_node.key == 40), 'test 11 failed'

报错信息：

Traceback (most recent call last):
  File "/Users/user/PycharmProjects/practice/main.py", line 50, in <module>
    (b, found_node) = t1.search(26)
  File "/Users/user/PycharmProjects/practice/main.py", line 27, in search
    return self.right.search(key)
  File "/Users/user/PycharmProjects/practice/main.py", line 25, in search
    return self.left.search(key)
AttributeError: 'NoneType' object has no attribute 'search'

错误原因分析 #

1. self == None判断无效：search是实例方法，调用时self必然是Node实例，不可能为None。当搜索路径走到叶子节点的子节点（即self.left或self.right为None）时，调用None.search(key)就会触发AttributeError。
2. 参数误解的澄清：报错里没有「需2个参数却传入3个」的问题，你可能混淆了其他场景。实例方法的self是Python自动传入的，你的调用方式t1.search(26)是正确的，只需要传目标键一个参数。

修复方案 #

在递归调用前先检查self.left或self.right是否为None，如果是则返回(False, self)（符合测试用例中「未找到时返回最后访问的节点」的期望）。修复后的search函数如下：

def search(self, key):
    if self.key == key:
        return (True, self)
    elif self.key > key:
        if self.left is None:
            return (False, self)
        return self.left.search(key)
    elif self.key < key:
        if self.right is None:
            return (False, self)
        return self.right.search(key)

验证说明 #

修复后搜索26的流程：

• 从t1(25)出发，26>25，进入右子树t4(40)
• 26<40，检查t4的左子树为None，返回(False, t4)
• 满足test10（not b）和test11（found_node.key ==40）的断言，测试通过。

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