Geek asks and answers

Implementing a binary tree in Ruby

I am trying to implement the BinaryTree class in Ruby, but I am getting an error stack level too deep, although it seems I am not using recursion in this particular piece of code:

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

Edit: my question is a little off track. The current code setting gives me an error stack level too deepon line 8. However, if I use the Ed S solution.

@left = @right = nil

then the method <<complains, saying: undefined method '<<' for nil:NilClass (NoMethodError)on line 22.

Can anyone suggest how to solve this? My idea is that if I could somehow tell the class BinaryTreethat the variables leftalso righthave instances BinaryTree(i.e. Their type BinaryTree), everything will be fine. I am wrong?

+5
source share
3 answers

, , :

...

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... .

, , node , @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
+10
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
+2

. . , - , .

# 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

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

0
source

More articles:


All Articles