|
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
def infix()
if @left != nil
flag = %w[* / + -].include? @left.data
yield "(" if flag
@left.infix {|y| yield y}
yield ")" if flag
end
yield @data
if @right != nil
flag = %w[* / + -].include? @right.data
yield "(" if flag
@right.infix {|y| yield y} if @right != nil
yield ")" if flag
end
end
end
def addnode(nodes)
node = nodes.shift
tree = Tree.new node
if %w[* / + -].include? node
tree.left = addnode nodes
tree.right = addnode nodes
end
tree
end
prefix = %w[ * + 32 * 21 45 - 72 + 23 11 ]
tree = addnode prefix
str = ""
tree.infix {|x| str += x}
# str is now "(32+(21*45))*(72-(23+11))"
|