wykonawcze Binary Tree in Ruby

Question

Próbuję zaimplementować klasę BinaryTree w Ruby, ale dostaję błąd stack level too deep, chociaż nie wydaje się być za pomocą dowolnego rekursji w danym kawałku kodu:

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 

Edycja: Moje pytanie nieco się zmieniło. Aktualne ustawienie kod daje mi błąd w wierszu 8. stack level too deep Jednakże, jeśli zatrudniają rozwiązanie Ed S.

@left = @right = nil 

wówczas metoda << narzeka mówiąc: undefined method '<<' for nil:NilClass (NoMethodError) na linii 22.

Czy ktoś może sugerować jak rozwiązać ten problem? Mój pomysł jest taki, że gdybym mógł jakoś powiedzieć klasie BinaryTree, że zmienne są instancjami BinaryTree (tj. Ich typ to BinaryTree), wszystko byłoby dobrze. Czy się mylę?

Answer 1

choć nie wydają się być za pomocą dowolnego rekursji w danym kawałku kodu:

jednak ...

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 

czyli nieskończonej rekurencji. Dzwonisz pod numer initilize, który z kolei dzwoni pod numer new, który z kolei wywołuje initialize ... i dookoła idziemy.

Musisz dodać strażnika, aby wykryć, że masz już zainicjowany główny węzeł i teraz inicjalizujesz listę, w takim przypadku, @left i @right powinny być ustawione na 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 

---

Aby być uczciwym, choć ... dlaczego nie tylko inicjowanie lewo i prawo do zera na początku? Nie mają jeszcze wartości, więc co zyskujesz? Ma więcej sensu semantycznie; tworzysz nową listę z jednym elementem, tzn. elementy lewe i prawe jeszcze nie istnieją. Chciałbym po prostu użyć:

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

Być może trzeba rozwiązać nieskończonej rekurencji w kodzie. Oto działający przykład drzewa binarnego. Musisz mieć podstawowy warunek, aby zakończyć rekursję gdzieś, inaczej będzie to stos o nieskończonej głębokości.

# 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