ruby - 在 Ruby 中实现二叉树

Question

我一直在尝试在 Ruby 中实现 BinaryTree 类，但我得到了 stack level too deep错误，尽管我似乎没有在该特定代码段中使用任何递归:

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

编辑:我的问题有点偏离正轨。当前代码设置为我提供了 stack level too deep第 8 行出现错误。但是，如果我采用 Ed S. 的解决方案

@left = @right = nil

然后是 <<方法提示说:undefined method '<<' for nil:NilClass (NoMethodError)在第 22 行。

谁能建议如何解决这个问题？我的想法是，如果我能以某种方式告诉 BinaryTree变量left的类和 right是 BinaryTree 的实例(即它们的类型是 BinaryTree )一切都会好起来的。我错了吗？

Answer 1

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...然后我们开始。

你需要在那里添加一个守卫来检测你已经初始化了主节点，现在正在初始化叶子，在这种情况下，@left 和 @right应该设置为 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

---

但老实说...您为什么不直接将 left 和 right 初始化为 nil 呢？他们还没有值(value)，那么你得到了什么？它在语义上更有意义；您创建一个包含一个元素的新列表，即左右元素尚不存在。我只会使用:

def initialize(value=nil)
    @value = value
    @left = @right = nil
end