Uygulama İkili Ağacı Ruby

Question

Ben Ruby BinaryTree sınıfını uygulamak çalışıyorum ama kodun o parça herhangi özyineleme kullanıyor görünüyor olmadığı halde ben, stack level too deep hatası alıyorum içinde:

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 

Düzenleme: Sorum şu ki biraz yoldan gitti. undefined method '<<' for nil:NilClass (NoMethodError) çizgisinde 22.

kimse önermek Could: geçerli kod ayarı Ed S. adlı çözümünü istihdam eğer

@left = @right = nil 

sonra << yöntem söyleyerek şikayet, Ancak bana hattı 8. en stack level too deep hata veriyor Bunu nasıl çözebilirim? Benim düşüncem, BinaryTree sınıfına left ve right değişkenlerinin BinaryTree (örn. Türleri BinaryTree) örneklerinden olduğunu söyleseydim, her şey iyi olurdu. Yanlış mıyım?

Answer 1

kod o parça herhangi özyineleme kullanıyor görünüyor olmadığı halde:

Yine de ... sonsuz özyinelemeye olduğunu

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 numaralı telefonu arayarak numarayı arayarak initialize numaralı telefonu arayabiliriz.

Sen zaten ana düğümü başlatıldı ve şu anda durum, @left ve @right sadece nil ayarlanmalıdır ki, yaprakları başlatılıyor olduğunu tespit etmek için oraya bir bekçi eklemeniz gerekir.

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 

---

neden sadece nil ile başlayacak sol ve sağa başlatılıyor değil ... Ama dürüst olmak gerekirse? Henüz değerlerine sahip değiller, ne kazanıyorsunuz? Anlamsal olarak daha anlamlı olur; Tek bir öğeyle yeni bir liste oluşturursunuz, yani, sol ve sağdaki öğeler henüz mevcut değil. Sadece kullanırsınız:

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

Kodunuzdaki sonsuz yinelemeye düzeltmek gerekebilir. İşte ikili bir ağacın çalışan bir örneği. Yinelemenizi bir yerde sonlandırmak için bir temel koşula sahip olmanız gerekir, aksi takdirde sonsuz derinlikte bir yığın olacaktır.

# 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 

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