我正在使用Python来学习BST并尝试实现插入和查找方法。但我在 insertNode 方法中遇到了最大递归深度超出错误。我对 BST 数据结构很陌生,因此很难在 Python 中实现这些方法。我尝试研究并使我的代码与互联网上的代码相似,但我仍然收到错误。
class Node:
def __init__(self,data):
self.data = data
self.left = None
self.right = None
class BST:
def __init__(self):
self.root = None
def insert(self,data):
temp = Node(data)
if self.root is None:
self.root = temp
else:
self.insertNode(self.root,data)
def insertNode(self,root,data):
temp = Node(data)
if data < self.root.data:
if self.root.left is None:
self.root.left = temp
else:
self.insertNode(self.root.left,data)
elif data > self.root.data:
if self.root.right is None:
self.root.right = temp
else:
self.insertNode(self.root.right,data)
def findinTree(self,root,data):
if self.root is None:
return False
if data == self.root.data:
return True
if data < self.root.data:
self.findinTree(self.root.left,data)
else:
self.findinTree(self.root.right,data)
return False
bst = BST()
bst.insert(30)
bst.insert(10)
bst.insert(50)
bst.insert(90)
bst.insert(100)
bst.insert(15)
请帮助调试错误,以便功能按预期工作。
最佳答案
在 insertNode
您引用self.root
这是树的根。相反,您应该引用root
,函数参数。
事实上,在创建第一个子级别( bst.insert(50)
)后,树根的右分支不是 None
不再这样了,所以它一直打电话self.insertNode(self.root.right,data)
def insertNode(self,root,data):
temp = Node(data)
if data < root.data:
if root.left is None:
print("Inserting {} on the left branch of {}".format(data, root.data))
root.left = temp
else:
print("Inserting {} on the left branch of {}".format(data, root.data))
self.insertNode(root.left,data)
elif data > root.data:
if root.right is None:
print("Inserting {} on the right branch of {}".format(data, root.data))
root.right = temp
else:
print("Inserting {} on the right branch of {}".format(data, root.data))
self.insertNode(root.right,data)
关于python - 在实现二叉搜索树时,Python 中的最大递归深度超出了错误,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/46473429/