在Ruby中实现二叉树 [英] Implementing Binary Tree in Ruby
问题描述
我一直在尝试在Ruby中实现BinaryTree类,但是我遇到了stack level too deep
错误,尽管在该特定代码中我似乎没有使用任何递归:
I've been trying to implement BinaryTree class in Ruby, but I'm getting the stack level too deep
error, although I don't seem to be using any recursion in that particular piece of code:
1. class BinaryTree
2. include Enumerable
3.
4. attr_accessor :value
5.
6. def initialize( value = nil )
7. @value = value
8. @left = BinaryTree.new # stack level too deep here
9. @right = BinaryTree.new # and here
10. end
11.
12. def empty?
13. ( self.value == nil ) ? true : false
14. end
15.
16. def <<( value )
17. return self.value = value if self.empty?
18.
19. test = self.value <=> value
20. case test
21. when -1, 0
22. self.right << value
23. when 1
24. self.left << value
25. end
26. end # <<
27.
28. end
我的问题有点偏离轨道了.当前的代码设置在第8行给了我stack level too deep
错误.但是,如果我使用Ed S.的解决方案
My question has gone a little bit off track. The current code setting gives me the stack level too deep
error at line 8. However, if I employ Ed S.'s solution
@left = @right = nil
然后<<
方法抱怨说:undefined method '<<' for nil:NilClass (NoMethodError)
在第22行.
then the <<
method complains saying: undefined method '<<' for nil:NilClass (NoMethodError)
at line 22.
有人可以建议如何解决这个问题吗?我的想法是,如果我能以某种方式告诉BinaryTree
类,变量left
和right
是BinaryTree
的实例(即它们的类型为BinaryTree
),那一切都会很好.我错了吗?
Could anyone suggest how to resolve this? My idea is that if I could somehow tell the BinaryTree
class that variables left
and right
are of instances of BinaryTree
(i.e. their type is BinaryTree
) it would all be well. Am I wrong?
推荐答案
尽管我似乎在那段特定的代码中没有使用任何递归:
although I don't seem to be using any recursion in that particular piece of code:
但是...
def initialize( value = nil )
@value = value
@left = BinaryTree.new # this calls initialize again
@right = BinaryTree.new # and so does this, but you never get there
end
那是无限递归.您呼叫initilize
,后者依次呼叫new
,其依次呼叫initialize
...然后我们就开始了.
That is infinite recursion. You call initilize
, which in turn calls new
, which in turn calls initialize
... and around we go.
您需要在其中添加保护以检测您已经初始化了主节点,并且正在初始化叶子,在这种情况下,@left
和@right
应该只设置为nil
.
You need to add a guard in there to detect that you have already initialized the main node and are now initializing leafs, in which case, @left
and @right
should just be set to nil
.
def initialize( value=nil, is_sub_node=false )
@value = value
@left = is_sub_node ? nil : BinaryTree.new(nil, true)
@right = is_sub_node ? nil : BinaryTree.new(nil, true)
end
不过,老实说...为什么不先从左向右初始化为nil?他们还没有价值,那么您将获得什么呢?从语义上讲,它更有意义.您使用一个元素创建了一个新列表,即左右元素尚不存在.我只会用:
To be honest though... why aren't you just initializing left and right to nil to begin with? They don't have values yet, so what are you gaining? It makes more sense semantically; you create a new list with one element, i.e., elements left and right don't yet exist. I would just use:
def initialize(value=nil)
@value = value
@left = @right = nil
end
这篇关于在Ruby中实现二叉树的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!