Thực hiện cây nhị phân trong Ruby

Question

Tôi đã cố gắng triển khai lớp BinaryTree trong Ruby, nhưng tôi nhận được lỗi stack level too deep, mặc dù tôi dường như không sử dụng bất kỳ đệ quy nào trong đoạn mã cụ thể đó:

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 

Chỉnh sửa: Câu hỏi của tôi đã biến mất một chút. Thiết lập mã hiện tại mang lại cho tôi những lỗi stack level too deep tại dòng 8. Tuy nhiên, nếu tôi sử dụng giải pháp Ed S. của

@left = @right = nil 

sau đó phương pháp << phàn nàn nói: undefined method '<<' for nil:NilClass (NoMethodError) tại dòng 22.

thể bất cứ ai đề nghị làm thế nào để giải quyết điều này? Ý tưởng của tôi là nếu tôi bằng cách nào đó có thể nói với lớp BinaryTree rằng các biến số left và right là các trường hợp của BinaryTree (tức là loại của chúng là BinaryTree) thì tất cả sẽ tốt. Liệu tôi có sai?

Answer 1

mặc dù tôi dường như không được sử dụng bất kỳ đệ quy trong đó đoạn cụ thể của mã:

Tuy nhiên ...

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 

Đó là đệ quy vô hạn. Bạn gọi số initilize, mà lần lượt gọi new, mà lần lượt gọi initialize ... và xung quanh chúng tôi đi.

Bạn cần thêm một bảo vệ trong đó để phát hiện rằng bạn đã khởi tạo nút chính và hiện đang khởi tạo các lá, trong trường hợp này, @left và @right chỉ nên được đặt thành 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 

---

Thành thật mà nói mặc dù ... tại sao bạn không chỉ cần khởi tạo trái và phải để nil để bắt đầu với? Họ không có giá trị, vậy bạn đang đạt được điều gì? Nó có ý nghĩa hơn về ngữ nghĩa; bạn tạo danh sách mới với một phần tử, tức là các phần tử bên trái và bên phải chưa tồn tại. Tôi sẽ chỉ sử dụng:

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

Bạn có thể cần phải sửa chữa các đệ quy vô hạn trong mã của bạn. Đây là một ví dụ làm việc của cây nhị phân. Bạn cần phải có một điều kiện cơ bản để chấm dứt đệ quy của bạn ở đâu đó, nếu không nó sẽ là một đống chiều sâu vô hạn.

# 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