为什么这个BST实现不起作用

Question

作为项目的一部分，我必须实现一个BST，目的是在键和值的大字典中进行排序。但是，我的代码出现了一些问题。具体来说，我收到一条错误消息，因为我已经超过了最大递归限制。

这是代码：

@dataclass
class Node:
key: Any = None
value: Any = None
left: Any = None
right: Any = None
def put(self, key, value):
new_node = Node(key, value)
if new_node.value < self.value:
if self.left is None:
self.left = Node(key, value, None, None)
else:
self.put(key, value)
elif new_node.value > self.value:
if self.right is None:
self.right = Node(key, value, None, None)
else:
self.put(key, value)

我知道我已经创建了一个无限递归函数，但我不明白为什么。看着它，我觉得它不应该是无限的。有人能告诉我我做错了什么吗？

Answer 1

据我所见，您的递归调用self.put(key，value(与初始调用相同(参数相同(，这会导致无限循环；想想你希望你的算法如何表现(在图表上模拟过程会有所帮助(。

为了将来参考，这里是固定的代码(只修复了问题中提到的问题；还有改进的空间(。

@dataclass
class Node:
key: Any = None
value: Any = None
left: Any = None
right: Any = None
def put(self, key, value):
new_node = Node(key, value)
if new_node.value < self.value:
if self.left is None:
self.left = Node(key, value, None, None)
else:
self.left.put(key, value)
elif new_node.value > self.value:
if self.right is None:
self.right = Node(key, value, None, None)
else:
self.right.put(key, value)