实现二叉树在Ruby中

Question

我一直想在Ruby中实现二叉树类，但我得到了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 

编辑：我的问题有点偏离轨道。当前的代码设置给了我在第8行的stack level too deep错误但是，如果我聘请埃德S.的解决方案

@left = @right = nil 

那么<<方法抱怨说：undefined method '<<' for nil:NilClass (NoMethodError)在22行

任何人都可以建议如何解决这个问题？我的想法是，如果我能以某种方式告诉BinaryTree类变量left和right属于BinaryTree（即它们的类型是BinaryTree）的实例，那一切都会好的。我错了吗？

Answer 1

虽然我似乎没有使用任何递归在特定的一段代码：

然而...

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 

---

说实话，虽然...你为什么不只是初始化左右，以零开始与？他们还没有价值，所以你获得了什么？它在语义上更有意义;你用一个元素创建一个新的列表，即左右元素还不存在。我只想用：

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

Answer 2

1. class BinaryTree 
2. include Enumerable 
3.  
4.  attr_accessor :value 
5.  
6.  def initialize(value = nil) 
7.   @value = value 
8.  end 
9.  
10.  def each # visit 
11.   return if self.nil? 
12.   
13.   yield self.value 
14.   self.left.each(&block) if self.left 
15.   self.right.each(&block) if self.right  
16.  end 
17. 
18.  def empty? 
19.   # code here 
20.  end 
21.   
22.  def <<(value) # insert 
23.   return self.value = value if self.value == nil 
24. 
25.   test = self.value <=> value 
26.   case test 
27.    when -1, 0 
28.     @right = BinaryTree.new if self.value == nil 
29.     self.right << value 
30.    when 1 
31.     @left = BinaryTree.new if self.value == nil 
32.     self.left << value 
33.   end 
34.  end  # << 
35. end 

Answer 3

您可能需要修复无限递归在你的代码。这是一个二叉树的工作示例。你需要有一个基本条件来终止你的递归，否则它将是无限深度的堆栈。

# Example of Self-Referential Data Structures - A Binary Tree 

class TreeNode 
    attr_accessor :value, :left, :right 

    # The Tree node contains a value, and a pointer to two children - left and right 
    # Values lesser than this node will be inserted on its left 
    # Values greater than it will be inserted on its right 
    def initialize val,left,right 
     @value = val 
     @left = left 
     @right = right 
    end 
end 

class BinarySearchTree 

    # Initialize the Root Node 
    def initialize val 
     puts "Initializing with: " + val.to_s 
     @root = TreeNode.new(val,nil,nil) 
    end 

    # Pre-Order Traversal 
    def preOrderTraversal(node= @root) 
     return if (node == nil) 
     preOrderTraversal(node.left) 
     preOrderTraversal(node.right) 
     puts node.value.to_s 
    end 

    # Post-Order Traversal 
    def postOrderTraversal(node = @root) 
     return if (node == nil) 
     puts node.value.to_s 
     postOrderTraversal(node.left) 
     postOrderTraversal(node.right) 
    end 

    # In-Order Traversal : Displays the final output in sorted order 
    # Display smaller children first (by going left) 
    # Then display the value in the current node 
    # Then display the larger children on the right 
    def inOrderTraversal(node = @root) 
     return if (node == nil) 
     inOrderTraversal(node.left) 
     puts node.value.to_s 
     inOrderTraversal(node.right) 
    end 


    # Inserting a value 
    # When value > current node, go towards the right 
    # when value < current node, go towards the left 
    # when you hit a nil node, it means, the new node should be created there 
    # Duplicate values are not inserted in the tree 
    def insert(value) 
     puts "Inserting :" + value.to_s 
     current_node = @root 
     while nil != current_node 
      if (value < current_node.value) && (current_node.left == nil) 
       current_node.left = TreeNode.new(value,nil,nil) 
      elsif (value > current_node.value) && (current_node.right == nil) 
       current_node.right = TreeNode.new(value,nil,nil) 
      elsif (value < current_node.value) 
       current_node = current_node.left 
      elsif (value > current_node.value) 
       current_node = current_node.right 
      else 
       return 
      end 
     end 
    end 
end 

bst = BinarySearchTree.new(10) 
bst.insert(11) 
bst.insert(9) 
bst.insert(5) 
bst.insert(7) 
bst.insert(18) 
bst.insert(17) 
# Demonstrating Different Kinds of Traversals 
puts "In-Order Traversal:" 
bst.inOrderTraversal 
puts "Pre-Order Traversal:" 
bst.preOrderTraversal 
puts "Post-Order Traversal:" 
bst.postOrderTraversal 

=begin 

Output : 
Initializing with: 10 
Inserting :11 
Inserting :9 
Inserting :5 
Inserting :7 
Inserting :18 
Inserting :17 
In-Order Traversal: 
5 
7 
9 
10 
11 
17 
18 
Pre-Order Traversal: 
7 
5 
9 
17 
18 
11 
10 
Post-Order Traversal: 
10 
9 
5 
7 
11 
18 
17 

=end 

编号：http://www.thelearningpoint.net/computer-science/basic-data-structures-in-ruby---binary-search-tre