martingagne / gmail.com wrote:
> On Apr 21, 12:26 am, Dan Zwell <dzw... / gmail.com> wrote:
>> Martin wrote:
>>> Hi all!
>>> I'm a newbie in Ruby and I am trying to implement a Binary Tree.
>>> However, it doesn't work. Could someone please help me?
>>> Thank you !
>>> class Node
>>>   attr_accessor :left, :right, :key, :data
>>>   def initialize(key, data)
>>>     @left = nil
>>>     @right = nil
>>>     @key = key
>>>     @data = data
>>>   end
>>>   def to_s()
>>>     print "Key = ", @key, " Data = ", @data
>>>   end
>>> end
>>> class Tree
>>>   attr_accessor :root
>>> public
>>>   def initialize()
>>>     @root = nil
>>>     print "Root Object Id ", @root.object_id, "\n"
>>>   end
>>>   def insert(newNode)
>>>     insertNode(@root, newNode)
>>>   end
>>>   def visit()
>>>     visitNode(@root)
>>>   end
>>> private
>>>   def insertNode(node, newNode)
>>>     print "Node Object Id ", node.object_id, "\n"
>>>      print "New Node Object Id ", newNode.object_id, "\n"
>>>     if (node == nil)
>>>       node = newNode
>>>        print "Node Affected Object Id ", node.object_id, "\n"
>>>     print @root
>>>         print node
>>>     else
>>>       if (newNode.data <= node.data)
>>>         insertNode(node.left, newNode)
>>>         print "Gauche"
>>>       else
>>>         insertNode(node.right, newNode)
>>>         print "Droite"
>>>       end
>>>     end
>>>   end
>>>   def visitNode(node)
>>>     if (node != nil)
>>>       print node.key
>>>       if (node.left != nil)
>>>         visitNode(node.left)
>>>       end
>>>       if (node.right != nil)
>>>         visitNode(node.right )
>>>       end
>>>     end
>>>   end
>>> end
>>> arbre = Tree.new
>>> arbre.insert(Node.new(1, "un"))
>>> arbre.insert(Node.new(2, "deux"))
>>> arbre.insert(Node.new(3, "trois"))
>>> arbre.visit()
>> Martin,
>>
>> In short, I don't know how to fix it. But the problem is with this line:
>>
>> node = newNode
>>
>> It doesn't seem to do what you want. I think it takes the reference
>> variable "node" (previously pointing at @root, until the method
>> recurses) and point it at a new variable ("newNode"). That isn't what
>> you want--you want to replace the contents of the node, not change the
>> reference. I don't know how to do this. I got something by changing the
>> above line to "@root = newNode", but that really breaks the algorithm.
>>
>> Dan Zwell
> 
> Hi Dan,
> 
> You're right, the problematic line is definitely: node = newNode.
> 
> When the tree has no root (@root == nil), the first node added to the
> tree should become the root. That's why I check just before if the
> node is nil. Since this method is called by insert which pass to
> insertNode the class attribute @root, why Ruby doesn't change the
> value of @root for the value of newNode. I thought that Ruby was using
> only references... Am I right?
> 
> Thank you for your help...
> 
> Martin
> 
> 
> 

Ruby doesn't change the value of @root (even though that is what is 
pointed to by "node") because it's busy changing the value of "node". 
Ruby variables don't seem to mate for life. As soon as ruby sees the 
'=', "node" no longer points at @root. This may be one disadvantage of a 
really loosely typed language. As for how to make the binary tree work, 
I can't think of a way that doesn't involve rewriting a lot of it to 
avoid this problem. If you really wanted to, perhaps you could store the 
nodes in an array and pass around index numbers instead of passing 
around nodes themselves? But then you lose some of advantages of a 
binary tree, and it's really not elegant.

You could rewrite the algorithm a little, but it is going to involve two 
things:
- at some point, you will need to explicitly set @root
- I suspect "node.left =" and "node.right =" will work as expected, so 
you wan assign to those directly, even if "node" is just some variable.

Sorry for not having a good answer,

Dan