Skip to content

Instantly share code, notes, and snippets.

@ryanbriones
Created April 3, 2011 04:07
Show Gist options
  • Save ryanbriones/900168 to your computer and use it in GitHub Desktop.
Save ryanbriones/900168 to your computer and use it in GitHub Desktop.
trying to understand binary trees using Ruby. had this on my desktop, wanted it off, but didn't want to lose it
class BinaryTree
def initialize
@size = 0
@root = nil
end
def insert(data)
node = BinaryTreeNode.new(data)
if @root.nil?
@root = node
else
@root.insert(node)
end
end
def in_order
@root.in_order
end
def pre_order
@root.pre_order
end
def post_order
@root.post_order
end
end
class BinaryTreeNode
include Comparable
attr_reader :data
def <=>(another)
self.data <=> another.data
end
def initialize(data)
@data = data
@left = nil
@right = nil
end
def insert(node)
position = self <=> node
case position
when 1
if(@left.nil?)
@left = node
else
@left.insert(node)
end
when -1
if(@right.nil?)
@right = node
else
@right.insert(node)
end
else
raise "something bad happened"
end
end
def in_order
@left.in_order if @left
puts self.data
@right.in_order if @right
end
def pre_order
puts self.data
@left.pre_order if @left
@right.pre_order if @right
end
def post_order
@left.pre_order if @left
@right.pre_order if @right
puts self.data
end
end
tree = BinaryTree.new
tree.insert(5)
tree.insert(3)
tree.insert(8)
tree.insert(1)
tree.insert(4)
tree.in_order
puts
tree.pre_order
puts
tree.post_order
class BinarySearchTree < BinaryTree
def insert(data)
node = AVLNode.new(data)
if(@root.nil?)
@root = node
else
@root.insert(node)
end
end
end
class AVLNode
def initialize(data)
@data = data
@left = nil
@right = nil
@factor = 0
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment