在为二叉树实现add_node
和search
方法时,我得到了一个递归错误:超过了最大递归深度
代码:
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class BinaryTree:
def __init__(self, root=None):
self.root = root
def add_node(self, node, value):
node = self.root
if node is not None:
if not node.value:
node.value = value
elif not node.left:
node.left = value
elif not node.right:
node.right = value
else:
node.left = self.add_node(node.left, value)
else:
self.root = TreeNode(value)
def search(self, value):
node = self.root
found = False
while node is not None:
if node.value == value:
found = True
if node.left:
found = node.left.search(value)
if node.right:
found = found or node.left.search(value)
return found
def main():
binary_tree = BinaryTree()
binary_tree.add_node(binary_tree.root, 200)
binary_tree.add_node(binary_tree.root, 300)
binary_tree.add_node(binary_tree.root, 100)
binary_tree.add_node(binary_tree.root, 30)
binary_tree.traverse_inorder(binary_tree.root)
print(binary_tree.search(200))
if __name__ == '__main__':
main()
错误:
Traceback (most recent call last):
File ".\binary_tree_test20.py", line 51, in <module>
main()
File ".\binary_tree_test20.py", line 45, in main
binary_tree.add_node(binary_tree.root, 30)
File ".\binary_tree_test20.py", line 22, in add_node
node.left = self.add_node(node.left, value)
File ".\binary_tree_test20.py", line 22, in add_node
node.left = self.add_node(node.left, value)
File ".\binary_tree_test20.py", line 22, in add_node
node.left = self.add_node(node.left, value)
[Previous line repeated 995 more times]
RecursionError: maximum recursion depth exceeded
这是我可以给你的补救办法
尽管我建议只扩展
TreeNode
定义,而不定义BinaryTree
您得到无限递归是因为您没有使用
node
参数,而是将其替换为self.root
。因此,当您递归时,每次都从根开始,而且永远不会结束另外,行
node.left = self.add_node(node.left, value)
期望add_node
返回新节点,但您的方法不返回任何内容。当它更新现有节点时,它应该只返回修改过的节点;如果它正在创建一个新节点,它将返回该节点您可以这样调用此方法:
相关问题 更多 >
编程相关推荐