實現二叉樹在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