Re: tree structures

Hmm. To be very, very, very frank, If I wanted binary trees for something, I'd
let the Berkeley DB do this for me. There's people way better at making
efficient data structures out there.

Dňa Pondelok 13 Február 2006 03:38 frank napísal:
I am afraid that I should be using struct or they may
be a better way to describe my tree structures rather than using
numbered and linked lists. Any information on using struct in ruby or
pointer equivalents would be appreciated. I am trying to come up with
a way of doing this such that I could use it on trees of any size.
Right now I am using arrays and the bookkeeping is getting tricky.


I smell C.

There are no pointer equivalents. Or rather, there's nothing else, but it
shouldn't matter anyway. Ruby has by-reference semantics, variables hold
references to objects. Which isn't -quite- true, but let's say it is for now.

Classes are your friends. But I'll let the code do the talking. If you find
you don't understand something, I recommend you read the Pickaxe book,
available for free online in the first edition, which is probably enough for
now. As a matter of fact, you should read it anyway, with nothing insulting
in mind, you have a little to learn about this gem of a language that is
Ruby. (Did I just make a pun?)

# A node of a binary tree.
class Node
attr_reader :left
attr_reader :right
attr_accessor :value
attr_accessor :parent

def left=(node)
@left = node
left.parent = self
end

def right=(node)
@right = node
right.parent = self
end

# Recursively duplicate a node.
def initialize_copy(node)
self.value = node.value
self.left = node.left.dup if node.left
self.right = node.right.dup if node.right
end

def initialize(new_value = nil)
self.value = new_value
end

# The recursive string conversion.
def to_s
"(" + [left, value, right].join(", ") + ")"
end

end

Calling Node#dup should duplicate a (sub) tree properly.

David Vallner


.

Relevant Pages
Loading