#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2008
    Posts
    4
    Rep Power
    0

    Ruby Binary Search Tree


    This is my first program and Ruby and I am trying to get some help on writing a BST.



    Code:
    require 'rational'
    
    class BST
        def insert(newo)
            if ! @o
    	   @o = newo
    	else
    	    case @o <=> newo
    		when 1
    		    @left = BST.new if ! @left
    		    @left.insert(newo)
    		when -1 
    		    @right = BST.new if ! @right
    		    @right.insert(newo)
    		when nil
    		    puts "#{@o} <=> #{newo} not defined"
    	    end
    	end
        end
    
        def to_s; @o; end
    
        def in_order
            [@left ? @left.in_order : [], @o, @right ? @right.in_order : []]
        end
        
        def pre_order
            [@o ? @o.pre_order : [], @o, @right ? @right.pre_order : []]
        end
    
        #def post_order
        #    [@left ? @left.in_order : [], @o, @right ? @right.in_order : []]
        #end
    
    end

    tree=BST.new
    tree.insert(0)
    tree.insert(5)
    tree.insert(1)
    tree.insert(10)
    puts tree.pre_order

    I tried creating a pre_order method and I continue getting an undefined method error whenever trying to use it. What exactly am I doing wrong with this? The in_order method works, now I am trying to get pre_order and post_order works.
  2. #2
  3. Banned ;)
    Devshed Supreme Being (6500+ posts)

    Join Date
    Nov 2001
    Location
    Woodland Hills, Los Angeles County, California, USA
    Posts
    9,616
    Rep Power
    4247
    Code:
        def pre_order
            [@o, @left ? @left.pre_order : [], @right ? @right.pre_order : []]
        end
    That'll fix it.

    The problem is that @o is of type Fixnum and doesn't have a pre_order method. @left and @right are of type BST and have a pre_order method. That is why you can't call @o.pre_order.
    Up the Irons
    What Would Jimi Do? Smash amps. Burn guitar. Take the groupies home.
    "Death Before Dishonour, my Friends!!" - Bruce D ickinson, Iron Maiden Aug 20, 2005 @ OzzFest
    Down with Sharon Osbourne

    "I wouldn't hire a butcher to fix my car. I also wouldn't hire a marketing firm to build my website." - Nilpo
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2008
    Posts
    4
    Rep Power
    0
    Thanks for the help Scorpions4ever. That helped me understand how these methods actually work.

    I am one confused again. I tried creating a BST of 3 and the output from my methods is as follows:

    Code:
        
    def to_s; @o; end     
    def print_left; @left;  end     
    def print_right; @right; end      
    def in_order [@left ? @left.in_order : [], @o, @right ? @right.in_order : []]     end         
    def pre_order [@o, @left ? @left.pre_order : [], @right ? @right.pre_order : []]     end              
    def post_order [@left ? @left.post_order : [], @right ? @right.post_order : [], @o]end  
    end  
    #eval $*[0]  
    # $ ruby -r rational BST.rb '\ 
    tree=BST.new  
    tree.insert(1)  
    tree.insert(2) 
    tree.insert(3) 
    puts 'In order' 
    puts tree.in_order 
    puts'' 
    puts 'Pre order' 
    puts tree.pre_order 
    puts'' 
    puts 'Post order' 
    puts tree.post_order 
    #puts tree.print_left 
    #puts tree.to_s 
    #puts tree.print_right
    The output of this:

    >ruby BST.rb
    In order
    1
    2
    3

    Pre order
    1
    2
    3

    Post order
    3
    2
    1
    >Exit code: 0

    Why doesn't this end up with In: 1 2 3, Pre: 2 1 3, Post 1 3 2.

    Am I implementing something wrong?
  6. #4
  7. Banned ;)
    Devshed Supreme Being (6500+ posts)

    Join Date
    Nov 2001
    Location
    Woodland Hills, Los Angeles County, California, USA
    Posts
    9,616
    Rep Power
    4247
    Nope. You inserted the items in the order 1, 2, 3 here:
    Code:
    tree.insert(1)  
    tree.insert(2) 
    tree.insert(3)
    Try inserting the items in the order 2, 1, 3:
    Code:
    tree.insert(2) 
    tree.insert(1)  
    tree.insert(3)
    and print pre-order, in-order and post-order and see what happens.

    Research what pre-order and in-order are supposed to do to the tree. Then you'll see that it is working just fine.
    Up the Irons
    What Would Jimi Do? Smash amps. Burn guitar. Take the groupies home.
    "Death Before Dishonour, my Friends!!" - Bruce D ickinson, Iron Maiden Aug 20, 2005 @ OzzFest
    Down with Sharon Osbourne

    "I wouldn't hire a butcher to fix my car. I also wouldn't hire a marketing firm to build my website." - Nilpo
  8. #5
  9. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2008
    Posts
    4
    Rep Power
    0
    Originally Posted by Scorpions4ever
    Nope. You inserted the items in the order 1, 2, 3 here:
    Code:
    tree.insert(1)  
    tree.insert(2) 
    tree.insert(3)
    Try inserting the items in the order 2, 1, 3:
    Code:
    tree.insert(2) 
    tree.insert(1)  
    tree.insert(3)
    and print pre-order, in-order and post-order and see what happens.

    Research what pre-order and in-order are supposed to do to the tree. Then you'll see that it is working just fine.
    Thanks again for the help. Is there anyway to print the tree out to visibly see it connected?
  10. #6
  11. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2008
    Posts
    4
    Rep Power
    0
    Oops, thought of one more thing I must implement. I have to create iterators for each method performing pre,post, and in orders. Why to do I need to do this? I don't really understand why.

IMN logo majestic logo spyfu logo threadwatch logo seochat tools logo