nash e. foster
4/21/2007 6:54:00 AM
I think this is more complex than necessary. I'll go through yours
and then show you another approach. Your tree is a little weird,
though, as it doesn't sort or balance anything. That's not wrong,
just unusual.
On Sat, Apr 21, 2007 at 11:28:41AM +0900, Martin wrote:
>
> class Node
> attr_accessor :left, :right, :key, :data
>
> def initialize(key, data)
Best to provide a default for key and data. E.g.,
def initialize(key="root", data=0)
> @left = nil
> @right = nil
> @key = key
> @data = data
> end
>
> def to_s()
> print "Key = ", @key, " Data = ", @data
More idiomatic ruby:
p "Key = #{@key} Data = #{@data}"
> end
> end
>
> class Tree
The Tree class isn't really helpful here. Having a higher level
object to contain the nodes isn't bad or wrong, but it complicates
things and it's distracting. My implementation below just omitted
this, but you could put it back. Putting the logic in the Tree class
is actually probably better, since individual Node instances could
be part of multiple Trees with different logic all at the same time,
but we're getting ahead of ourselves.
> 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
The variable 'node' is an argument variable. It's basically like a
stack variable in C. When insertNode returns, the binding goes away
and so this assignment only does something within the context of this
function. The variable "node" doesn't hold a reference to the original
variable's slot from the calling function. Here's another example:
def foo()
x = 1
bar(x)
p x
end
def bar(y)
y = 5
p y
end
foo()
5
1
See? When bar is done, the 'y' variable goes away and the value '5' is
lost. It's not stored in the place the original 'x' lived because they
are different variables.
> 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()
>
Ok, here's mine:
class Node
attr_accessor :left, :right, :key, :data
def initialize(key="root", data=0)
@left = nil
@right = nil
@key = key
@data = data
end
def insert(newNode)
return if nil == newNode
# insert it to the left if it's <= what we have, otherwise right
if self.data <= newNode.data then
if @left then
@left.insert newNode
else
@left = newNode
end
else
if @right then
@right.insert newNode
else
@right = newNode
end
end
end
def visit(depth=0)
print " " * depth * 2 # two spaces per level in the tree
print "#{self.key} -> #{self.data}\n"
@left.visit(depth+1) if @left
@right.visit(depth+1) if @right
end
end
arbre = Node.new
arbre.insert Node.new("un", 1)
arbre.insert Node.new("quatre", -4)
arbre.insert Node.new("deux", 2)
arbre.insert Node.new("trois", 3)
arbre.visit
ciao,
--nash