在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屋！