Python二进制搜索树:搜索功能错误

Question

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'

我的搜索函数在递归调用search(self)时出现错误。Left(键)和search(self。键)。它说search()需要2个位置参数，但是得到3个，我不明白这是怎么发生的?

Answer 1

这个问题真的让我绞尽脑汁....感谢那些提醒我函数被调用的评论，self实例被隐式传递，我忘记了对象的基本知识，我猜。这个实现通过了测试用例。如果有更好的实现方法，请随时发布，因为我很想看到他们…

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