|
class Tree
attr_accessor :left
attr_accessor :right
attr_accessor :data
def initialize(x=nil)
@left = nil
@right = nil
@data = x
end
def insert(x)
list = []
if @data == nil
@data = x
elsif @left == nil
@left = Tree.new(x)
elsif @right == nil
@right = Tree.new(x)
else
list << @left
list << @right
loop do
node = list.shift
if node.left == nil
node.insert(x)
break
else
list << node.left
end
if node.right == nil
node.insert(x)
break
else
list << node.right
end
end
end
end
def traverse()
list = []
yield @data
list << @left if @left != nil
list << @right if @right != nil
loop do
break if list.empty?
node = list.shift
yield node.data
list << node.left if node.left != nil
list << node.right if node.right != nil
end
end
def insert(x)
if @data == nil
@data = x
elsif x <= @data
if @left == nil
@left = Tree.new x
else
@left.insert x
end
else
if @right == nil
@right = Tree.new x
else
@right.insert x
end
end
end
def inorder()
@left.inorder {|y| yield y} if @left != nil
yield @data
@right.inorder {|y| yield y} if @right != nil
end
def preorder()
yield @data
@left.preorder {|y| yield y} if @left != nil
@right.preorder {|y| yield y} if @right != nil
end
def postorder()
@left.postorder {|y| yield y} if @left != nil
@right.postorder {|y| yield y} if @right != nil
yield @data
end
def search(x)
if self.data == x
return self
elsif x < self.data
return left != nil ? left.search(x) : nil
else
return right != nil ? right.search(x) : nil
end
end
def to_s
"[" +
if left then left.to_s + "," else "" end +
data.inspect +
if right then "," + right.to_s else "" end + "]"
end
def to_a
temp = []
temp << left.to_a if left
temp << data
temp << right.to_a if right
temp
end
end
items = %w[bongo grimace monoid jewel plover nexus synergy]
tree = Tree.new
items.each {|x| tree.insert x}
str = tree.to_s
# str is now:
# "bongo,grimace,jewel,monoid,nexus,plover,synergy"
arr = tree.to_a
# arr is now:
# ["bongo",["grimace",[["jewel"],"monoid",[["nexus"],"plover",
# ["synergy"]]]]]
|