-----------------------------------

Tony

Fri Sep 02, 2005 5:07 pm


building trees in Ruby

-----------------------------------

how would I go about putting one together and then traversing it?


-----------------------------------

wtd

Fri Sep 02, 2005 6:23 pm



-----------------------------------

class BTreeNode
   attr_reader :value
   attr_accessor :left, :right

   def initialize(value, left = nil, right = nil)
      @value = value
      @left, @right = left, right
   end

   def to_a
      ...
   end

   def each 
      ...
   end
end


-----------------------------------

Tony

Sat Sep 03, 2005 12:40 am



-----------------------------------

I don't quite get it. How would a pointer look like, and how would I use it?

Other than an array that is :lol:


-----------------------------------

wtd

Sat Sep 03, 2005 12:49 am



-----------------------------------

No pointers.

But you can have an instance variable be either nil or another BTreeNode.


-----------------------------------

Tony

Sat Sep 03, 2005 1:56 am



-----------------------------------

I suppose I could always just inline C :lol:


-----------------------------------

wtd

Sat Sep 03, 2005 2:58 am



-----------------------------------

Ok... let's look at traversing a Ruby binary tree.

def values
   output = [@value]
   output.push(*@left.values) unless @left.nil?
   output.push(*@right.values) unless @right.nil?
   output
end


-----------------------------------

Cervantes

Mon Sep 05, 2005 5:28 pm



-----------------------------------

Though I haven't finished reading it, perhaps [url=http://www.compsci.ca/v2/viewtopic.php?t=8243]wtd's tutorial on linked lists and binary trees in Haskell, Java, and Ruby will help.


-----------------------------------

wtd

Mon Sep 05, 2005 5:37 pm



-----------------------------------

The very short answer...

"nil" is your Ruby equivalent to a NULL pointer.


-----------------------------------

Tony

Mon Sep 05, 2005 9:07 pm



-----------------------------------

ah, excellent :D I'll be trying out the examples.