我试图为二叉搜索树编写一个递归插入方法,但不断得到 stack level too deep
到底是怎么回事,它一直给我错误?
我的节点类
class Node
attr_accessor :value, :left, :right
def initialize(value)
@value = value
left = nil
right = nil
end
end
二叉搜索树类
class Bst
attr_accessor :root, :size
def initialize
@root = nil
@size = 0
end
def insert(value, root=nil)
if @root == nil
@root = Node.new(value)
end
if value < @root.value
if @root.left == nil
@root.left = Node.new(value)
else
return insert(value, @root.left)
end
return root
end
if value > @root.value
if @root.right == nil
@root.right = Node.new(value)
else
return insert(value, @root.right)
end
end
return root
end
一旦我尝试向树中添加4,就会发生这种情况
tree = Bst.new
tree.insert(10)
tree.insert(6)
tree.insert(19)
tree.insert(4)
1条答案
按热度按时间sqyvllje1#
当您递归并提供新的
root
,您仍在将该值与@root.value
.自从
4
还不到10
,您将递归并传递@root.left
作为root
. 然而,root
从未使用过;你又在比较了@root.value
,并使用@root.left
,而那些永远不会改变;因此,您有无限递归(或者至少无限,直到您破坏堆栈)。你想和我比较吗
root.value
,并使用root.left
相反有
@root
及root
不同的事物是混乱的,并且会导致逻辑错误。更好的变量命名可能会防止此错误。编辑: